Maximilian Gorsky, The Disjoint Paths Problem lies in the Oort cloud of algorithms

In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint Paths Problem, Minor Checking, and more generally, the Folio-Problem. We in fact prove something even stronger: It turns out that it is not in fact the number of terminals (or more generally vertices) that matters in these problems, but rather their structure within the graph. Concretely, we show that the Vital Linkage Function is single-exponential only in the bidimensionality of the terminals, whilst the number of terminals contributes only polynomially. A direct consequence of this is an algorithm for the k-Disjoint Paths Problem running in $f(k)n^2$-time, where f(k) is singly exponential in k and doubly exponential in the bidimensionality of k. This derives directly from an algorithm for the Folio-problem we give that has an analogous runtime. Notably these are the first algorithms for these problems in which the function f is explicit. In particular, we give the first explicit bounds for the Vital Linkage Function.

Joint work with Dario Cavallaro, Stephan Kreutzer, Dimitrios Thilikos, and Sebastian Wiederrecht.