Stephan Kreutzer, Disjoint Paths in Graphs and Digraphs

One of the important algorithmic consequences of Robertson and Seymour’s Graph Minor Project is their proof that the k-Vertex-Disjoint Paths problem is fixed-parameter tractable on the class of all undirected graphs, that is, solvable in time $f(k) \cdot n^c$, for some function $f$ and constant $c$.

For directed graphs the problem is significantly harder: the k-Disjoint-Paths problem it is NP-complete already for $k=2$. While this indicates that the Directed-k-Disjoint Paths problem is unlikely to be fixed-parameter tractable in general, it is nevertheless interesting to investigate which of the techniques used to solve the problem on undirected graphs fail for digraphs and why and whether some of them can be made to work in a more restricted setting.

In this talk I will speak about recent results on disjoint directed paths including positive solutions for special graph classes such as Eulerian digraphs but also recently obtained further hardness results.