Problem 1. Matching. [25 points Consider the following problem Bipartite-Perfect-Matching Input: Undirected bipartite graph G = (V, E) with bipartition V = LUR where |LI IRI- Output: A perfect matching if one exists, and NO if none exist in G exactly one edge in S. Here is an example of a bipartite graph with a perfect matching in dashed edges: bi b2 Explain how to reduce the Bipartite-Perfect-Matching problem to the max-flow problem. In other words, explain how to solve the bipartite perfect matching problem using the algorithm for solving max-flow as a black-box. Part (a): Given an input G = (V, E) to the Bipartite-perfect-Matching problem, explain how you create the input to the max-flow problem (specify the graph G and the edge capacities in this new graph). Do not do it for Part (b): Given a max-flow f for the flow network that you defined in part (a), explain how you use f to determine if G has a perfect matching. Part (e): What is the running time of your algorithm in terms of the original graph G where n V andm E. State whether you are using the Ford- Fulkerson or Edmonds-Karp algorithm (only consider these two which we saw in class); faster is better. Part (d): A 2-perfect subgraph is a subset S of edges where every vertex has degree exactly 2 in S. So a perfect matching corresponds to a 1-perfect subgraph. Below is an example graph with a 2-perfect subgraph marked by red/dashed lines. Explain what needs to change in part (a) to check if a bipartite graph G has a 2-perfect subgraph Problem 1. Matching. [25 points Consider the following problem Bipartite-Perfect-Matching Input: Undirected bipartite graph G = (V, E) with bipartition V = LUR where |LI IRI- Output: A perfect matching if one exists, and NO if none exist in G exactly one edge in S. Here is an example of a bipartite graph with a perfect matching in dashed edges: bi b2 Explain how to reduce the Bipartite-Perfect-Matching problem to the max-flow problem. In other words, explain how to solve the bipartite perfect matching problem using the algorithm for solving max-flow as a black-box. Part (a): Given an input G = (V, E) to the Bipartite-perfect-Matching problem, explain how you create the input to the max-flow problem (specify the graph G and the edge capacities in this new graph). Do not do it for Part (b): Given a max-flow f for the flow network that you defined in part (a), explain how you use f to determine if G has a perfect matching. Part (e): What is the running time of your algorithm in terms of the original graph G where n V andm E. State whether you are using the Ford- Fulkerson or Edmonds-Karp algorithm (only consider these two which we saw in class); faster is better. Part (d): A 2-perfect subgraph is a subset S of edges where every vertex has degree exactly 2 in S. So a perfect matching corresponds to a 1-perfect subgraph. Below is an example graph with a 2-perfect subgraph marked by red/dashed lines. Explain what needs to change in part (a) to check if a bipartite graph G has a 2-perfect subgraph
