A bipartite graph is a graph (V, E) whose set of nodes V can be split into two disjoint sets Vi and V2, such that each edge (v, w) 6 E starts out in Vi and ends in V2 (that is, ve Vi and we V2). 1. Write a linear program that can be used to find a set of nodes S of minimum size such that for each edge (v, w) we have v E S or we S. Note that in mathematics, the conjunction "or" is not exclusive. For instance, the following statement is true: -4 E R or TER. Recall that we cannot require decision variables in an LP to be binary, so the optimal solution to your LP could include non-integer values. For full credit, you must specify how to use fractional values to create a node set of optimal size or explain why your optimal solution is guaranteed to be integral. 2. Write down the dual of the LP in (1). Interpret the dual LP. That is, explain in words what each decision variable represents and what is the objective of the problem. 3. Write down the complementary slackness conditions for part (2)