The Art Gallery Guardian

Reduction between vertex disjoint paths and maximum matching


1 Reduce maximum bipartite matching to maximum vertex disjoint paths

Given a bipartite graph , add a vertex and , such that connect to all vertices in and connect to all vertices in . For each vertex disjoint path from to , alternately remove the edges, the remaining is a maximum matching.

2 Reduce maximum vertex disjoint paths to two maximum bipartite matching

This is a slight modification of the reduction in Sankowski’s paper on bipartite matching[1]. It is also a solution to the first problem of the algorithmic trends hw 1.

Notice this consist of two parts, find the value of a maximum matching, and then find a perfect matching on two modified graphs.

Let to be a directed graph with specified nodes and (for simplicity, assume ). Define be a bipartite graph of edges and vertices, where , , and . Notice it is similar to the common vertex split in max flow, where get’s split into and .

consist of following edges:

  1. if and .
  2. for all .
  3. for all and .
  4. for all and .

We can find maximum number of vertex disjoint paths from to by solving a maximum matching problem on a bipartite graph . Any matching that covers both and would induce some set of vertex disjoint paths by contracting into . It’s clear no such path can start and end in and for some and , similarly no path can start at and end at . Thus we can contract into and into and remove paths doesn’t involves any and to get the set of disjoint paths. The number of such disjoint paths can be readily read from the size of the maximum matching, because the number equals to the number of and ’s matched. Of course, an algorithm for maximum matching might not return a maximum matching that covers both and , but we use a value to build such an graph.

Let the size of the maximum matching be , then there exist maximum vertex disjoint paths. Build graph and find a maximum matching in . This time the matching would be a perfect matching, and use the same idea as above gives the vertex disjoint paths between and .

3 Reference

References

[1]
P. Sankowski, Maximum weight bipartite matching in matrix multiplication time, Theoretical Computer Science. 410 (2009) 4480–4488 10.1016/j.tcs.2009.07.028.
Posted by Chao Xu on .
Tags: Algorithm, Combinatorial Optimization, Matching.