Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman & Saket Saurabh
In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, $k$-Leaf Out-Branching, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k}...