Abstract
In the NodeDisjoint Paths (NDP) problem, the input is an undirected nvertex graph G, and a collection {(s_1,t_1),...,(s_k,t_k)} of pairs of vertices called demand pairs. The goal is to route the largest possible number of the demand pairs (s_i,t_i), by selecting a path connecting each such pair, so that the resulting paths are nodedisjoint. NDP is one of the most basic and extensively studied routing problems. Unfortunately, its approximability is far from being wellunderstood: the best current upper bound of O(sqrt(n)) is achieved via a simple greedy algorithm, while the best current lower bound on its approximability is Omega(log^{1/2\delta}(n)) for any constant delta. Even for seemingly simpler special cases, such as planar graphs, and even grid graphs, no better approximation algorithms are currently known. A major reason for this impasse is that the standard technique for designing approximation algorithms for routing problems is LProunding of the standard multicommodity flow relaxation of the problem, whose integrality gap for NDP is Omega(sqrt(n)) even on grid graphs.
Our main result is an O(n^{1/4} * log(n))approximation algorithm for NDP on grids. We distinguish between demand pairs with both vertices close to the grid boundary, and pairs where at least one of the two vertices is far from the grid boundary. Our algorithm shows that when all demand pairs are of the latter type, the integrality gap of the multicommodity flow LPrelaxation is at most O(n^{1/4} * log(n)), and we deal with demand pairs of the former type by other methods. We complement our upper bounds by proving that NDP is APXhard on grid graphs.
BibTeX  Entry
@InProceedings{chuzhoy_et_al:LIPIcs:2015:5303,
author = {Julia Chuzhoy and David H. K. Kim},
title = {{On Approximating NodeDisjoint Paths in Grids}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {187211},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5303},
URN = {urn:nbn:de:0030drops53032},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.187},
annote = {Keywords: Nodedisjoint paths, approximation algorithms, routing and layout}
}
Keywords: 

Nodedisjoint paths, approximation algorithms, routing and layout 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) 
Issue Date: 

2015 
Date of publication: 

13.08.2015 