TY - GEN

T1 - Tight bounds for linkages in planar graphs

AU - Adler, Isolde

AU - Kolliopoulos, Stavros G.

AU - Krause, Philipp Klaus

AU - Lokshtanov, Daniel

AU - Saurabh, Saket

AU - Thilikos, Dimitrios

PY - 2011

Y1 - 2011

N2 - The Disjoint-Paths Problem asks, given a graph G and a set of pairs of terminals (s 1,t 1),...,(s k ,t k ), whether there is a collection of k pairwise vertex-disjoint paths linking s i and t i , for i = 1,...,k. In their f(k)•n 3 algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g(k) there is an "irrelevant" vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem, whose - very technical - proof gives a function g(k) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we prove this result for planar graphs achieving g(k) = 2 O(k). Our bound is radically better than the bounds known for general graphs. Moreover, our proof is new and self-contained, and it strongly exploits the combinatorial properties of planar graphs. We also prove that our result is optimal, in the sense that the function g(k) cannot become better than exponential. Our results suggest that any algorithm for the Disjoint-Paths Problem that runs in time better than will probably require drastically different ideas from those in the irrelevant vertex technique.

AB - The Disjoint-Paths Problem asks, given a graph G and a set of pairs of terminals (s 1,t 1),...,(s k ,t k ), whether there is a collection of k pairwise vertex-disjoint paths linking s i and t i , for i = 1,...,k. In their f(k)•n 3 algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g(k) there is an "irrelevant" vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem, whose - very technical - proof gives a function g(k) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we prove this result for planar graphs achieving g(k) = 2 O(k). Our bound is radically better than the bounds known for general graphs. Moreover, our proof is new and self-contained, and it strongly exploits the combinatorial properties of planar graphs. We also prove that our result is optimal, in the sense that the function g(k) cannot become better than exponential. Our results suggest that any algorithm for the Disjoint-Paths Problem that runs in time better than will probably require drastically different ideas from those in the irrelevant vertex technique.

UR - http://www.scopus.com/inward/record.url?scp=79959986071&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959986071&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22006-7_10

DO - 10.1007/978-3-642-22006-7_10

M3 - Conference contribution

AN - SCOPUS:79959986071

SN - 9783642220050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 110

EP - 121

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011

Y2 - 4 July 2011 through 8 July 2011

ER -