Colloquium Details
On the planar disjoint paths problem
| Author: | Isolde Adler University of Frankfurt |
|---|---|
| Date: | April 21, 2011 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
In the course of their proof of Wagner's Conjecture, Robertson and Seymour developed an algorithm for the disjoint paths problem (DPP), which is probably one of the most famous polynomial time algorithms in theoretical computer science. The DPP asks, given graph G with k pairs (s_1,t_1), ..., (s_k,t_k) of vertices, whether there exist k pairwise vertex- disjoint paths P_1, ..., P_k in G such that each P_i connects s_i to t_i. Their algorithm runs in time f(k)*|G|^3, where f is a computable function. Nevertheless, the algorithm is mainly of theoretical interest, because the parameter dependence f is gigantic (in the proof, the funcion f is a huge tower of iterated exponentials, and the precise order of f was not determined). The main source of the huge parameter dependence is the so-called "irrelevant vertex technique" (introduced in Robertson and Seymour's - very technical - paper "Graph Minors XXII").
In my talk I will present a new and much simpler proof for finding irrelevant vertices in planar graphs. This improves the parameter dependence to double-exponential. Moreover, our results suggest that for any further improvement, methods quite different from the irrelevant vertex technique will be required.
This is joint work with Stavros Kolliopoulos, Philipp Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios Thilikos.
Biography
Dr. Isolde Adler is currently a Junior Professor at Goethe University, Frankfurt, Germany. Her research interests include graph and hypergraph theory, algorithms and complexity, as well as logic and databases. She studied mathematics in Goettingen, Thessaloniki and Freiburg, sponsored by the German National Academic Foundation. In 2006 she received her PhD from the University of Freiburg for her thesis on hypergraph decompositions and algorithmic applications. As a postdoc, she had positions at Humboldt University Berlin and at the University of Bergen in Norway. In 2008 she was a visiting professor at Humboldt University Berlin for six months, representing Prof. Grohe in the Logic-in-Computer-Science group.