Id: arxiv/2608.24031 Url: https://arxiv.org/abs/2608.24031 Tags: math.CO Score: 0 Title: Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors Domain: math.CO Source: arxiv Authors: Hangning Liu, Jørgen Bang-Jensen, Jin Yan, Jia Zhou Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-25 Page: https://delphi.science/r/arxiv/2608.24031 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. For example, a (strong,strong)-arc-decomposition of a digraph $D=(V,A)$ is a partitioning $A=A_1\cup{}A_2$ of $A$ so that each of the spanning digraphs $D_i=(V,A_i)$, $i=1,2$ are strongly connected. 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 \{$(is a perfect…