Decomposing Directed Graphs into Partial Orders is Hard
cs.CC
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: Comparability graphs represent partial orders and provide natural building blocks for representing a graph as a union of simpler graphs.
Abstract
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 at least 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 at least 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.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?