Disjoint S-paths
Let [math]G=(V,E)[/math] be an undirected graph, and [math]S \subseteq V[/math] a subset of nodes. An [math]S[/math]-path is a path between two distinct nodes in [math]S[/math] that does not contain any other node from [math]S[/math]. The problem of finding the maximum number of node-disjoint [math]S[/math]-paths can be reduced to maximum matching.
If [math]{\mathcal S}[/math] is a collection of disjoint subsets of [math]V[/math], then a path is called an [math]{\mathcal S}[/math]-path if its endnodes are in different members of [math]{\mathcal S}[/math].
The problem of finding the maximum number of node-disjoint [math]{\mathcal S}[/math]-paths is equivalent to the problem of finding the maximum number of internally node-disjoint [math]S[/math]-paths. A min-max formula was given by Mader [1], see Mader's S-paths theorem. Lovász [2] showed that the problem can be reduced to matroid matching, which implies a polynomial algorithm. Combinatorial polynomial-time algorithms were given in [3] and [4].
References
- ↑ W. Mader, Über die Maximalzahl kreuzungsfreier H-Wege, Arch. Math. 31 (1978), 387-402, DOI link
- ↑ L. Lovász, Matroid matching and some applications, DOI 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
