Directed Path-width and Monotonicity in Digraph Searching

Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achieved using the mixed-search technique developed by Bienstock and Seymour. A search is called monotone, in which the robber's territory never increases. We show that there is a mixed-search of D with k cops if and only if there is a monotone mixed-search with k cops. For our cops-and-robber game we get a slightly weaker result: the monotonicity can be guaranteed by using at most one extra cop. On leave from Bolyai Institute, University of Szeged, Hungary. This research has been supported by a Marie Curie Fellowship of the European Community under contract number HPMF-CT-2002-01868 and by OTKA Grants F.030737 and T.34475.