Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.24031
curl -X POST /api/v1/records/arxiv/2608.24031/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.24031/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'