Fleszar, Krzysztof ;
Mnich, Matthias ;
Spoerhase, Joachim
New Algorithms for Maximum Disjoint Paths Based on TreeLikeness
Abstract
We study the classical NPhard problems of finding maximumsize subsets from given sets of k terminal pairs that can be routed via edgedisjoint paths (MaxEDP) or nodedisjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/NDP is currently not well understood; the best known lower bound is Omega(log^{1/2  varepsilon} n), assuming NP not subseteq ZPTIME(n^{poly log n}). This constitutes a significant gap to the best known approximation upper bound of O(n^1/2) due to Chekuri et al. (2006) and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica, 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 above fundamental results. 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.
 For MaxEDP, we give an O(r^0.5 log^1.5 kr)approximation algorithm. As r<=n, up to logarithmic factors, our result strengthens the best known ratio O(n^0.5) due to Chekuri et al.
 Further, we show how to route Omega(opt) pairs with congestion O(log(kr)/log log(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson.
 For MaxNDP, we give an algorithm that gives the optimal answer in time (k+r)^O(r)n. This is a substantial improvement on the run time of 2^kr^O(r)n, which can be obtained via an algorithm by Scheffler.
We complement these positive results by proving that MaxEDP is NPhard even for r=1, and MaxNDP is W[1]hard for parameter r. This shows that neither problem is fixedparameter tractable in r unless FPT = W[1] and that our approximability results are relevant even for very small constant values of r.
BibTeX  Entry
@InProceedings{fleszar_et_al:LIPIcs:2016:6354,
author = {Krzysztof Fleszar and Matthias Mnich and Joachim Spoerhase},
title = {{New Algorithms for Maximum Disjoint Paths Based on TreeLikeness}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {42:142:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6354},
URN = {urn:nbn:de:0030drops63542},
doi = {10.4230/LIPIcs.ESA.2016.42},
annote = {Keywords: disjoint paths, approximation algorithms, feedback vertex set}
}
2016
Keywords: 

disjoint paths, approximation algorithms, feedback vertex set 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 