Mader's S-paths theorem
Let [math]G=(V,E)[/math] be an undirected graph, and let [math]{\mathcal S}[/math] be a collection of disjoint subsets of [math]V[/math]. A partition [math]V_0,V_1,\dots,V_k[/math] of [math]V[/math] is called [math]{\mathcal S}[/math]-feasible if every [math]{\mathcal S}[/math]-path contains a node in [math]V_0[/math] or an edge in [math]E[V_i][/math] for some [math]i[/math]. We use the notation
[math]V'_i=V_i \cap (S \cup N(V \setminus (V_0 \cup V_i))).[/math]
Theorem (Mader [1]). The maximum number of node-disjoint [math]{\mathcal S}[/math]-paths equals the minimum, taken over all [math]{\mathcal S}[/math]-feasible partitions [math]V_0,V_1,\dots,V_k[/math], of
[math]|V_0|+\sum_{i=1}^k \left\lfloor \frac{|V'_i|}{2}\right\rfloor .[/math]
Notes
A short proof of the theorem can be found in [2]. Lovász [3] showed that the problem can be reduced to matroid matching, which implies a polynomial algorithm. A randomized algorithm with running time [math]O(n^{\omega})[/math] (where [math]\omega[/math] is the smallest known exponent for matrix multiplication) is presented in [4]. There are also combinatorial polynomial-time algorithms that solve generalizations to group-labeled graphs [5] [6].
References
- ↑ W. Mader, Über die Maximalzahl kreuzungsfreier H-Wege, Arch. Math. 31 (1978), 387-402, DOI link
- ↑ A. Schrijver, A short proof of Mader's S-paths theorem, DOI link, author link
- ↑ L. Lovász, Matroid matching and some applications, DOI link
- ↑ H.Y. Cheung, L.C. Lau, K.M. Leung, Algebraic algorithms for linear matroid parity problems, DOI link, author link
- ↑ M. Chudnovsky, W.H. Cunningham, J. Geelen, An algorithm for packing non-zero A-paths in group-labelled graphs, DOI link, author link
- ↑ Gy. Pap, Packing non-returning A-paths algorithmically, DOI link, conference version
