Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

subexponential algorithm on undirected planar graphs by showing that
k-Dominating Set
is solvable in time 2^O(sqrt{k}) n^O(1), where n is the input size.
This result triggered an extensive study of parameterized problems on
planar
and more general classes of sparse graphs and culminated in the
creation of Bidimensionality Theory by Demaine et al.[J. ACM 2005].
The theory utilizes deep theorems from Graph Minor Theory of Robertson
and Seymour, and provides a simple criteria for
checking whether a parameterized problem is solvable in subexponential
time on sparse graphs.

While bidimensionality theory is an algorithmic framework on
undirected graphs, it remains unclear how to apply it to problems
on directed graphs. The main reason is that Graph Minor Theory for
directed graphs is still in a nascent stage and there are no
suitable obstruction theorems so far. Even the analogue of treewidth
for directed graphs is not unique and several alternative
definitions have been proposed.

In this talk we make the first step beyond bidimensionality by
obtaining subexponential time algorithms for problems on directed
graphs.
We develop different methods to achieve subexponential time
parameterized algorithms for problems on sparse directed graphs.
We exemplify our approaches with two well studied problems:
k-Leaf Out-Branching, which is to find an oriented spanning tree
with at least k leaves, and
k-Internal Out-Branching---a generalization of the Directed
Hamiltonian Path problem---which is to find an oriented spanning tree
with at least k
internal vertices.
Finally, we observe that for any c>0, the k-Directed Path problem
is solvable in time O((1+c)^k n^f(c)), where f is some function of c.

Our methods are based on non-trivial combinations of obstruction
theorems for undirected graphs, kernelization, problem specific
combinatorial structures
and a layering technique similar to the one employed by Baker to
obtain PTAS for planar graphs.

This talk is based on joint work with Fedor V. Fomin, Daniel
Lokshtanov, Venkatesh Raman, and Saket Saurabh.