Irrelevant Vertices for the Planar Disjoint Paths Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Preprints, Working Papers, ... Year : 2013

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.

Dates and versions

lirmm-00904538 , version 1 (14-11-2013)

Identifiers

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

Cite

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⟩
276 View
0 Download

Altmetric

Share

More