Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Irrelevant Vertices for the Planar Disjoint Paths Problem

Abstract : The {\sc Disjoint Paths Problem} asks, given a graph $G$ and a set of pairs of terminals $(s_{1},t_{1}),\ldots,(s_{k},t_{k})$, whether there is a collection of $k$ pairwise vertex-disjoint paths linking $s_{i}$ and $t_{i}$, for $i=1,\ldots,k.$ In their $f(k)\cdot n^{3}$ algorithm for this problem, Robertson and Seymour introduced the {\sl 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 {\sl 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)=26\cdot k^{3/2}\cdot 2^{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.
Complete list of metadata
Contributor : Dimitrios Thilikos <>
Submitted on : Thursday, November 14, 2013 - 4:17:21 PM
Last modification on : Thursday, November 26, 2020 - 4:00:02 PM

Links full text


  • HAL Id : lirmm-00904538, version 1
  • ARXIV : 1310.2378



Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabhh, et al.. Irrelevant Vertices for the Planar Disjoint Paths Problem. 2013. ⟨lirmm-00904538⟩



Record views