Graph Searching Games and Width Measures for Directed Graphs
Abstract
In cops and robber games a number of cops tries to capture a robber in a graph. A variant of
these games on undirected graphs characterises tree width by the least number of cops needed to
win. We consider cops and robber games on digraphs and width measures (such as DAG-width,
directed tree width or D-width) corresponding to them. All of them generalise tree width and
the game characterising it.
For the DAG-width game we prove that the problem to decide the minimal number of cops
required to capture the robber (which is the same as deciding DAG-width), is PSPACE-complete,
in contrast to most other similar games. We also show that the cop-monotonicity cost for directed
tree width games cannot be bounded by any function. As a consequence, D-width is not bounded
in directed tree width, refuting a conjecture by Safari.
A large number of directed width measures generalising tree width has been proposed in the
literature. However, only very little was known about the relation between them, in particular
about whether classes of digraphs of bounded width in one measure have bounded width in
another. In this paper we establish an almost complete order among the most prominent width
measures with respect to mutual boundedness.