Digraph Decompositions and Monotonicity in Digraph Searching

Stephan Kreutzer, Sebastian Ordyniak

Abstract

This paper investigates the structural and algorithmic properties of directed graphs (digraphs) through the lens of searching games. It resolves long-standing questions regarding the monotonicity of these games and demonstrates that standard directed width measures, such as DAG-width, fail to simplify many NP-complete problems. These results highlight a fundamental divergence between directed and undirected graph theory, suggesting that the algorithmic utility of tree-width does not easily translate to the directed setting.

Introduction

In graph theory, searching games provide a powerful framework for understanding structural complexity. A typical game involves a set of searchers (cops) attempting to capture a fugitive (robber) within a network. The minimum number of cops required to guarantee a catch defines a "width" measure of the graph. For undirected graphs, this is intrinsically linked to tree-width, a concept that has revolutionized algorithmic research by making many NP-complete problems tractable on graphs with low width.

However, directed graphs—where edges possess a specific orientation—present a significantly more complex landscape. While researchers have proposed directed analogues like DAG-width and Kelly-width, two critical questions remained: the property of monotonicity in searching strategies and the actual algorithmic utility of these measures. This paper by Stephan Kreutzer and Sebastian Ordyniak provides definitive, albeit pessimistic, answers to both.

The Monotonicity Problem

A searching strategy is considered "monotone" if the cops can capture the robber without ever allowing them to re-enter an area that has already been cleared. In undirected graphs, if $k$ cops can catch a robber, they can always do so monotonically. In the directed case, the authors prove this is not a universal truth.

Illustration of component decomposition in directed searching games.

By constructing specific families of digraphs, the authors demonstrate that directionality allows a robber to exploit "one-way streets." In certain configurations, the only way for cops to advance is to temporarily leave a "back door" open. A clever robber can use these openings to re-occupy cleared territory, forcing a non-monotone strategy. Specifically, they resolve cases involving visible/fast and invisible/lazy robbers, showing a significant gap where a monotone search requires nearly $4/3$ times as many cops as a non-monotone one.

Algorithmic Complexity and Directed Width

The second major contribution of the paper concerns the "Almost Acyclic" illusion. A graph with low DAG-width is structurally close to a Directed Acyclic Graph (DAG), which one might assume makes it computationally easy to navigate. The authors use gadget-based reductions to shatter this assumption.

A gadget construction demonstrating how complex logic can be encoded in low-width digraphs.

By mapping classic NP-complete problems like 3-SAT onto digraphs with very low width, they prove that the internal logic of these graphs remains complex enough to encode difficult puzzles. Their results show that several key problems remain NP-complete even under restrictive conditions:

  • Minimum Equivalent Subgraph: NP-complete for DAG-width < 4.
  • Feedback Vertex Set: NP-complete for DAG-width ≤ 4.
  • Graph Grundy Numbering & Kernel: NP-complete for DAG-width 2.

Conclusion

The findings of Kreutzer and Ordyniak suggest a "Success Gap" in graph theory. While tree-width is a silver bullet for undirected graphs, directed graph theory is fundamentally more resistant to such universal solutions. The paper serves as a call to action for the community to develop more robust directed width measures that can capture the same algorithmic magic as their undirected counterparts. Until then, the search for a directed decomposition that truly simplifies NP-complete problems continues.

Summary updated

BibTeX
@article{kreutzer2011digraph,
  author = {Stephan Kreutzer and Sebastian Ordyniak},
  title = {{Digraph Decompositions and Monotonicity in Digraph Searching}},
  journal = {Theoretical Computer Science},
  year = {2011},
  doi = {10.1016/j.tcs.2011.05.003},
}
Figure