{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}