Disjoint S-paths

Let $$G=(V,E)$$ be an undirected graph, and $$S \subseteq V$$ a subset of nodes. An $$S$$ -path is a path between two distinct nodes in $$S$$ that does not contain any other node from $$S$$ . The problem of finding the maximum number of node-disjoint $$S$$ -paths can be reduced to maximum matching.

If $${\mathcal S}$$ is a collection of disjoint subsets of $$V$$ , then a path is called an $${\mathcal S}$$ -path if its endnodes are in different members of $${\mathcal S}$$ .

The problem of finding the maximum number of node-disjoint $${\mathcal S}$$ -paths is equivalent to the problem of finding the maximum number of internally node-disjoint $$S$$ -paths. A min-max formula was given by Mader , see Mader's S-paths theorem. Lovász showed that the problem can be reduced to matroid matching, which implies a polynomial algorithm. Combinatorial polynomial-time algorithms were given in and .