Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors
Abstract
For two digraph properties P1 and P2, a (P1,P2)-arc-decomposition of a digraph D is a partition A(D)=A1mathbin∪̇A2 such that the spanning subdigraphs D[A1] and D[A2] have properties P1 and P2, respectively. We prove that it is NP-complete to decide whether a digraph admits an arc-decomposition with properties (P1,P2) where (P1,P2)∈ {(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].
Related
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- A simplified proof of the FPRAS for counting perfect matchings
- Perfect matchings in hypergraphs and Feige's inequality
- Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
BibTeX
@misc{liu2026complexity,
title = {{Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors}},
author = {Hangning Liu and Jørgen Bang-Jensen and Jin Yan and Jia Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.24031},
eprint = {2608.24031},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.24031},
}
RIS
TY - UNPB
TI - Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors
AU - Hangning Liu
AU - Jørgen Bang-Jensen
AU - Jin Yan
AU - Jia Zhou
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2608.24031
UR - https://arxiv.org/abs/2608.24031
AB - 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_1mathbin∪̇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)∈ {(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].
ER -