Problem 5. (3 pts) Fractional Matching in regular and bipartite graphs. In the standard Matching problem, given a graph G our goal is to find a subset of the edge MCE such that each vertex is adjacent to at most one edge in M. Of course, Mis a valid matching and so our goal is the largest possible matching in the graph G, i.e. a maximum matching It is possible to relax the problem and allow one to choose fractions of edges; and now we want that for each vertex u the total chosen fractions of edges adjacent to u is at most 1. This can be written obviously as a LP with |E| variables, where for each edge re E [0, 1] max s.t. Vu Te ! e: e adjacent to u Just FYI (this is irrelevant to the question): Because no point lies on the hyperplane then the sign is never 0 and so for all points sign(w-b) E { 1, 1), and similarly 11 E {-1, 1). So having the two signs match is formulated, in some books, as the constraintsVi, i sign(w-T-b)-1 (i) (1 pts) Give an example of a graph (with very few nodes and edges) where the largest fractional matching, i.e. the value of the LP you write for this particular graph, is strictly greater than the size of the integral (the standard) maximum matching. Your answer must include the particular LP you write for this particular graph, as well as a proof the the LP-value (of the specific LP you outlined) is strictly greater than the maximal matching size (i) (2 pts) Prove that for any bipartite graph, there exists an optimal solution for the LP which is integral, thereby proving that the LP-value on bipartite graph is exactly the size of the maximum- matching. Here is one way to reason about it. ASOC that all optimal solutions to the LP have non-integer entries Pick z* as an optimal solution where the number of non-integer coordinates is minimized. Now use x* to construct an optimal solution y with at least one more integer coordinate, contradicting the minimality of x* How to construct such a z? Note that every edge e has one LHS node and one RHS node. Think of using " to walk around the edges of G using only fractional edges (edge e whose r E (0,1)). Cal a fractional edge e eztendable from the left if its LHS vertex is adjacent to another edge e e which is also fractional; and similarly call a fraction edge e ertendable from the right if its RHS vertex is adjacent to another edge e' e which is also fractional. This means that if I walk around G using only fractional edges, then from an edge e which is extendable from the left I can use its LHS node to move a different fractional edge; and if e is extendable from the right I can use its RHS node to move toa different fractional edge. Now ask yourself What if there exists a fractional edge which isn't extendable from the left or from the right? What if there exists a fractional edge which is extendable only from the left but not from the right (or vice-versa)? Leaving us to deal with the toughest case: what if all fractional edges are extendable both from the left and from the right? Hint: cycles in a bipartite graph. Problem 5. (3 pts) Fractional Matching in regular and bipartite graphs. In the standard Matching problem, given a graph G our goal is to find a subset of the edge MCE such that each vertex is adjacent to at most one edge in M. Of course, Mis a valid matching and so our goal is the largest possible matching in the graph G, i.e. a maximum matching It is possible to relax the problem and allow one to choose fractions of edges; and now we want that for each vertex u the total chosen fractions of edges adjacent to u is at most 1. This can be written obviously as a LP with |E| variables, where for each edge re E [0, 1] max s.t. Vu Te ! e: e adjacent to u Just FYI (this is irrelevant to the question): Because no point lies on the hyperplane then the sign is never 0 and so for all points sign(w-b) E { 1, 1), and similarly 11 E {-1, 1). So having the two signs match is formulated, in some books, as the constraintsVi, i sign(w-T-b)-1 (i) (1 pts) Give an example of a graph (with very few nodes and edges) where the largest fractional matching, i.e. the value of the LP you write for this particular graph, is strictly greater than the size of the integral (the standard) maximum matching. Your answer must include the particular LP you write for this particular graph, as well as a proof the the LP-value (of the specific LP you outlined) is strictly greater than the maximal matching size (i) (2 pts) Prove that for any bipartite graph, there exists an optimal solution for the LP which is integral, thereby proving that the LP-value on bipartite graph is exactly the size of the maximum- matching. Here is one way to reason about it. ASOC that all optimal solutions to the LP have non-integer entries Pick z* as an optimal solution where the number of non-integer coordinates is minimized. Now use x* to construct an optimal solution y with at least one more integer coordinate, contradicting the minimality of x* How to construct such a z? Note that every edge e has one LHS node and one RHS node. Think of using " to walk around the edges of G using only fractional edges (edge e whose r E (0,1)). Cal a fractional edge e eztendable from the left if its LHS vertex is adjacent to another edge e e which is also fractional; and similarly call a fraction edge e ertendable from the right if its RHS vertex is adjacent to another edge e' e which is also fractional. This means that if I walk around G using only fractional edges, then from an edge e which is extendable from the left I can use its LHS node to move a different fractional edge; and if e is extendable from the right I can use its RHS node to move toa different fractional edge. Now ask yourself What if there exists a fractional edge which isn't extendable from the left or from the right? What if there exists a fractional edge which is extendable only from the left but not from the right (or vice-versa)? Leaving us to deal with the toughest case: what if all fractional edges are extendable both from the left and from the right? Hint: cycles in a bipartite graph