[Back]

R. Ganian, P. Hlinený, J. Kneis, A. Langer, J. Obdrzalek, P. Rossmanith:
"Digraph Width Measures in Parameterized Algorithmics";
Discrete Applied Mathematics, 168 (2014), 88 - 107.

In contrast to undirected width measures such as tree-width, which have provided many
important algorithmic applications, analogous measures for digraphs such as directed
tree-width or DAG-width do not seem so successful. Several recent papers have given
some evidence on the negative side. We confirm and consolidate this overall picture by
thoroughly and exhaustively studying the complexity of a range of directed problems with
respect to various parameters, and by showing that they often remain NP-hard even on
graph classes that are restricted very beyond having small DAG-width. On the positive side,
it turns out that clique-width (of digraphs) performs much better on virtually all considered
problems, from the parameterized complexity point of view.

http://dx.doi.org/10.1016/j.dam.2013.10.038

Project Head Stefan Szeider:
Exploiting New Types of Structure for Fixed Parameter Tractability

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems