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 G=(S,T,E)G=(S,T,E), add a vertex ss and tt, such that ss connect to all vertices in SS and tt connect to all vertices in TT. For each vertex disjoint path from ss to tt, 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 G=(V,E)G=(V,E) to be a directed graph with specified nodes ss and tt(for simplicity, assume st∉Est\not\in E). Define Gk=(VSk,V+Tk,E)G_k=(V^- \cup S_k ,V^+ \cup T_k,E') be a bipartite graph of O(m+k2)=O(n2)O(m+k^2)=O(n^2) edges and O(n)O(n) vertices, where V={vvV}V^- = \{v^-|v\in V\}, V+={v+vV}V^+ = \{v^+|v\in V\}, Sk={s1,,sk}S_k=\{s_1,\ldots,s_k\} and Tk={t1,,tk}T_k=\{t_1,\ldots,t_k\}. Notice it is similar to the common vertex split in max flow, where vv get’s split into vv^- and v+v^+.

EE' consist of following edges:

  1. uv+Eu^-v^+\in E' if uvEuv\in E and {u,v}{s,t}=\{u,v\}\cap \{s,t\} = \emptyset.
  2. uu+Eu^-u^+\in E' for all uVu\in V.
  3. siv+Es_iv^+\in E' for all 1ik1\leq i\leq k and svEsv\in E.
  4. vtiEv^-t_i\in E' for all 1ik1\leq i\leq k and vtEvt\in E.

We can find maximum number of vertex disjoint paths from ss to tt by solving a maximum matching problem on a bipartite graph GnG_n. Any matching that covers both VV^- and V+V^+ would induce some set of vertex disjoint paths by contracting vv+v^-v^+ into vv. It’s clear no such path can start and end in sis_i and sjs_j for some ii and jj, similarly no path can start at tit_i and end at tjt_j. Thus we can contract SnS_n into ss and TnT_n into tt and remove paths doesn’t involves any ss and tt 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 sis_i and tjt_j’s matched. Of course, an algorithm for maximum matching might not return a maximum matching that covers both VV^- and V+V^+, but we use a value to build such an graph.

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


[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.