Ive encountered the following problem studying for my test, with no answer published to it: 1)Maximum double matching problem- given a bipartite graph G=(V=(LUR),E) describe an algorithm that returns a group of edges M in E s.t for each vertice v in V there are atmost 2 edges in M that include v, of a maximum size. 2)Definition: a "Strong double matching" is a double matching s.t for each vertice v in V there is at least one edge in M that includes v. Given a bipartite graph G=(V=(LUR),E) and strong double matching M, describe an algorithm that returns a strong double matching M' of maximum size. Prove your answer.

so Ive already managed to solve a) using reduction to max-flow: adding vertices's s and t and edges from s to L and edges from R to t each with the capacity of 2, and defining the capacity of each edge between L and R with the infinite capacity. Finding a max flow using Dinic's algorithm and returning all edges with positive flow between L and R.

about b- i thought about somehow manipulating the network so that there is positive flow from each vertice then using the algorithm from a somehow to construct a maximum solution. Any thoughts ?? the runtime restriction is O(V^2E) (Dinics runtime)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.