[Back]

V. Engelmann, S. Ordyniak, S. Kreutzer:
"Directed elimination games";
Discrete Applied Mathematics, 199 (2016), 187 - 198.

While tools from structural graph theory such as tree- or path-width have proved to be
highly successful in coping with computational intractability on undirected graphs, corresponding
width measures for directed graphs have not yet fulfilled their promise for broad
algorithmic applications on directed graphs. One reason for this is that in most existing
digraph width measures the class of acyclic digraphs has small width which immediately
implies hardness of problems such as computing directed dominating sets.
Fernau and Meister (2014) introduce the concept of elimination width and a corresponding
graph searching game which overcomes this problem with acyclic digraphs. In
their paper, the focus was on structural characterizations of classes of digraphs of bounded
elimination width.
In this paper we study elimination width from an algorithmic and graph searching perspective.
We analyse variations of the elimination width game and show that this leads
to width measures on which the directed dominating set problem and some variants of it
become tractable.

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