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 -