TY - JOUR
T1 - Complexity of some arc-partition problems for digraphs
AU - Bang-Jensen, J.
AU - Bessy, S.
AU - Gonçalves, D.
AU - Picasarri-Arrieta, L.
N1 - Funding Information:
Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B , by research grant DIGRAPHS ANR-19-CE48-0013 and by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency ( ANR ) with the reference number ANR-17-EURE-0004 .
Publisher Copyright:
© 2022 The Author(s)
PY - 2022/9/3
Y1 - 2022/9/3
N2 - We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.
AB - We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.
KW - Acyclic digraph
KW - Arc-partitions
KW - Branchings
KW - Cycle factor
KW - Digraphs
KW - NP-complete
KW - Polynomial algorithm
KW - Strong subdigraphs
U2 - 10.1016/j.tcs.2022.06.023
DO - 10.1016/j.tcs.2022.06.023
M3 - Journal article
AN - SCOPUS:85132527843
SN - 0304-3975
VL - 928
SP - 167
EP - 182
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -