Paperlane

no. 4 · Wednesday 28 October 2026

Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors

Hangning Liu, Jørgen Bang-Jensen, Jin Yan and Jia Zhou

math.CO · v2 · 18 pp

Abstract

For two digraph properties $P_1$ and $P_2$, a $(P_1,P_2)$-arc-decomposition of a digraph $D$ is a partition $A(D)=A_1\mathbin{\dot\cup}A_2$ such that the spanning subdigraphs $D[A_1]$ and $D[A_2]$ have properties $P_1$ and $P_2$, respectively. We prove that it is NP-complete to decide whether a digraph admits an arc-decomposition with properties $(P_1,P_2)$ where $(P_1,P_2)\in \{$(perfect matching, having no odd cycle), (perfect matching, strong), (perfect matching, having an out-branching), (cycle factor, having no odd cycle)$\}$. All four problems remain NP-complete even when restricted to strongly connected digraphs. We also prove that every strongly connected digraph with minimum semi-degree at least three contains two vertex-disjoint cycles whose simultaneous arc deletion leaves the digraph strongly connected. These results settle some open problems posed by Bang-Jensen, Bessy, Gonçalves, and Picasarri-Arrieta [Theoret. Comput. Sci. 928 (2022), 167–182].

comments
18 pages, 10 figures
fields
Combinatorics
pdf ↗ page arXiv:2608.24031 ↗