Source-linked AI summary
Decomposing Directed Graphs into Partial Orders is Hard
Grzegorz Gutowski, Dominik Jilg, Antonio Lauerbach, Mikołaj Rams
TL;DR
The paper studies how hard it is to cover or partition a digraph’s arcs into partial orders, a decomposition motivated by structural bounds for directed coloring. It uses reductions from NAE-3-SAT and k-Coloring and proves NP-completeness for every fixed k ≥2, even on DAGs.
Problem
The complexity of partial order decompositions on general digraphs and restricted classes is an algorithmic question motivated by their connection to directed coloring.
Source: §1 · p. 2Method
The paper reduces NAE-3-SAT for k = 2 and k-Coloring for k ≥3 to the covering and partitioning problems.
Source: §1 · p. 3Results
For every fixed k ≥2, both variants are NP-complete on DAGs, and for k ≥3 they remain so when the underlying graph is triangle-free.
Source: §1 · p. 2Takeaways & Limitations
The minimum cover and partition sizes can differ, so the two decomposition parameters are distinct even on DAGs.
Source: §4 · p. 10For the k ≥3 construction, the vertex gadget is not explicit and its size has no polynomial bound in k.
Source: §3.2 · p. 10
Abstract
from arXiv · showhide
Comparability graphs represent partial orders and provide natural building blocks for representing a graph as a union of simpler graphs. The analogous task in the directed setting is to represent a digraph as a union of partial orders. Aboulker et al. [arXiv, 2026] recently introduced the partial order decomposition number as a useful structural parameter in their study of tournaments. Formally, a partial order decomposition of a digraph $D$ is a cover of its arc set by transitive acyclic subdigraphs, each representing a strict partial order on the vertex set of $D$. The partial order decomposition number is the minimum number of such subdigraphs needed. We also consider the partitioning variant, in which every arc belongs to exactly one of the partial orders in the decomposition. We prove that, for every fixed $k\geq 2$, deciding whether a digraph admits a decomposition into at most $k$ partial orders is NP-complete, even for directed acyclic graphs (DAGs). For $k=2$, we reduce from NAE-3-SAT. For $k\geq 3$, we reduce from $k$-Coloring, and the reduction yields DAGs with triangle-free underlying graphs. Both reductions establish hardness for both variants. We further show that the minimum cover size and the minimum partition size can differ even on DAGs.
1 Introduction
The paper studies digraph decompositions into transitive acyclic subdigraphs, motivated by structural bounds for directed coloring. It establishes NP-completeness for both covering and partitioning arcs into partial orders, including on DAGs.
1 Introduction
- A partial order decomposition covers a digraph’s arcs with transitive acyclic subdigraphs, and its minimum number of parts is pod (D); pop (D) is the minimum when parts must be arc-disjoint.The orientations are prescribed, and each subdigraph represents a strict partial order.Source: §1 · p. 2
- Bounding the number of partial orders gives a polynomial bound on the dichromatic number in terms of the directed clique number.This structural link motivates studying decomposition complexity beyond tournaments.Source: §1 · p. 2
- For every fixed k ≥2, deciding whether a DAG’s arcs can be covered or partitioned into at most k partial orders is NP-complete; for k ≥3, this holds with triangle-free underlying graphs.The k = 2 reduction is from NAE-3-SAT, while the k ≥3 reduction is from k-Coloring.Source: §1 · pp. 2–3
- Covering and partitioning can differ even on a DAG: the illustrated graph has pod (D) = 2 but pop (D) = 3.Its unique two-part cover places the central arc in both partial orders.Source: §1 · p. 2, Figure 1 · p. 3
- For k = 1, both variants are polynomial-time solvable by checking acyclicity and transitivity.The paper’s hardness results therefore begin at k = 2.Source: §1 · p. 3
2 Hardness Result for k = 2
The k = 2 proof reduces NAE-3-SAT to partial-order decomposition and partitioning, establishing NP-completeness for both variants on DAGs. Variable and clause gadgets encode assignments as two-colorings whose color classes are transitive.
2 Hardness Result for k = 2
- Both deciding whether pod(G) ≤ 2 or pop(G) ≤ 2 is NP-complete, even when G is a DAG.Source: §2 · p. 3
- The reduction uses NAE-3-SAT clauses of three literals, satisfied when each clause contains both a true and a false literal.The input variant has three distinct variables per clause [8].Source: §2 · p. 3
- A variable gadget's two path arcs must receive different orders because their shortcut is absent, yielding two states for each variable.The states correspond to the variable's two possible truth values.Source: §2 · pp. 3–4
- Each clause gadget's three consecutive path arcs encode its literals, and cannot all share one color because transitivity would require a missing shortcut.Source: §2 · pp. 4–5, Figure 2 · p. 4
- On the constructed instances, a cover by two partial orders exists exactly when a partition does, so both variants reduce to coloring arcs with two transitive color classes.The construction is acyclic and can be built in polynomial time; it has 3n + 4m vertices and 2n + 11m arcs.Source: §2 · pp. 4–5
- A satisfying NAE assignment yields a valid two-coloring, and every valid coloring recovers an assignment satisfying every clause.Source: §2 · p. 5
3 Hardness Result for k ≥3
For every fixed k ≥3, both partial-order cover and partition decisions are NP-complete even on triangle-free DAGs. The reduction uses structural properties of partial-order partitions and a construction from k-Coloring.
3 Hardness Result for k ≥3
- For every fixed k ≥3, both partial-order cover and partition decisions are NP-complete even on DAGs with triangle-free underlying graphs.Source: §3 · p. 5
3.1 Structural Properties
- For triangle-free DAGs, the minimum cover and partition sizes are equal because redundant covered arcs can be deleted while preserving transitivity.Source: §3.1 · p. 6
- In a triangle-free DAG, an arc set is a partial order exactly when it is an independent set in the underlying graph of the line digraph.Source: §3.1 · p. 6
- Removing an arc into a sink from a (k+1)-pop-critical triangle-free DAG yields a (k−1)-rainbow arc set used in the reduction gadgets.Source: §3.1 · pp. 7–8
3.2 Reduction
- The k-Coloring reduction builds vertex gadgets in a triangle-free DAG, orders inter-gadget arcs by vertex order, and encodes colors through gadget arcs.Source: §3.2 · pp. 8–10
- Although the construction works for every fixed k, the vertex gadgets are not explicit and have no known size bound polynomial in k.Source: §3.2 · p. 10
4 Open Problems
Although the paper characterizes the complexity on triangle-free DAGs, the complexity for tournaments remains open for k ≥ 3. The authors also leave open whether the partition and decomposition numbers can differ arbitrarily much.
4 Open Problems
- The complexity of partial order decomposition on tournaments remains open for k ≥ 3.The paper characterizes the problem's complexity on triangle-free DAGs.Source: §4 · p. 10
- The partial order partition number can differ from the partial order decomposition number, even on DAGs.Source: §4 · p. 10
- Whether the difference between the partition and decomposition numbers can be arbitrarily large remains open.Source: §4 · p. 10