Source author record

Philipp Klaus Krause

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Irrelevant Vertices for the Planar Disjoint Paths Problem

The 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 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 give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves $g(k)=O(k^{3/2}\cdot 2^{k}).$ Our bound is radically better than the bounds known for general graphs.

preprint2010arXiv

A lower bound for the tree-width of planar graphs with vital linkages

The disjoint paths problem asks, given an graph G and k + 1 pairs of terminals (s_0,t_0), ...,(s_k,t_k), whether there are k+1 pairwise disjoint paths P_0, ...,P_k, such that P_i connects s_i to t_i. Robertson and Seymour have proven that the problem can be solved in polynomial time if k is fixed. Nevertheless, the constants involved are huge, and the algorithm is far from implementable. The algorithm uses a bound on the tree-width of graphs with vital linkages, and deletion of irrelevant vertices. We give single exponential lower bounds both for the tree-width of planar graphs with vital linkages, and for the size of the grid necessary for finding irrelevant vertices.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.