Consider a bipartite graph G -(V, E) where each edge e E is given a weight we > 0. Recall that a graph is bipartite if and only if every cycle in the graph is even. A matching M C E of a graph is a set of edges such that no vertex is adjacent to two edges in M. We wish to compute a matching in G that has maximum weight. Let xe be a variable for each edge such that xe-1 if edge e is in a maximum weight matching and e-0 if edge e is not in a maximum weight matching (this is like an indicator variable for the edge e). Consider the following linear program: Maximize Lee Wee subject to ee (eEE)A(vEe) Te 1 for each vertex v E V, and Notice that if each variable xe takes on a value of 0 or 1, then a solution to this linear program gives us a maximum matching. However, it is possible that some variable xe to have a fractional value like 1/2. Consider the bipartite graph in Figure 5 and notice that it is a feasible solution to the above linear program. Now, if this solution is an optimal solution, then notice that there exists an optimal solution where each variable xe takes on a value of 0 or 1 regardless of the non-zero weights put on the edges. e2 Xe,-1/2 Figure 1: Bipartite graph with non-integral feasible solution to the LP. (a) Suppose that we have a solution where each variable xe takes on a value of 0 or 1. Prove that the set of edges whose corresponding ^e takes on a value of 1 forms a matching Consider a bipartite graph G -(V, E) where each edge e E is given a weight we > 0. Recall that a graph is bipartite if and only if every cycle in the graph is even. A matching M C E of a graph is a set of edges such that no vertex is adjacent to two edges in M. We wish to compute a matching in G that has maximum weight. Let xe be a variable for each edge such that xe-1 if edge e is in a maximum weight matching and e-0 if edge e is not in a maximum weight matching (this is like an indicator variable for the edge e). Consider the following linear program: Maximize Lee Wee subject to ee (eEE)A(vEe) Te 1 for each vertex v E V, and Notice that if each variable xe takes on a value of 0 or 1, then a solution to this linear program gives us a maximum matching. However, it is possible that some variable xe to have a fractional value like 1/2. Consider the bipartite graph in Figure 5 and notice that it is a feasible solution to the above linear program. Now, if this solution is an optimal solution, then notice that there exists an optimal solution where each variable xe takes on a value of 0 or 1 regardless of the non-zero weights put on the edges. e2 Xe,-1/2 Figure 1: Bipartite graph with non-integral feasible solution to the LP. (a) Suppose that we have a solution where each variable xe takes on a value of 0 or 1. Prove that the set of edges whose corresponding ^e takes on a value of 1 forms a matching
