TL;DR
This paper settles a significant open question in graph theory by proving that determining if an oriented graph has a "degreewidth" of 1 is NP-complete. Beyond this specific proof, the authors propose a powerful unifying framework that translates classical undirected graph properties into directed ones using "backedge graphs."
What Problem Does This Paper Address?
In graph theory, many problems are easy to solve on Directed Acyclic Graphs (DAGs) but become difficult when cycles are introduced. To manage this complexity, researchers use "width parameters" to measure how far a graph is from being a simple DAG.
Degreewidth is a recently introduced parameter (2023). To find it, you first pick an ordering of the graph's vertices. Any arrow (arc) that points "backwards" against that ordering is called a backedge. The collection of these backedges forms an undirected "backedge graph." The degreewidth of the whole digraph is the minimum possible maximum degree of this backedge graph across all possible vertex orderings.
While previous research showed that computing degreewidth is hard in general, the complexity of the simplest non-trivial case—checking if degreewidth is at most 1—remained an open question. If the degreewidth is 0, the graph is simply a DAG (which is easy to check). This paper proves that even for $k=1$, the problem is computationally "hard" (NP-complete).
Methods
The authors employ two primary approaches:
- Complexity Proof (Reduction): To prove NP-completeness, they perform a reduction from 3-SAT, a classic hard problem in logic. They construct a complex "gadget" digraph where a specific vertex ordering with a backedge degree of 1 exists if and only if the original logic formula is satisfiable. Key components of this construction include "transfer digraphs" (which force certain ordering constraints) and "clause gadgets."
- Theoretical Framework: They formalize a "recipe" for creating directed graph parameters. Given any undirected parameter $\gamma$, they define its directed version $\vec{\gamma}$ by minimizing $\gamma$ over all possible backedge graphs produced by different vertex orderings.
Datasets
As a theoretical paper in combinatorics and complexity theory, this work does not use empirical datasets or training benchmarks. It relies on mathematical proofs and logical derivations.
Key Insights and Ideas
- The "Backedge Recipe": The authors argue that many seemingly unrelated directed graph parameters are actually just undirected parameters viewed through the lens of vertex ordering. For example, they show that the dichromatic number (a directed version of coloring) and the Feedback Vertex Set size can both be derived using their backedge graph framework.
- Settling the Boundary: By proving hardness for $k=1$, the authors establish that there is no "easy" middle ground between DAGs ($k=0$) and general digraphs. Even the slightest amount of "backwards" complexity makes the problem hard.
- Brooks’ Theorem Connection: The paper explores a directed version of Brooks’ Theorem (which relates a graph's maximum degree to its coloring number). They show that while a directed version exists, a complete characterization of the "exceptional" cases is likely impossible to compute efficiently.
Key Results
- Theorem 1.2: Determining if a digraph has degreewidth at most $k$ is NP-complete for every $k \ge 1$. This holds true even for "oriented graphs" (digraphs without bidirectional edges).
- Lemma 2.1: They provide a useful alternative characterization: a digraph has degreewidth $\le k$ if and only if it has a Feedback Arc Set (a set of edges whose removal leaves no cycles) such that the undirected version of that set has a maximum degree of $\le k$.
- Unification: They successfully demonstrate that their framework retrieves several classical parameters, providing a more cohesive way to study directed graph theory.
Limitations and Future Work
- Brooks' Characterization: While the authors prove that a directed version of Brooks' Theorem is "unlikely" to have a simple characterization (due to NP-hardness), they provide only a partial observation (Observation 3.6) regarding the structure of graphs that reach the upper bound of the theorem.
- Layout Parameters: The authors note that their "backedge recipe" does not perfectly align with some existing "layout" parameters like cutwidth or bandwidth. Exploring why these parameters behave differently under vertex ordering remains a point for future investigation.
- Tournament Classes: The paper suggests that applying this framework to specific classes of graphs, like tournaments (where every pair of vertices has an edge), is a promising area for further research.
Summary updated