Yusuke Kobayashi and Christian Sommer
Discrete Optimization, Volume 7, Issue 4
For a graph and a collection of vertex pairs, the disjoint paths problem is to find vertex-disjoint paths for each pair of nodes. In the corresponding optimization problem, the shortest disjoint path problem, the vertex-disjoint paths have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: min-sum), and minimizing the length of the longest path (min-max).
min-sum: We extend recent results by Colin de Verdière and Schrijver to prove that for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.
min-max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We also close the gap between easy and hard instances by proving that the problem is weakly NP-hard for graphs with tree-width at least 3.
@article{KS10,
author = {Yusuke Kobayashi and Christian Sommer},
title = {On Shortest Disjoint Paths in Planar Graphs},
journal = {Discrete Optimization},
volume = {7},
number = {4},
year = {2010},
pages = {234--245},
url = {http://dx.doi.org/10.1016/j.disopt.2010.05.002},
doi = {10.1016/j.disopt.2010.05.002},
note = {Announced at ISAAC 2009}
}
Official version
Local version (184.2 KB)
Slides (269.9 KB)
Different from the single source shortest path problem, the single pair shortest path problem (find the shortest path between two nodes), and the multiple pairs shortest path problem, the shortest disjoint paths problem cannot be solved by just running Dijkstra's algorithm or its bidirectional version. A k shortest path algorithm is not sufficient either. The difficulty of the shortest disjoint paths problem comes from the difficulty of finding node disjoint paths (even without length restrictions). The disjoint paths problem for a fixed number of terminals in an undirected graph can be solved using a polynomial-time algorithm that relies on graph minor theory. In each step, the algorithm finds a node that can be removed without altering the solution, for which crude connectivity is sufficient. A straightforward generalization of this algorithm to the weighted version would mean to find a vertex whose removal changes neither the connectivity of the terminals nor the optimality of the solution. Consequently, much less is known for the weighted version of the disjoint paths problem.
Home → Publications → On Shortest Disjoint Paths in Planar Graphs