Chuzhoy, Julia ;
Kim, David H. K. ;
Nimavat, Rachit
Improved Approximation for NodeDisjoint Paths in Grids with Sources on the Boundary
Abstract
We study the classical NodeDisjoint Paths (NDP) problem: given an undirected nvertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called sourcedestination, or demand pairs, find a maximumcardinality set {P} of mutually nodedisjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy O(sqrt{n})approximation algorithm. Until recently, the best negative result was an Omega(log^{1/2epsilon}n)hardness of approximation, for any fixed epsilon, under standard complexity assumptions.
A special case of the problem, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for this special case achieves an O~(n^{1/4})approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor 2^{Omega(sqrt{log n})}, even if the underlying graph is a subgraph of a grid, and all source vertices lie on the grid boundary. In a very recent followup work, the authors further show that NDP in grid graphs is hard to approximate to within factor Omega(2^{log^{1epsilon}n}) for any constant epsilon under standard complexity assumptions, and to within factor n^{Omega(1/(log log n)^2)} under randomized ETH.
In this paper we study the NDP problem in grid graphs, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized 2^{O(sqrt{log n}* log log n)}approximation algorithm for this problem. Our result in a sense complements the 2^{Omega(sqrt{log n})}hardness of approximation for subgraphs of grids with sources lying on the grid boundary, and should be contrasted with the abovementioned almost polynomial hardness of approximation of NDP in grid graphs (where the sources and the destinations may lie anywhere in the grid).
Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an Omega(sqrt n) integrality gap, even in grid graphs, with all source and destination vertices lying on the grid boundary. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods.
BibTeX  Entry
@InProceedings{chuzhoy_et_al:LIPIcs:2018:9042,
author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat},
title = {{Improved Approximation for NodeDisjoint Paths in Grids with Sources on the Boundary}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {38:138:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9042},
URN = {urn:nbn:de:0030drops90423},
doi = {10.4230/LIPIcs.ICALP.2018.38},
annote = {Keywords: Nodedisjoint paths, approximation algorithms, routing and layout}
}
04.07.2018
Keywords: 

Nodedisjoint paths, approximation algorithms, routing and layout 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 