The Parameterized Complexity of Oriented Colouring

Robert Ganian

TL;DR

This paper investigates the computational complexity of "oriented coloring" on directed graphs, a problem related to but distinct from standard graph coloring. The authors show that while the problem remains hard even for restricted graph classes, it becomes tractable when parameterized by certain "undirected" structural properties like tree-width and rank-width. They provide new complexity results and a novel algorithm for this problem, bridging the gap between directed graph problems and established undirected graph parameters.

What Problem Does This Paper Address?

Graph coloring, a fundamental problem in computer science, involves assigning colors to vertices such that no two adjacent vertices share the same color. The "oriented coloring" problem is a directed graph analogue: instead of just checking for adjacency, we consider the direction of edges. Specifically, it asks if a directed graph (digraph) can be mapped to a tournament (a specific type of directed graph) on $k$ vertices such that if there's an arc from vertex $u$ to vertex $v$ in the original digraph, then the image of $u$ maps to a vertex that has an arc to the image of $v$ in the tournament.

While standard graph coloring is NP-hard, it becomes much easier on restricted graph classes like trees. However, oriented coloring remains NP-hard even on very simple directed graph classes like directed acyclic graphs (DAGs). This makes it challenging to find efficient algorithms. The paper tackles this by exploring "parameterized complexity," where we analyze how the problem's difficulty changes with specific structural parameters of the graph. The key challenge is that standard directed graph parameters don't offer much help for oriented coloring, and the problem doesn't directly translate to undirected graph parameters. This paper investigates using undirected graph parameters (like tree-width and rank-width) to analyze oriented coloring, effectively "forgetting" the arc orientations for the purpose of measuring these parameters.

Methods

The paper employs techniques from parameterized complexity theory. The core idea is to leverage established structural parameters of undirected graphs – specifically, tree-width and rank-width – to bound the complexity of oriented coloring on directed graphs.

  • Rank-width: The authors establish a new complexity result for oriented coloring on digraphs with bounded undirected rank-width. They prove that the problem is DET-hard even in this restricted setting. DET-hardness implies a high level of computational difficulty, comparable to general graph isomorphism. This is achieved through a reduction from the problem of tournament isomorphism.
  • Tree-width: For digraphs with bounded undirected tree-width, the paper presents a new FPT (Fixed-Parameter Tractable) algorithm. This means that for a fixed tree-width $t$, the problem can be solved in time that is polynomial in the graph size, but potentially exponential in $t$. The algorithm relies on a crucial intermediate result: they show that the bi-rank-width of a digraph is bounded by a function of its tree-width (specifically, $2 \cdot (\text{tree-width} + 1)$). This connection allows them to utilize existing FPT algorithms for bi-rank-width. The proof of this tree-width to bi-rank-width bound involves a careful transformation of tree decompositions into bi-rank decompositions.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity results and algorithmic design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Undirected parameters for directed problems: A significant insight is that established undirected graph parameters (tree-width, rank-width) can be effectively used to analyze the complexity of directed graph problems like oriented coloring, even though the parameters themselves ignore the directionality of edges. This opens up new avenues for studying directed graph problems.
  • DET-hardness for rank-width: The proof that oriented coloring is DET-hard on digraphs of bounded rank-width is a strong negative result, indicating that even with this structural restriction, the problem remains computationally challenging.
  • FPT algorithm for tree-width: The development of an FPT algorithm for oriented coloring on digraphs of bounded tree-width is a key positive result. This is the first such algorithm for this problem based on an undirected width parameter.
  • Tree-width bounds bi-rank-width: The theorem showing that tree-width bounds bi-rank-width is an important theoretical contribution. This connection is not immediately obvious and was previously unknown, enabling the application of existing bi-rank-width algorithms to tree-width bounded graphs.

Key Results

  • DET-hard: Computing the oriented chromatic number of digraphs is DET-hard even when restricted to digraphs of bounded undirected rank-width.
  • FPT algorithm: An FPT algorithm is presented for computing the oriented chromatic number on digraphs of bounded undirected tree-width.
  • Tree-width bounds bi-rank-width: The bi-rank-width of a digraph with tree-width $t$ is bounded by $2 \cdot (t + 1)$. This result is crucial for enabling the FPT algorithm.

Limitations and Future Work

  • Limitations: The paper acknowledges that while the FPT algorithm for tree-width is a significant step, the runtime complexity is still quite high, especially due to the dependence on the bound $b(t)$ (related to the oriented chromatic number itself). The DET-hard result for rank-width highlights the inherent difficulty of the problem.
  • Future Work: The authors suggest exploring undirected width measures for other directed graph problems that don't directly translate to undirected graphs. They also propose investigating the complexity of oriented coloring on digraphs of bounded bi-rank-width, and if it proves hard, searching for new directed measures that can handle such problems.

Summary updated

Abstract

The oriented colouring problem is intuitive and related to undirected colouring, yet remains NP-hard even on digraph classes with bounded traditional directed width measures. Recently we have also proved that it remains NP-hard in otherwise severely restricted digraph classes. However, unlike most other problems on directed graphs, the oriented colouring problem is not directly transferable to undirected graphs. In the article we look at the parameterized complexity of computing the oriented colouring of digraphs with bounded undirected width parameters, whereas the parameters ``forget'' about the orientations of arcs and treat them as edges. Specifically, we provide new complexity results for computing oriented colouring on digraphs of bounded undirected rank-width and a new algorithm for this problem on digraphs of bounded undirected tree-width.
BibTeX
@inproceedings{ganian2009parameterized,
  author = {Robert Ganian},
  title = {{The Parameterized Complexity of Oriented Colouring}},
  booktitle = {MEMICS},
  year = {2009},
}
Figure