New algorithms for maximum disjoint paths based on tree-likeness

摘要

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 paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is 2(Omega(root log n)), assuming NP not subset of DTIME(n(O(log n))). This constitutes a significant gap to the best known approximation upper bound of O(root 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 O(1)-approximation when edges or nodes) may be used by O(log n/log log n) 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: