Complexity of some arc-partition problems for digraphs

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.