The Relations between Directed Tree-width & Co

We consider the cops and robber games characterising DAG-width and directed tree-width (up to a constant factor). For DAG-width games, it is an open question whether the robber-monotonicity cost (the difference between the minimal numbers of cops capturing the robber in the general and in the monotone case) can be bounded by any function. Examples show that this function (if it exists) is at least f ( k ) > 4 k /3 [Kreutzer, Ordyniak '08]. We approach a solution by defining weak monotonicity and showing that if k cops win weakly monotonically, then O ( k 2 ) cops win monotonically. It follows that bounded Kelly-width implies bounded DAG-width, which has been open since the definition of Kelly-width [Hunter, Kreutzer '08]. The game also corresponds to a tree decomposition whose properties are nicer than those of DAG-decompositions. For directed tree-width games we show that, unexpectedly, the cop-monotonicity cost (the cops never revisit any vertex) is not bounded by any function. This also separates directed tree-width from D -width defined in [Safari '05], refuting a conjecture made there. In the second part of the talk we consider the relative strength of directed width measures: does the boundedness of the values of one measure imply that that the values of the other measure are bounded? So far only some results separating directed width-measures are known. We give an almost complete picture of this relation.

Authors

• Roman Rabinovich

Keywords

No keywords are indexed for this paper.