Approximation Algorithms and Hardness of Routing on Disjoint Path

In the classical node-disjoint paths problem, one is given as input an n-vertex graph G and a collection M = {(s1,t1 ),...,(sk,tk)} of pairs of vertices of G called source-destination or demand pairs, and the goal is to find a maximum-cardinality set of pairwise vertex-disjoint paths connecting the demand pairs. While the node-disjoint paths problem is one of the most basic routing problems, there has been a wide gap in our understanding of its approximability status. Currently, the best upper bound of O(√n) is achieved by a simple, greedy algorithm, while until very recently, the best known hardness of approximation result was a O(log1/2--delta n) lower bound for any constant delta, under standard complexity assumptions. Even for special cases of the problem, including when the input graph G is constrained to be planar, and surprisingly, even when G is a square grid, no better upper bound was known, while only NP-hardness was known on the negative side.;This thesis studies the approximability of the node-disjoint paths problem and three of its special cases. The first part of the thesis presents approximation algorithms for the special cases of the problem. In the first chapter, we investigate when the input graph is constrained to be a square grid. We show an O(n1/4)-approximation algorithm for this case and extend the approximation algorithm to show that the same upper bound holds for the closely related edge-disjoint paths problem in wall graphs.;In the second chapter, we focus on two cases of node-disjoint paths when the input graph G is planar. In the first case, we assume that we are given a planar graph G embedded into a disc, where all of the terminals participating in the demand pairs lie on the boundary of the disc. In the second case, we assume that we are given a cylinder obtained by removing two disjoint, open discs from it. We assume that G can be embedded into the cylinder such that all source terminals lie on the boundary of one of the discs and all destination terminals on the boundary of the other. We present an O(log k)-approximation algorithm for both problems of routing node-disjoint paths on a disc and a cylinder.;The third chapter of the thesis presents an improved inapproximability result for the node-disjoint paths problem. We show that the problem is 2O(√log n)-hard to approximate, unless all problems in NP have deterministic, quasi-polynomial time algorithms. The result holds even when the underlying graph is a sub-graph of a grid with all sources of the demand pairs lying on the boundary of the outer face.