New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness

Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase

We study the classical NP-hard problems of finding maximum-size subsets from given sets of $k$ terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint p…