An approach to the k paths problem
Allen Cypher · 1980
The k paths problem asks whether it is possible to find k edge-disjoint paths joining k given pairs of vertices in a graph. We show that this problem can be solved in polynomial time for k≤5 if the input graph is k+2 -connected.