Deciding how to split directed graphs into partial orders is computationally hard
Decomposing Directed Graphs into Partial Orders is Hard
Computational Complexity
Summary
This research looks at breaking down directed graphs into simpler parts called partial orders. The authors show that figuring out if you can split a directed graph into a small number of these parts is a really hard problem for computers. They prove that even simple directed graphs can’t easily be checked for these splits. Their work helps explain the limits of understanding complex networks by decomposing them into simpler structures.
What this means in practice
- •For graph algorithm designers: Avoid assuming efficient algorithms exist to decompose directed graphs into few partial orders when designing graph processing systems.
- •For network schedulers: Recognize computational limits in scheduling tasks modeled as partial orders within directed acyclic task graphs.
A theory result. No direct application yet.
Authors
Grzegorz Gutowski, Dominik Jilg, Antonio Lauerbach, Mikołaj Rams
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\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.