Abstract:

In this talk, I will present a subexponential parameterized algorithm for finding k vertex-disjoint paths of minimal total length between given terminal pairs in a planar graph parameterized by the number of edges in the solution. The algorithm generalizes to different settings such as edge-weighted graphs and/or directed graphs. We complement our algorithm by an almost matching ETH-based lower bound.

This is joint work with Petr Golovach and Fedor Fomin.