# Irrelevant Vertices for the Planar Disjoint Paths Problem

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Pré-publication, Document de travail
Journal Version of the paper (presented at ICALP 2011, titled "Tight Bounds for Linkages in Plana.. 2013
Domaine :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904538
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 16:17:21
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

### Identifiants

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

### Citation

Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabhh, et al.. Irrelevant Vertices for the Planar Disjoint Paths Problem. Journal Version of the paper (presented at ICALP 2011, titled "Tight Bounds for Linkages in Plana.. 2013. 〈lirmm-00904538〉

### Métriques

Consultations de la notice