Title: Cops and Robber Games and Decompositions of Digraphs

Abstract:
The notion of tree-width of graphs and associated decompositions have
found numerous applications in the design of efficient algorithms,
aside from the fundamental role of tree-width in Robertson and
Seymour's theory of graph minors and their proof of the graph minor theorem. 
A particularly elegant characterisation of tree-width is in terms of
certain two player games called Cops and Robber games. Essentially,
the number of cops required to catch a fugitive on a graph is
equivalent to its tree-width. 

More recently, attempts have been made to generalise the notion of
tree-width from undirected to directed graphs and to develop a
decomposition theory consistent with standard notions of
connectivity in digraphs. Again, Cops and Robber games provide an
adequate framework to study these width-measures.

In this talk, we will present various notions of Cops and Robber games
on digraphs. A key issue will be monotonicity of these games - the
problem whether the cops may need to retreat in their pursuit of the
robber. We will also present some of the width measures and
decompositions for digraphs introduced so far and state the main
challenges and open problems in this area.