New algorithms for maximum disjoint paths based on tree-likeness
Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase · Mathematical Programming · 2017
We study the classical $${\mathsf {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 paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is $${2^{\varOmega (\sqrt{\log n})}}$$ , assuming $${\mathsf {NP} ot \subseteq \mathsf {DTIME}(n^{\mathcal {O}(\log n)})}$$ . This constitutes a significant gap to the best known approximation upper bound of $${\mathcal {O}(\sqrt{n})}$$ due to Chekuri et al. (Theory Comput 2:137–146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365–374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an $${\mathcal {O}(1)}$$ -approximation when edges (or nodes) may be used by $${\mathcal {O}\left( \log n/\log \log n\right) }$$ paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results: We complement these positive results by proving that MaxEDP is $${\mathsf {NP}}$$ -hard even for $${r=1}$$ , and MaxNDP is $${\mathsf {W}[1]}$$ -hard when r is the parameter. This shows that neither problem is fixed-parameter tractable in r unless $${\mathsf {FPT}= \mathsf {W}[1]}$$ and that our approximability results are relevant even for very small constant values of r.