# Mitarbeiterseminar Logik in der Informatik

Freitag, 2. Dezember 2005, 11:15 Uhr

RUD 25, Raum 4.410
## DAG-Width and Parity Games

Stephan Kreutzer

Humboldt-Universität zu Berlin

Tree-width is a well-known metric on undirected graphs that measures
how tree-like a graph is and gives a notion of graph decomposition
that proves useful in algorithm development. Tree-width is
characterised by a game known as the cops-and-robber game where a
number of cops chase a robber on the graph. We consider the natural
adaptation of this game to directed graphs and show that monotone
strategies in the game yield a measure with an associated notion of
graph decomposition that can be seen to describe how close a
directed graph is to a directed acyclic graph (DAG). This promises
to be useful in developing algorithms on directed graphs. In
particular, we show that the problem of determining the winner of a
parity game is solvable in polynomial time on graphs of bounded
DAG-width. We also consider the relationship between DAG-width and
other measures of such as entanglement and directed tree-width.
One consequence we obtain is that certain NP-complete
problems such as Hamiltonicity and disjoint paths are
polynomial-time computable on graphs of bounded DAG-width.