Consider a graph where vertices represent intersections and edges represent roads. The company Food To Go can place a maximum of one food cart at each intersection. A food cart placed at intersection X has an income equal to the number of roads at intersection X (ie, the degree of vertex X). If two food carts share a road, the income of that road is shared equally among the two. We are interested in calculating the total profit of all food carts placed, ie, the total income minus the cost, where each food cart costs 1 unit and each road provides an income of 1 unit. More formally, the profit for a graph G = (V,E) where the set SCV represents food cart locations, is calculated by the number of edges covered by the vertices in S minus the size of S (ie. |S|). E B In this example, placing a food cart on each of the vertices A and C will result in a profit of |{(A, B), (A,C'), (A, D), (C, D), (C, E)}| |{A,C}|= 5 2 = 3. The decision version for the food cart problem asks to find a subset of vertices such that the profit for G, as defined above, is maximized. FoodCart Dec Input: G = (V,E), integer k > 0 Question: Does there exist SCV where | Es| |S| k? Here, Es CE denotes the set of all edges (x, y) = E where at least one endpoint of (x, y) is in S, that is S or y S. 1. Define the language Lpc corresponding to FoodCartdec 2. Show that LFC NP. For this: Clearly describe what a certificate looks like. Then give a polynomial-time verifier and proof its correctness. 3. Define the optimization version FoodCartopt for decision version FoodCart Dee.