# Complexity of some arc-partition problems for digraphs

Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas

Picasarri-Arrieta

► To cite this version:

Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas Picasarri-Arrieta. Complexity of some arc-partition problems for digraphs. Theoretical Computer Science, 2022, 928, pp.167-182. 10.1016/j.tcs.2022.06.023. hal-03699980

HAL Id: hal-03699980

https://hal.science/hal-03699980

Submitted on 20 Jun 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complexity of some arc-partition problems for digraphs*

J. Bang-Jensen†

S. Bessy‡

D. Gonçalves§

L. Picasarri-Arrieta¶

June 13, 2022

## Abstract

We study the complexity of deciding whether a given digraph $D = (V, A)$ admits a partition $(A_1, A_2)$ of its arc set such that each of the corresponding digraphs $D_1 = (V, A_1)$ and $D_2 = (V, A_2)$ 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.

**Keywords:** Digraphs, arc-partitions, NP-complete, polynomial algorithm, branchings, strong subdigraphs, cycle factor, acyclic digraph

## 1 Introduction

There are many papers in the literature dealing with the following type of problem: for given (di)graph properties $Q_1, Q_2$ a $(Q_1, Q_2)$-partition of a digraph $D = (V, A)$ is a vertex partition $V = V_1 \cup V_2$ such that the digraph $D[V_i]$ induced by $V_i$ has property $Q_i$. For literature see [5, 7] and the references therein. Important examples of such vertex partition problems are the feedback vertex set problem, where we ask for a partition $(V_1, V_2)$ such that $D[V_1]$ is acyclic and $|V_2| \le k$ for some prescribed $k$, and the dichromatic number of a digraph. A digraph has dichromatic number 2 if and only if it has a vertex partition $(V_1, V_2)$ such that $D[V_i]$ is acyclic for $i = 1, 2$. Both problems are known to be NP-complete [19, 13]. In [5, 7] a complete complexity characterization was given for the 120 vertex-partition problems where we seek a partition $(V_1, V_2)$ of $V(D)$ such that $D_i = D[V_i]$ has property $Q_i$ and $Q_1, Q_2$ both belong to the following set of properties: {being strongly connected, being connected, having minimum out-degree at least 1, having minimum in-degree at least 1, having minimum semi-degree at least 1, having minimum degree at least 1, having an out-branching, having an in-branching}.

No similar extensive study of arc-partition problems seems to have been made so this is the purpose of the present paper. For two (di)graph properties $P_1$ and $P_2$, we define the $(P_1, P_2)$-arc-partition problem as the problem of partitioning the arcs of $D$ in two subsets $A_1$ and $A_2$ such that the digraph $D_1 = (V, A_1)$ has property $P_1$ and the digraph $D_2 = (V, A_2)$ has property $P_2$. Although no exhaustive study seems to exist so far, there are many natural $(P_1, P_2)$-arc-partition problems, and there exist some well-known research on special cases of it. For instance, the (having an out-branching, having an out-branching)-arc-partition problem is known to be polynomial [16],

<footnote>*Research supported by the Independent Research Fond 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.</footnote>

<footnote>†Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark (email: jbj@imada.sdu.dk).</footnote>

<footnote>‡LIRMM, Univ Montpellier, CNRS, Montpellier, France (email:stephane.bessy@lirmm.fr).</footnote>

<footnote>§LIRMM, Univ Montpellier, CNRS, Montpellier, France (email:daniel.goncalves@lirmm.fr).</footnote>

<footnote>¶Université Côte d'Azur, Inria, CNRS, I3S, France (email: lucas.picasarri-arrieta@inria.fr).</footnote>
where an *out-branching* (resp. *in-branching*) is the orientation of a spanning tree where every vertex has in-degree at most one (resp. out-degree at most one). As another example, the (*being strongly connected*, *being strongly connected*)-arc-partition problem was shown to be NP-complete [11]. The purpose of this paper is to address the complexity of the 120 ($P_1$, $P_2$)-arc-partition problems when $P_1$ and $P_2$ belong to the following 15 properties:

- bipartite : Being bipartite,

- connected : The underlying graph is connected,

- strong : Being strongly connected,

- acyclic : Being acyclic,

- acyclic spanning : Being acyclic and each vertex is spanned (minimum degree at least 1).

- having $B^+$ : Containing an out-branching rooted in some vertex

- having $B^-$ : Containing an in-branching rooted in some vertex

- cycle factor : Each vertex has in-degree and out-degree exactly 1,

- $\delta^- \ge k$: Each vertex has in-degree at least $k$,

- $\delta^+ \ge k$: Each vertex has out-degree at least $k$,

- $\ge k$ arcs : Having at least $k$ arcs,

- $\le k$ arcs : Having at most $k$ arcs,

- balanced : $d^+(v) = d^-(v)$ for every vertex $v$,

- eulerian : Being balanced and strongly connected,

- cycle : Being an oriented cycle (with possibly some vertices not spanned).

In the following, we determine, or recall results on, the complexity of the corresponding 120 algorithmic problems. For each of these problems their status with respect to NP-completeness is established. We point out that some of our NP-completeness proofs uses polynomial so-called Turing (one to many) reductions from a known NP-complete problem to our present problem. For those problems we have not been able to find a polynomial Karp (many to one) reduction (compare with [17, p. 113, 118-120]). All the problems for which we use Turing reductions to show their hardness are in NP so they are at least as hard as any other problem in NP.

See Tables 1-3 for an overview of the complexities. The notation in the tables is as follows: We use $P$ for polynomially solvable problems and NP-c for problems that are NP-complete and finally we denote by NP-cT problems that are NP-complete with respect to Turing reductions. In each entry of the tables we refer to either a subsection where the result is proved, to a Theorem in a section or to a result from the literature. As we already mentioned, some of the problems have already been studied in the literature and their complexity is known. We review those in Section 2. Then Section 3 is devoted to the description of polynomial-time algorithms, and it is organized according to the techniques used therein (e.g. reduction to a max-flow, or to a matroid intersection instance). Section 4 contains proofs for the NP-complete problems that were not already in the literature. Then we conclude in Section 5 with some open problems.

<table><caption>Table 1: Complexity of arc-partitioning problems</caption><thead><tr><th></th><th>Bipartite</th><th>Connected</th><th>Strong</th><th>Acyclic</th><th>Acyclic spanning</th><th>Having B<sup>+</sup></th><th>Having B<sup>-</sup></th></tr></thead><tbody><tr><td>Bipartite</td><td>NP-c (4.3.1)</td><td>P (3.1)</td><td>P (3.1)</td><td>NP-c (4.2.2)</td><td>NP-c (4.2.3)</td><td>P (3.1)</td><td>P (3.1)</td></tr><tr><td>Connected</td><td>×</td><td>P [18, 24]</td><td>NP-c [12]</td><td>P (3.1)</td><td>NP-c (4.2.4)</td><td>NP-c [12]</td><td>NP-c [12]</td></tr><tr><td>Strong</td><td>×</td><td>×</td><td>NP-c [11]</td><td>P (3.1)</td><td>NP-c (4.2.7)</td><td>NP-cT (Th. 10)</td><td>NP-cT (Th. 10)</td></tr><tr><td>Acyclic</td><td>×</td><td>×</td><td>×</td><td>P (3.2.6)</td><td>P (3.5)</td><td>P (3.1)</td><td>P (3.1)</td></tr><tr><td>Acyclic spanning</td><td>×</td><td>×</td><td>×</td><td>×</td><td>P (3.5)</td><td>NP-c (4.2.6)</td><td>NP-c (4.2.6)</td></tr><tr><td>Having B<sup>+</sup></td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>P [16]</td><td>NP-c [2]</td></tr><tr><td>Having B<sup>-</sup></td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>P [16]</td></tr></tbody></table>
<table><caption>Table 2: Complexity of arc-partitioning problems continued</caption><thead><tr><th></th><th>δ<sup>-</sup> ≥ k</th><th>δ<sup>+</sup> ≥ k</th><th>Cycle Factor</th><th>≤ k arcs</th><th>≥ k arcs</th><th>Balanced</th><th>Eulerian</th><th>Cycle</th></tr></thead><tbody><tr><td>Bipartite</td><td>P (3.1)</td><td>P (3.1)</td><td>NP-c (4.3.3)</td><td>NP-c (4.3.2)</td><td>P (3.1)</td><td>NP-c (4.3.4)</td><td>NP-c (4.3.5)</td><td>NP-c (4.3.6)</td></tr><tr><td>Connected</td><td>P (3.4.2)</td><td>P (3.4.2)</td><td>NP-c (Th. 8)</td><td>P (3.1)</td><td>P (3.2.1)</td><td>P (3.1)</td><td>NP-c (Th. 10)</td><td>NP-c [12]</td></tr><tr><td>Strong</td><td>NP-c (Cor. 9)</td><td>NP-c (Cor. 9)</td><td>NP-c (Th. 8)</td><td>P (3.1)</td><td>NP-c (Th. 8)</td><td>P (3.1)</td><td>NP-c (Th. 10)</td><td>NP-c [12]</td></tr><tr><td>Acyclic</td><td>P (3.1)</td><td>P (3.1)</td><td>NP-cT (Th. 8)</td><td>NP-c (4.2.1)</td><td>P (3.1)</td><td>P (3.2.5)</td><td>NP-c (4.2.8)</td><td>NP-cT (Th. 10)</td></tr><tr><td>Acyclic spanning</td><td>P (3.3.1)</td><td>P (3.3.1)</td><td>NP-cT (Th. 8)</td><td>NP-c (4.2.1)</td><td>P (3.2.1)</td><td>NP-cT (Th. 8)</td><td>NP-cT (Th. 10)</td><td>NP-cT (Th. 10)</td></tr><tr><td>Having B<sup>+</sup></td><td>P (3.2.3)</td><td>NP-c (4.2.5)</td><td>NP-c (Th. 8)</td><td>P (3.1)</td><td>P (3.2.1)</td><td>P (3.1)</td><td>NP-c (Th. 10)</td><td>NP-c [12]</td></tr><tr><td>Having B<sup>-</sup></td><td>NP-c (4.2.5)</td><td>P (3.2.3)</td><td>NP-c (Th. 8)</td><td>P (3.1)</td><td>P (3.2.1)</td><td>P (3.1)</td><td>NP-c (Th. 10)</td><td>NP-c [12]</td></tr></tbody></table>

<table><caption>Table 3: Complexity of arc-partitioning problems continued</caption><thead><tr><th></th><th>δ<sup>-</sup> ≥ k</th><th>δ<sup>+</sup> ≥ k</th><th>Cycle Factor</th><th>≤ k arcs</th><th>≥ k arcs</th><th>Balanced</th><th>Eulerian</th><th>Cycle</th></tr></thead><tbody><tr><td>δ<sup>-</sup> ≥ k</td><td>P (3.2.3)</td><td>P (3.3.2)</td><td>P (3.2.2)</td><td>P (3.1)</td><td>P (3.2.1)</td><td>P (3.1)</td><td>NP-c (Cor. 9)</td><td>P (3.2.3)</td></tr><tr><td>δ<sup>+</sup> ≥ k</td><td>×</td><td>P (3.2.3)</td><td>P (3.2.2)</td><td>P (3.1)</td><td>P (3.2.1)</td><td>P (3.1)</td><td>NP-c (Cor. 9)</td><td>P (3.2.3)</td></tr><tr><td>Cycle Factor</td><td>×</td><td>×</td><td>P (3.2.2)</td><td>P (3.2.1)</td><td>P (3.2.1)</td><td>P (3.2.2)</td><td>NP-c (Th. 8)</td><td>NP-c (Th. 8)</td></tr><tr><td>≤ k arcs</td><td>×</td><td>×</td><td>×</td><td>P (3.2.1)</td><td>P (3.1)</td><td>P [14]</td><td>NP-c [14]</td><td>NP-c (Th. 8)</td></tr><tr><td>≥ k arcs</td><td>×</td><td>×</td><td>×</td><td>×</td><td>P (3.2.1)</td><td>P (3.1)</td><td>NP-c (Th. 8)</td><td>P (3.2.1)</td></tr><tr><td>Balanced</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>P (3.2.4)</td><td>P (3.2.4)</td><td>P (3.2.4)</td></tr><tr><td>Eulerian</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>NP-c (Th. 10)</td><td>NP-c [12]</td></tr><tr><td>Cycle</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><td>NP-c (Th. 10)</td></tr></tbody></table>

## 2 Preliminaries

We refer the reader to [6] for notation and terminology not explicitly defined in this paper. We will only recall a few pieces of notation here. The **underlying graph** $UG(D)$ of a digraph $D = (V, A)$ is the graph $G = (V, E)$ which has an edge between $u$ and $v$ if and only if at least one of $uv, vu$ is an arc of $D$. A digraph is **connected** if $UG(D)$ is a connected graph.

Let $D = (V, A)$ be a digraph. The **out-degree**, $d^{+}(v)$ (resp. **in-degree**, $d^{-}(v)$) of a vertex $v \in V$ is the number of arcs in $A$ of the form $vw$ (resp. $uv$) and the **degree** of $v$ is $d(v) = d^{+}(v) + d^{-}(v)$. We denote by $\delta^{+}(D)$ (resp. $\delta^{-}(D)$ and $\delta(D)$) the minimum out-degree (resp. in-degree and degree) of a vertex in $D$. The minimum semi-degree, denoted $\delta^{0}(D)$ of $D$ is $\delta^{0}(D) = \min\{\delta^{+}(D), \delta^{-}(D)\}$. A digraph $D$ is **k-regular** if every vertex has in-degree and out-degree equal to $k$; $D$ is **balanced** if $d^{+}(v) = d^{-}(v)$ for every vertex $v \in V(D)$ and $D$ is **eulerian** if it is balanced and connected.

**Theorem 1** (Edmonds). [16] Let $D = (V, A)$ be a digraph, let $s \in V$ be a fixed vertex and let $k \ge 2$ be an integer. Then $D$ has $k$ arc-disjoint out-branchings rooted at $s$ if and only if there are $k$ arc-disjoint $(s, t)$-paths in $D$ for every choice of $t \in V - s$

The existence of $k$ arc-disjoint $(s, t)$-paths in a digraph can be checked in polynomial time using flows (see e.g. [6, Section 5.4]). A polynomial algorithm which constructs the desired out-branchings or determines that no such collection exists follows from the proof of Theorem 1 in [22].

**Theorem 2.** [23] For every integer $k > 2$ it is NP-complete to decide whether a $k$-regular graph $G$ has a hamiltonian cycle.

**Theorem 3.** [6, Theorem 6.1.2] It is NP-complete to decide whether a $2$-regular digraph has a hamiltonian cycle

**Corollary 4.** For every integer $k \ge 2$ it is NP-complete to decide whether a $k$-regular digraph $D$ has a hamiltonian cycle.
**Proof.** The case $k = 2$ is Theorem 3 and for $k \ge 3$ the result follows by the observation that if $G$ is $k$-regular and $D$ is obtained from $G$ by replacing each edge of $G$ by a directed 2-cycle, then $D$ is a $k$-regular digraph and $D$ has a hamiltonian cycle if and only $G$ has a hamiltonian cycle. $\square$

**Lemma 5.** For every integer $k \ge 2$ the problem of deciding whether a $k$-regular digraph contains an hamiltonian path is NP-complete.

**Proof.** Given a $k$-regular digraph $D$, let us construct a $k$-regular digraph $D_2$ that has an hamiltonian path if and only if $D$ has an hamiltonian cycle. As the hamiltonian cycle problem is NP-hard for $D$ by Corollary 4, we obtain the NP-hardness for $D_2$.

Fix an arbitrary vertex $x$ of $D$ and construct $D_2$ by starting with two copies of $D$, with the vertices $x'$ and $x''$ corresponding to $x$. Then replace each arc $x'u$ by an arc $x''u$, and vice versa. Clearly $D_2$ is $k$-regular. Let us now see that it has an hamiltonian path if and only if $D$ has an hamiltonian cycle. Indeed, if $D_2$ has an hamiltonian path, the subpath linking $x'$ and $x''$ spans a copy of $D$, and thus corresponds to an hamiltonian cycle of $D$. Conversely, an hamiltonian cycle of $D$ corresponds to an $x'x''$-path spanning a copy of $D$, thus taking two such paths one obtains an hamiltonian cycle of $D_2$. $\square$

**Theorem 6.** [12] It is NP-complete to decide whether a 2-regular digraph has a pair of arc-disjoint hamiltonian cycles.

The following classic theorem by Tutte characterizes graphs with $k$-edge disjoint spanning trees.

**Theorem 7** (Tutte). [26] A graph $G = (V, E)$ has $k$ edge-disjoint spanning trees for an integer $k \ge 2$ if and only if

$$e_P \ge k \cdot (|V| - 1) \qquad (1)$$

holds for every partition $\mathcal{P} = \{V_1, V_2, \dots, V_r\}$ of $V$ into non-empty sets, where $e_P$ denotes the number of edges of $E$ which have an end in two distinct sets of $\mathcal{P}$

Although the condition in the theorem involves an exponential family of partitions of the vertex set, one can obtain a polynomial algorithm which for a given integer $k \ge 2$ either constructs $k$ edge-disjoint trees in $G$ or a partition $\mathcal{P}$ which violates (1). This follows from the constructive proof of Theorem 7 in [18] and also from the fact that the problem can be solved using matroid techniques (see Section 3.4).

This implies that the (connected, connected)-arc-partition problem is polynomial as it is equivalent to finding two edge-disjoint spanning trees in a graph.

A digraph $D = (V, A)$ has a (having $B^+$, having $B^+$)-arc-partition if and only if there are two vertices $u_1, u_2$ of $D$ (possibly $u_1 = u_2$) of $D$ such that $D$ has arc-disjoint out-branchings $B_{u_1}^+$ and $B_{u_2}^+$, where $B_{u_i}^+$ is rooted at $u_i$, $i = 1, 2$. For a given choice of distinct vertices $u_1, u_2$ of $D$ the digraph $D'$ we obtain by adding a new vertex $s$ and the arcs $su_1, su_2$ has two arc-disjoint out-branchings rooted at $s$ if and only if $D$ has branchings $B_{u_1}^+$ and $B_{u_2}^+$ as above.

By Theorem 1 and the remark after it we can check the existence of arc-disjoint out-branchings from $s$ in $D'$. Hence by checking all possible choices of $u_1, u_2$ we can solve the (having $B^+$, having $B^+$)-arc-partition for $D$ in polynomial time. By symmetry (reversing all arcs of $D$) implies that also the (having $B^-$, having $B^-$)-arc-partition problem, is polynomial. In contrast to this, Thomassen proved that the (having $B^+$, having $B^-$)-arc-partition problem is NP-complete (see [2] and [3]).

The more constrained (strong, strong)-arc-partition problem is NP-complete [11]. This problem is more constrained because any strongly connected graph contains an out-branching, and an in-branching.

The (strong, connected)-arc-partition problem is NP-c [12]. Actually this problem remains NP-c for 2-regular digraphs [9]. The (having $B^+$, connected)-arc-partition problem is also known to be NP-c [12] but this time, the problems turns out to be polynomial on 2-regular digraphs [9].

In [12], it is also shown that the (strong, cycle), the (having $B^+$, cycle), the (connected, cycle), and the (eulerian, cycle)-arc-partitions problems are all NP-c. The latter result is not explicitly stated but one can check that the reduction in [12] from 3-SAT to the (strong, cycle)-arc-partition problem is also a reduction from 3-SAT to (eulerian, cycle)-arc-partition problem, because the
constructed digraph is eulerian, and every (strong, cycle)-arc-partition of an eulerian digraph $D$ is also an (eulerian, cycle)-arc-partition of $D$.

In [14] it is shown that the ($\leq k$ arcs, balanced)-arc-partition problem can be solved in polynomial time, while the ($\leq k$ arcs, eulerian)-arc-partition problem is NP-complete, even when restricted to planar digraphs with maximum degree three. However the authors showed that the ($\leq k$ arcs, eulerian)-arc-partition problem admits an FPT algorithm when parameterized by $k$.

# 3 Polynomially solvable arc-partition problems

## 3.1 Trivial problems

A property $\mathcal{P}$ is **upward closed** if every superdigraph on the same vertex set of a digraph $D$ with property $\mathcal{P}$ also has property $\mathcal{P}$. The ($P_1, P_2$)-arc-partition problem is trivial to solve when $P_1$ holds for the arcless digraph, and when $P_2$ is upward closed. Indeed, it suffices to check whether $D$ has property $P_2$. If this is the case then $(\emptyset, A(D))$ is a solution and otherwise there is no solution. This argument shows that the ($P_1, P_2$)-arc-partition problem is polynomial when $P_1$ belongs to $\{\textit{bipartite, acyclic}, \leq k \textit{ arcs, balanced}\}$ and $P_2$ belongs to $\{\textit{connected, spanning, strong, having } B^+, \\ \textit{having } B^-, \delta^+ \geq k, \delta^- \geq k, \geq k \textit{ arcs}\}$. Note that these combinations of properties define 32 different problems.

## 3.2 Almost trivial problems

### 3.2.1 ($\geq k$ arcs, $P_2$)-arc-partition

If there exists a polynomial algorithm $\mathcal{A}$ which given a digraph $D$, either computes the minimum size of a subgraph of $D$ having property $P_2$ or decides that $D$ has no such subdigraph, then it suffices to check whether there are enough edges left to verify the $\geq k$ arcs property. We claim that such an algorithm $\mathcal{A}$ exists when $P_2$ belongs to $\{\geq k \textit{ arcs}, \delta^+ \geq k, \textit{cycle, cycle factor, connected, having } B^+, \textit{having } B^-, \textit{Acyclic spanning}\}$. For $\geq k$ arcs and $\delta^+ \geq k$, the existence of $\mathcal{A}$ is clear. For *cycle*, one just computes the shortest directed cycle of $D$ in polynomial time [6]. For *connected*, one has to check that $UG(D)$ is connected, and has to consider a spanning tree (with $|V| - 1$ edges) for the connected subgraph. For *having* $B^+$ (resp. *having* $B^-$, or a *cycle factor*), one has to check that $D$ has an out-branching (resp. in-branching, or a *cycle factor*), and only has to consider that it uses exactly $|V| - 1$ arcs (resp. $|V| - 1$ arcs, or $|V|$ arcs). Note that as a *cycle factor* always has exactly $|V|$ arcs, the (*cycle factor*, $\leq k$ arcs)-arc-partition problem is also polynomial. For *acyclic spanning*, one has to compute a minimum spanning star forest of $UG(D)$, and this is polynomial [20].

### 3.2.2 (*cycle factor*, $P_2$)-arc-partition

Removing a cycle factor decreases the out-degree and the in-degree of every vertex by exactly one. Hence, for any property $P_2$ for which it suffices to check the in- and out-degrees of the vertices (which is the case when $P_2$ belongs to $\{\textit{cycle factor, balanced}, \delta^+ \geq k, \delta^- \geq k\}$) it suffices to check whether $D$ contains a cycle factor or not (recall that a digraph $H$ has property 'cycle factor' precisely when $H$ is 1-regular).

### 3.2.3 ($\delta^+ \geq k, P_2$)-arc-partition

For each vertex we know how many out-going arcs are available for $A_2$, and there is no other constraint for $A_1$. Thus, if property $P_2$ admits an extra constraint consisting in bounding the out-degrees of the vertices, and remains polynomially solvable, the ($\delta^+ \geq k, P_2$)-arc-partition problem is polynomially solvable. This is the case when $P_2$ belongs to $\{\textit{cycle}, \delta^+ \geq \ell, \textit{having } B^-\}$. Indeed, for *cycle* we are given a set of vertices (those with $\delta^+(v) = k$) through which the cycle should not pass. For $\delta^+ \geq \ell$, all vertices must have out-degree at least $k + \ell$. For *having* $B^-$, at most one vertex can have out-degree $\leq k$, and in that case it is the only possible root for the in-branching.
### 3.2.4 (balanced, $P_2$)-arc-partition

If every digraph with property $P_2$ is balanced (which is the case when $P_2$ belongs to $\{\text{balanced}, \text{eulerian}, \text{cycle}, \text{cycle factor}\}$, then $D$ admits a (balanced, $P_2$)-arc-partition if and only if $D$ is balanced and contains a subgraph $(V, A_2)$ with property $P_2$ (as the graph $(V, A \setminus A_2)$ is necessarily balanced).

### 3.2.5 (balanced, acyclic)-arc-partition

Every digraph has such an arc-partition $(A_1, A_2)$. Indeed, let $A_1 = \emptyset$ and $A_2 = A(D)$ and then while $D[A_2]$ contains a directed cycle $C$, move all its edge from $A_2$ to $A_1$. Clearly this results in the desired arc-partition in polynomial time.

### 3.2.6 (acyclic, acyclic)-arc-partition

Let us recall the easy argument that every digraph $D$ has such an arc-partition: just take an arbitrary ordering $x_1, x_2, ..., x_n$ of $V(D)$. Then

$$A_1 = \{x_i x_j \in A | i < j\} \text{ and } A_2 = \{x_i x_j \in A | i > j\}$$

is an (acyclic, acyclic)-arc-partition of $D$ (see Figure 1).

<figure><img src="image_2.png" /><figcaption>Figure 1: Construction of an (acyclic, acyclic)-arc-partition</figcaption></figure>

## 3.3 Problems that can be solved using flows in networks

Here we list two problems which we have not already shown to be polynomial and where a polynomial algorithm can be obtained using flows.

A network $N(V, A, l, u)$ consists of a directed graph $D = (V, A)$ associated with two functions on $A$: a lower bound $l$, a capacity $u$.

Let $s, t \in V$ be distinct vertices of a network $N(V, A, l, u, c)$. A feasible $(s,t)$-flow in $N$ is a function $x: A \to \mathbb{R}^+$ such that the following holds:

* $\sum_{sv \in A} x(sv) = \sum_{vt \in A} x(vt)$,

* for each $v \in V \setminus \{s, t\}$, $\sum_{uv \in A} x(uv) = \sum_{vu \in A} x(uv)$ and

* for each $a \in A$, $l(a) \le x(a) \le u(a)$.

Given a network $N(V, A, l, u)$, along with distinct vertices $s, t \in V$, one can decide in polynomial time whether $N$ has a feasible $(s,t)$-flow (see e.g [1] or [6, Chapter 4]).

### 3.3.1 (acyclic spanning, $\delta^+ \ge k$)-arc-partition

Given an instance $D = (V, A)$ we make a network as follows: let $V', V''$ be disjoint copies of $V$ and form a network with vertex set $V' \cup V'' \cup \{s, t\}$ with an arc $v'w''$ for each original arc $vw$, all possible arcs from $s$ to $V'$ as well as all possible arcs from $V''$ to $t$. All arcs have lower bounds 0 and their capacities are as follows: all arcs from $V'$ to $V''$ have capacity 1. If $d_D^+(v) = k$ then set the capacity of the arc $v''t$ to $d^-(v) - 1$ otherwise it is $d^-(v)$. Set the capacity and the lower bound of the arc $sv'$ to $k$ for all $v \in V$. This network has a feasible $(s,t)$-flow if and only if $D$ has a subdigraph $D_2 = (V, A_2)$ with out-degree $k$ everywhere such that $D_1 = D - A_2$ has min degree at least one. If $D_1$ has directed cycles, we can move arcs to $D_2$ until there are no directed cycles in $D_1$ and still have minimum degree at least one in the remaining digraph.
### 3.3.2 ($\delta^{-} \ge k$, $\delta^{+} \ge \ell$)-arc-partition

Let $\mathcal{N}$ be a network on vertices $\{s,t\} \cup V_1 \cup V_2$ where $V_1$ and $V_2$ are two copies of $V$ with all arcs $v_{i,1}v_{j,2}$ such that $v_iv_j \in A(D)$. These arcs have capacity 1 and lower bound 0. Then add all arcs $sv_{i,1}$ with lower bound 0 and capacity $d^{+}(v) - \ell$. and all arcs $v_{i,2}t$, with a lower bound $k$ and infinite capacity (see Figure 2).

Then it is easy to check that $\mathcal{N}$ admits a $(s,t)$-flow if and only if $D$ admits a ($\delta^{-} \ge k$, $\delta^{+} \ge \ell$)-arc-partition: the capacities on the arcs out of $s$ make sure that we reserve at least $\ell$ arcs out of every vertex for $D_1$ and the capacities on the arcs into $t$ make sure that we reserve at least $k$ arcs entering every vertex for $D_2$.

<figure><img src="image_3.png" /><figcaption>Figure 2: Construction of the network $\mathcal{N}$</figcaption></figure>

## 3.4 Problems solvable by matroid techniques

Although we only need matroid techniques to solve the (connected, $\delta^{-} \ge k$)-arc-partition problem, we have included this small subsection as it illustrates the power of matroid algorithms.

Let $S$ be a finite set of elements and let $\mathcal{F}$ be a collection of subsets of $S$. The pair $M = (S, \mathcal{F})$ is a **matroid** if the following holds :

(i) $\emptyset \in \mathcal{F}$,

(ii) If $Y \in \mathcal{F}$ and $X \subseteq Y$, then $X \in \mathcal{F}$,

(iii) If $X, Y \in \mathcal{F}$ and $|Y| = |X| + 1$ then there exists an $y \in Y \setminus X$ such that $X \cup \{y\} \in \mathcal{F}$.

The sets in $\mathcal{F}$ are called **independent** and it follows from the axioms above that all maximal independent sets (called **bases**) of a matroid have the same size. A famous and very useful example of a matroid is the circuit matroid associated with a graph $G = (V, E)$. Here $S = E$ and $\mathcal{F}$ consists of the acyclic edge sets $E$. The following are two very important problems for matroids

* **The matroid intersection problem:** Given two matroids $M_1 = (S, \mathcal{F}_1)$ and $M_2 = (S, \mathcal{F}_2)$ over the same set $S$; Find a set $X \in \mathcal{F}_1 \cap \mathcal{F}_2$ of maximum cardinality.

* **The matroid partition problem:** Given two matroids $M_i = (S, \mathcal{F}_i)$, $i = 1, 2, \dots, k$ over the same set $S$; Find a set $X \subset S$ of maximum cardinality with the property that $X$ has a partition $X = X_1 \cup X_2 \dots \cup X_k$ such that $X_i \in \mathcal{F}_i$ for $i = 1, 2, \dots, k$.

Both problems above can be solved in polynomial time provided that we have polynomial oracles to decide independence of a given set in the involved matroids. (see e.g. [21, 24]).
### 3.4.1 (connected, connected)-arc-partition

We mentioned already in Section 2 that Kaiser [18] gave an algorithmic proof of Theorem 7 and that this leads to a polynomial algorithm that either produces a pair of edge-disjoint trees or a bad partition $\mathcal{F}$ of the vertex set. Another way to find $k$ edge-disjoint spanning trees or decide that no such collection exists is to use an algorithm for matroid partition: Given a graph $G = (V, E)$ let $M_1, M_2, \dots, M_k$ be $k$ copies of the circuit matroid for $G$ (as defined above) So a set of $E' \subseteq E$ of edges is independent in $M_i$ precisely when $E'$ induces a forest in $G$ and a base of $M_i$ has size $|V| - 1$ if and only if $G$ is connected (bases are the edges of a spanning tree). Thus $G$ has $k$ edge-disjoint spanning trees if and only if the solution $X$ to the matroid partition problem for $M_1, M_2, \dots, M_k$ has size $k(|V| - 1)$. Hence we obtain an algorithm for deciding whether a graph has $k$ edge-disjoint spanning trees by solving the corresponding matroid partitioning problem.

### 3.4.2 (connected, $\delta^- \ge k$)-arc-partition

First note that this problem is equivalent to the partition of the arc set into a spanning tree of the underlying undirected graph, and a graph with minimum in-degree at least $k$. This can be solved by matroid intersection. Given a digraph $D = (V, A)$ with $\delta^-(D) \ge k$ we let $M_1$ be the circuit matroid of $UG(D)$ and let $M_2 = (A, \mathcal{F}_2)$ be the matroid where a set $A'$ of arcs is in $\mathcal{F}_2$ if each vertex $v$ has in-degree at most $d^-(v) - k$ in $D' = (V, A')$ (we leave out the easy proof that $M_2$ is a matroid over the set $A$). Then $M_1$ and $M_2$ have a common independent set of size $|V| - 1$ if and only if $D$ has the desired partition (the spanning tree must leave at least $k$ arcs into $v$ unused for each $v$.)

## 3.5 (acyclic spanning, acyclic (spanning))-arc-partition

Let $D$ be a connected digraph (otherwise handle each of its connected component separately). We claim that $D$ admits an (acyclic spanning, acyclic spanning)-arc-partition if and only if the following holds:

* $D$ has minimum degree at least two,

* $UG(D)$ is not a cycle of odd length.

If $D$ is an odd cycle or has minimum degree at most one, then $D$ does not admit any (spanning, spanning)-arc-partition and hence it also has no (acyclic spanning, acyclic spanning)-arc-partition. Here the property *spanning* is the same as having minimum degree at least one in the underlying graph.

Conversely, Assume that $UG(D)$ is not an odd cycle and that it has minimum degree at least two. If $UG(D)$ is an even length cycle, then $D$ clearly admits a (acyclic spanning, acyclic spanning)-arc-partition) so we can assume that $UG(D)$ is not a cycle. We will show how to construct an (acyclic spanning, acyclic spanning)-arc-partition of $D$.

As we mentioned in Section 3.2.6, $D$ admits an (acyclic, acyclic)-arc-partition $(A_1, A_2)$. While $D$ has a vertex $v$ such that $v$ is not covered by $A_1$, choose one arc (entering or leaving) of $v$ and move it from $A_2$ to $A_1$. This move cannot create a cycle and thus we can repeat this operation until the current arc-partition $(A_1, A_2)$ is an (acyclic spanning, acyclic)-arc-partition. This shows that the (acyclic spanning, acyclic)-arc-partition problem can be solved in polynomial time, because every digraph without any isolated vertex admits such a partition. Assume now that $(A_1, A_2)$ is such a partition that minimizes the number of vertices of $D$ that are not covered by $A_2$. If $A_2$ covers every vertex of $V$ we are done, so assume that $v$ is a vertex of $D$ which is not covered by $A_2$.

**Claim 7.1.** $UG(D)$ does not contain a walk $W = u_0u_1\dots u_k$ alternating between $A_1$ and $A_2$ from $v=u_0$, and such that if $u_{k-1}u_k \in A_i$ the vertex $u_k$ has an incident edge in $A_i \setminus E(W)$.

*Proof.* Suppose that $UG(D)$ contains such a walk and let $W$ be a shortest walk with this property, and note that the minimality of $W$ implies that the following holds:

* $u_0u_1 \in A_1$ and $d_{A_1}(u_0) > 1$,
• $d_{A_1}(u_j) = 1$ (this edge being $u_{j-1}u_j$) for any odd $j < k$, and

• $d_{A_2}(u_j) = 1$ (this edge being $u_{j-1}u_j$) for any even $0 < j < k$.

Then, let $A'_1 = A_1\Delta A(W)$ and $A'_2 = A_2\Delta A(W)$ (where $X\Delta Y$ is the set $(X \setminus Y) \cup (Y \setminus X)$). Note that each of $A'_1, A'_2$ induce acyclic digraphs. If $A'_1$ (resp. $A'_2$) contains a directed cycle, this cycle uses an edge $u_{j-1}u_j$ where $j$ is even (resp. odd). However, as $d_{A'_1}(u_{j-1}) = 1$ (resp. as $d_{A'_2}(u_{j-1}) = 1$) such cycle cannot exist. Furthermore, one can also note that $(V, A'_1)$ is (still) spanning and that $(V, A'_2)$ spans one more vertex, $v$. This is a contradiction, and we thus have that $D$ does not contain such alternating walk $W$. $\square$

Since $UG(D)$ has minimum degree at least two, this graph contains cycles. Let us now show that $v$ belongs to every cycle of $UG(D)$. Otherwise, one could consider a cycle $C$ of $UG(D)$ not containing $v$, and a (non-trivial) path $P = u_0u_1...u_k$ from $u_0 = v$ to any vertex $u_k$ of $C$. By applying Claim 7.1, to all subpaths of $P \cup C$ starting at $v$ we conclude that $P$ is alternating, that the two edges incident to $u_k$ in $C$ belong to the same set $A_i$ (the one such that $u_{k-1}u_k \notin A_i$), and that otherwise the edges of $C$ alternate between $A_1$ and $A_2$ (and thus $C$ has odd length). These observations imply that $(A'_1, A'_2)$ with $A'_i = A_i\Delta(A(P) \cup A(C))$ is an (acyclic spanning, acyclic)-arc-partition such that $A'_2$ covers more vertices of $D$ than $A_2$, a contradiction.

Finally, we have that $v$ has degree two: otherwise the walk consisting in going from $v$ to $v$ through a cycle, and leaving $v$ through a third edge would violate Claim 7.1. This contradicts the fact that $UG(D)$ is not a cycle. Indeed if $UG(D)$ had a vertex of degree at least three, it would contain several cycles (since $\delta(UG(D)) \ge 2$), say $C_1$ and $C_2$, intersecting at $v$, but in that case $C_1\Delta C_2$ would contain a cycle that does not contain $v$, a contradiction. We thus conclude that $(A_1, A_2)$ is an (acyclic spanning, acyclic spanning)-arc-partition.

# 4 Some NP-complete arc-partition problems

The NP-completeness of many of the arc-partition problems follow from Theorems 3 and 6 and the following two results

## 4.1 Reduction from hamiltonian cycle in 2-regular digraphs

**Theorem 8.** Let $D = (V, A)$ be a 2-regular digraph on $n$ vertices. The following properties are equivalent:

0. $D$ admits a hamiltonian cycle,

1. $D$ admits a (strong, $\delta^+ \ge 1$)-arc-partition,

2. $D$ admits an (eulerian, $\delta^+ \ge 1$)-arc-partition,

3. $D$ admits a (connected, cycle factor)-arc-partition,

4. $D$ admits a (strong, cycle factor)-arc-partition,

5. $D$ admits a (having $B^+$, cycle factor)-arc-partition,

6. $D$ admits a (strong, $\ge n$ arcs)-arc-partition,

7. $D$ admits a (eulerian, $\ge n$ arcs)-arc-partition,

8. $D$ admits an (eulerian, cycle factor)-arc-partition,

9. $D$ admits a (cycle, cycle factor)-arc-partition,

10. $D$ admits a (cycle, $\le n$ arcs)-arc-partition,

11. there is an arc $a \in A$ such that $D - \{a\}$ admits an (acyclic, cycle factor)-arc-partition,
12. there is an arc $a \in A$ such that $D - \{a\}$ admits an (acyclic spanning, cycle factor)-arc-partition,

13. there is an arc $a \in A$ such that $D - \{a\}$ admits an (acyclic spanning, balanced)-arc-partition,

*Proof.* Let $D$ be a 2-regular digraph. If $D$ has a hamiltonian cycle $C$, then $D - A(C)$ is a cycle factor. Hence, $(A(C), A \setminus A(C))$ is the desired partition of the properties 1 to 10. For properties 11, 12 and 13, one just has to consider any arc $a$ of $C$ and $(A(C) \setminus \{a\}, A \setminus A(C))$ is the desired partition.

Conversely, if $D$ admits a (cycle, $\le n$ arcs)-arc-partition, then $D$ admits a cycle $C$ of size at least $n$. This cycle is thus of size exactly $n$ and $D$ is hamiltonian. Hence property 10 implies property 0.

If $D$ admits a ($P_1, P_2$)-arc-partition ($A_1, A_2$), with $P_1 \in \{\text{strong, eulerian}\}$, then $A_1$ induces a strong spanning subdigraph on at least $n$ arcs of $D$. If $P_2 \in \{\delta^+ \ge 1, \ge n \text{ arcs, cycle factor}\}$, then $|A_2| \ge n$. Thus $A_1$ induces an hamiltonian cycle, as it is spanning strong subdigraph with exactly $n$ arcs. Thus each of the properties 1, 2, 4, 6, 7 and 8 implies property 0.

If $D$ admits a (cycle factor, $P_2$)-arc-partition ($A_1, A_2$), then $A_2$ also induces a cycle factor of $D$ since $D$ is 2-regular. If property $P_2$ implies that $(V, A_2)$ is connected, then this subgraph is hamiltonian. This is the case for $P_2 \in \{\text{connected, having } B^+, \text{ cycle}\}$ and similarly if $P_2$ is the property of having an arc such that its removal results in being acyclic. Indeed, a cycle factor with $k$ connected components needs at least $k$ arc removals to become acyclic. Hence each of the properties 3, 5, 9, 11, and 12 implies property 0.

If $D$ has an arc-partition ($A_1, A_2$), such that $(V, A_1)$ is balanced and such that $(V, A_2 \setminus \{a\})$ is spanning and acyclic for some arc $a$, the reasoning is similar. Here we have that $A_2$ induces an eulerian subdigraph (as it is balanced, connected and spanning), but as $A_2 \setminus \{a\}$ induces an acyclic digraph, the eulerian subdigraph induced by $A_2$ has only one cycle and it is thus an hamiltonian cycle. Hence property 13 also implies property 0. $\square$

By Theorem 3, each of the 13 arc-partition problems 1-13 mentioned above are NP-complete.

Using the fact that a $(k+1)$-regular digraph has a (strong, $\delta^+ \ge k$)-arc-partition if and only if it has a hamiltonian cycle which again is if and only if it has a (eulerian, $\delta^+ \ge k$)-arc-partition we obtain the following from Corollary 4.

**Corollary 9.** For every integer $k \ge 1$ the following problems are NP-complete

* The (strong, $\delta^+ \ge k$)-arc-partition problem.

* The (eulerian, $\delta^+ \ge k$)-arc-partition problem.

**Theorem 10.** Let $D = (V, A)$ be a 2-regular digraph. The following properties are equivalent :

0. $D$ admits two arc-disjoint hamiltonian cycles,

1. $D$ admits a (strong, strong)-arc-partition,

2. $D$ admits an (eulerian, connected)-arc-partition,

3. $D$ admits an (eulerian, strong)-arc-partition,

4. $D$ admits an (eulerian, eulerian)-arc-partition,

5. $D$ admits an (eulerian, having $B^+$)-arc-partition,

6. $D$ admits a (cycle, cycle)-arc-partition,

7. there is an arc $a \in A$ such that $D - \{a\}$ admits a (cycle, acyclic)-arc-partition,

8. there is an arc $a \in A$ such that $D - \{a\}$ admits an (cycle, acyclic spanning)-arc-partition,

9. there is an arc $a \in A$ such that $D - \{a\}$ admits an (eulerian, acyclic spanning)-arc-partition,
10. there is an arc $a \in A$ such that $D - \{a\}$ admits a (strong, having $B^+$)-arc-partition,

*Proof.* If $D$ admits two arc-disjoint hamiltonian cycles $C_1$ and $C_2$, then $(A(C_1), A(C_2))$ is the desired partition of properties 1 to 6. By removing any arc of $A(C_2)$, one can obtain the desired partition of properties 7 to 10. Let us now show that each of the properties 1 to 10 implies property 0.

If $D$ admits $(A_1, A_2)$ a (strong, strong)-arc-partition, $A_1$ and $A_2$ induce two arc-disjoint strong spanning subdigraph of $D$. Then, each of this subdigraph has exactly $n$ arcs and $D$ admits two arc-disjoint hamiltonian cycle.

If $D$ admits $(A_1, A_2)$ an (eulerian, connected)-arc-partition, then $A_2$ is eulerian, because it is balanced (since $D$ is 2-regular and $A_1$ is eulerian) and connected. Hence, $(A_1, A_2)$ is a (strong, strong)-arc-partition of $D$, so $A_1$ and $A_2$ are two arc-disjoint hamiltonian cycles of $D$. The same holds for partitions with properties 3, 4 and 5 because they are also (eulerian, connected)-arc-partitions of $D$.

If $D$ admits $(C_1, C_2)$ a (cycle, cycle)-arc-partition, then $C_1$ and $C_2$ are two arc-disjoint hamiltonian cycles because each cycle must have exactly $n$ arcs.

If there exists an arc $a \in A$ such that $D - \{a\}$ admits $(A_1, A_2)$ a (cycle, acyclic)-arc-partition, then $D - A_1$ is a balanced spanning subdigraph of $D$. In other words, $D - A_1$ the union of some arc-disjoint cycles. Since $D - (A_1 \cup a)$ is acyclic, $D - A_1$ is a cycle, and $(A_1, A_2 \cup a)$ is a (cycle, cycle)-arc-partition of $D$. With the previous remark, we show that $D$ has 2 arc-disjoint hamiltonian cycles. The same kind of argument works for properties 8 and 9.

Finally if there is an arc $uv$ such that $D' = D - \{uv\}$ admits $(A_1, A_2)$ a (strong, having $B^+$)-arc-partition, then $A_1$ has exactly $n$ arcs and $A_2$ has exactly $n-1$ arcs. Then, $A_1$ induces a hamiltonian cycle of $D'$, and $A_2$ induces a hamiltonian path $P$ of $D'$. Since $u$ has exactly one leaving arc in $D'$, and $v$ has exactly one entering arc in $D'$, then $P$ starts in $v$ and ends in $u$. Then, $A_1$ and $A_2 \cup \{uv\}$ induces two arc-disjoint hamiltonian cycles of $D$. $\square$

By Theorem 6, each of the 10 arc-partition problems 1-10 mentioned above are NP-complete.

## 4.2 ($P_1$, acyclic)-arc-partition problems

### 4.2.1 ($\leq k$ arcs, acyclic)-arc-partition

This is exactly the Feedback-Arc-Set problem, known to be NP-c [6].

The ($\leq k$ arcs, acyclic spanning)-arc-partition problem is also NP-c : let $D$ be an instance of the ($\leq k$ arcs, acyclic)-arc-partition problem and $D'$ obtained from $D$ by adding a vertex $v$ and all arcs $vu$ (where $u$ is a vertex of $D$). Clearly, since $v$ is a source and is dominating, $D$ admits an ($\leq k$ arcs, acyclic)-arc-partition if and only if $D'$ admits a ($\leq k$ arcs, acyclic spanning)-arc-partition.

### 4.2.2 (bipartite, acyclic)-arc-partition

This problem is equivalent to finding a bipartition $(V_1, V_2)$ of $V$ such that each $D[V_i]$ is an acyclic digraph on $V$: If $D$ has such a vertex partition, then taking $A_1$ to be all arcs between $V_1$ and $V_2$ and $A_2 = A(D[V_1]) \cup A(D[V_2])$ we get a (bipartite, acyclic)-arc-partition. Conversely, if $(A_1, A_2)$ is a (bipartite, acyclic)-arc-partition, then let $(V_1, V_2)$ be a bipartition of $D_1 = (V, A_1)$. Then $(V_1, V_2)$ is the desired vertex partition of $D$.

This shows that the (bipartite, acyclic)-arc-partition problem is NP-complete as the corresponding vertex-partition problem (acyclic chromatic number at most 2) is known to be NP-c [13].

### 4.2.3 (bipartite, acyclic spanning)-arc-partition

This is NP-c as the previous problem is NP-c : let $D$ be an instance of the (bipartite, acyclic)-arc-partition problem. Let $D'$ the digraph obtained from $D$ by adding a new vertex $x$ and an arc from $x$ to every vertex of $D$. Then $D$ admits a (bipartite, acyclic)-arc-partition if and only if $D'$ admits a (bipartite, acyclic spanning)-arc-partition.
### 4.2.4 (connected, acyclic spanning)-arc-partition

Clearly a digraph $D$ admits a (connected, acyclic spanning)-arc-partition if and only if $D$ admits a (connected, spanning)-arc-partition (while the spanning part contains a cycle, one can move one arc of this cycle to the connected part).

Now let $G$ be a cubic graph, and $D'$ an arbitrary orientation of $G$. Then $G$ admits a hamiltonian path if and only if $D'$ admits a (connected, spanning)-arc-partition. This shows that the (connected, acyclic spanning)-arc-partition problem is NP-c since the hamiltonian path problem is NP-complete on cubic graphs (see e.g. page 199 in [17]).

### 4.2.5 (having $B^+$, $\delta^+ \ge k$)-arc-partition

The (having $B^+$, $\delta^+ \ge k$)-arc-partition problem is NP-complete on ($k+1$)-regular digraphs because it is equivalent to the hamiltonian path problem on ($k+1$)-regular digraphs, which is NP-complete by Lemma 5. Indeed, if a ($k+1$)-regular digraph $D$ has a hamiltonian path $P$, then $P$ is also an out-branching, and $\delta^+(D \setminus E(P)) \ge k$. Conversely, given a (having $B^+$, $\delta^+ \ge k$)-arc-partition ($A_1, A_2$), note that every vertex has at most one outgoing arc in $A_1$. Since in any out-branching every vertex except the root has exactly one incoming arc, this out-branching in $A_1$ is a hamiltonian path starting at the root of the out-branching.

### 4.2.6 (having $B^+$, acyclic spanning)-arc-partition

We describe a polynomial reduction of the hamiltonian path problem for 2-regular digraphs to the (having $B^+$, acyclic spanning)-arc-partition problem.

Let $D = (V, A)$ be an instance of the hamiltonian path problem for 2-regular digraphs and let $B(D) = (V', V'', A')$ be the bipartite digraph where $V'$ and $V''$ are two copies of $V$, and $A'$ contains all arcs $u'u''$ (for $u \in V$) and all arcs $u''v'$ (for $uv \in A$). Note that every vertex of $B(D)$ is incident to exactly 3 arcs. We claim that $D$ has a hamiltonian path if and only if $B(D)$ admits a (having $B^+$, acyclic spanning)-arc-partition. Suppose first that $P = u_1u_2\dots u_n$ is a hamiltonian path of $D$. Then $P' = u'_1u''_1u'_2u''_2\dots u'_nu''_n$ is a hamiltonian path of $B(D)$ and every arc not on $P'$ goes from $V''$ to $V'$. This implies that ($A_1, A_2$) is a (having $B^+$, acyclic spanning)-arc-partition of $B(D)$ when we take $A_1 = A(P')$ and $A_2 = A(B(D)) \setminus A_1$.

Conversely, assume we have such partition ($A_1, A_2$) of $A(B(D))$. As $A_2$ is spanning, we have that $A_1$ induces a digraph whose maximum undirected degree is at most two. Thus, the out-branching contained in this digraph is either a hamiltonian path or it is the union of two directed paths $P_1, P_2$ starting from the same root. In the former case we are done, so assume we are in the latter case. If the root has out-degree two then it is a vertex of $V''$, we denote it $r''$. As $r'$ has out-degree zero in this out-branching we have that one of the paths, say $P_1$, ends at $r'$. We finally obtain a hamiltonian path of $B(D)$, from the out-branching by removing the first edge of $P_1$, adding the edge $r'r''$ and finishing with the path $P_2$.

### 4.2.7 (strong, acyclic spanning)-arc-partition

The bipartite digraph $B(D)$ that we constructed above has a (strong, acyclic spanning)-arc-partition if and only if it has a hamiltonian cycle and this happens if and only if $D$ has a hamiltonian cycle. Hence the fact that the hamiltonian cycle problem is NP-complete for 2-regular digraphs [6] implies that the (strong, acyclic spanning)-arc-partition problem is NP-complete.

### 4.2.8 (eulerian, acyclic)-arc-partition

Consider again a 2-regular digraph $D$ and the digraph $B(D)$ as above. It is easy to see that $D$ is hamiltonian if and only if $B(D)$ is hamiltonian.

If $D$ is hamiltonian, then let $C$ be a hamiltonian cycle of $B(D)$. Since every vertex has in-degree or out-degree at most 1, $B(D) - A(C)$ is acyclic because every vertex in $B(D) - A(C)$ is either a source or a sink and $(A(C), A \setminus A(C))$ is an (eulerian, acyclic spanning)-arc-partition.

Conversely, if $B(D)$ admits an eulerian subgraph $H$, then, since the degree of every vertex in the underlying graph of $B(D)$ is three, every vertex of $B(D)$ has exactly one entering and one
leaving arc in $H$, implying that $H$ is a hamiltonian cycle of $B(D)$. This shows that $B(D)$ has an (eulerian, acyclic (spanning))-arc-partition if and only if $D$ is hamiltonian. Thus the (eulerian, acyclic (spanning))-arc-partition problem is NP-complete.

## 4.3 (bipartite, $P_2$)-arc-partition problems

### 4.3.1 (bipartite, bipartite)-arc-partition

It is easy to check that $D = (V, A)$ admits such a partition if and only if the underlying graph $D$ is 4-colorable: Suppose $V_1, V_2, V_3, V_4$ is a partition of $V(D)$ into 4 independent sets. Let $A_1$ consist of all arcs of $A$ that go between $V_1 \cup V_2$ and $V_3 \cup V_4$ and let $A_2$ be the remaining arcs (they go between $V_1$ and $V_2$ or between $V_3$ and $V_4$). Then $(A_1, A_2)$ is a (bipartite, bipartite)-arc-partition. Conversely if $(A_1, A_2)$ is a (bipartite, bipartite)-arc-partition, then let $(X_{i,1}, X_{i,2})$ be a bipartition of $V(D[A_i])$, $i = 1, 2$, and take the vertex partition $X_{1,1} \cap X_{2,1}, X_{1,1} \cap X_{2,2}, X_{1,2} \cap X_{2,1}, X_{1,2} \cap X_{2,2}$. Each of the 4 sets in this partition are independent so they induce a 4-colouring of the underlying graph $D$. The (bipartite, bipartite)-arc-partition problem is thus NP-c.

### 4.3.2 (bipartite, $\le k$ arcs)-arc-partition

This problem is equivalent to finding a cut of size at least $m-k$, where $m$ is the number of arcs in the input. Since the problem of finding a maximum cut is known to be NP-hard [17], The (bipartite, $\le k$ arcs)-arc-partition problem is NP-c.

### 4.3.3 (bipartite, cycle factor)-arc-partition

We will show how to reduce the well known NP-complete 3-SAT problem to this arc-partition problem.

Let $W[u, v, p, q]$ be the digraph (the variable gadget) with vertices $\{u, v, y_1, \dots, y_{3p}, z_1, \dots, z_{3q}\}$, which has two directed $(u, v)$-paths $uy_1, \dots, y_{3p}v$ and $uz_1, \dots, z_{3q}v$, and also has the arc $vu$ and all the arcs $y_{3i}y_{3i-2}$, for $i \in \{1, \dots, p\}$, and $z_{3i}z_{3i-2}$, for $i \in \{1, \dots, q\}$ (see Figure 3). We allow one of $p, q$, but not both to be zero, in which case one of the $(u, v)$-paths is just an arc from $u$ to $v$.

Note that if $(A_1, A_2)$ is a (bipartite, cycle factor)-arc-partition of $W[u, v, p, q]$, then the following holds:

* The arc $vu$ is necessarily in $A_2$ (because of the cycle in $A_2$ containing $u$).

* Either $uy_1$ or $uz_1$ belongs to $A_2$ (same reason).

* Each arc $y_{3i}y_{3i+1}$ (respectively $z_{3i}z_{3i+1}$) belongs to the same part as $uy_1$ and as $y_{3p}v$ (respectively as $uz_1$ and as $z_{3q}v$). This follows from the fact that all the vertices $y_{3i+2}$ and $z_{3i+2}$ are incident to two arcs in $A_2$, and that then among the arcs entering $y_{3i+1}$ and $z_{3i+1}$ (resp. leaving $y_{3i}$ and $z_{3i}$) exactly one should be in $A_2$.

Note that these three properties still hold if $W[u, v, p, q]$ is part of a larger digraph, in such a way that the only arcs leaving $W[u, v, p, q]$ leave from the vertices $y_{3i+1}$ and $z_{3i+1}$, and the only arcs entering $W[u, v, p, q]$ enter at the vertices $y_{3i}$ and $z_{3i}$. Furthermore, note that all arcs leaving and entering $W[u, v, p, q]$ must be part of $A_1$.

<figure><img src="image_4.png" /><figcaption>Figure 3: One of the two possible (bipartite, cycle factor)-arc-partitions of $W[u, v, 2, 1]$.</figcaption></figure>
Let $W'[r, s, t, a_1, a_2, a_3]$ be the digraph (the clause gadget) of Figure 4 ($r, s$ and $t$ are vertices, $a_1, a_2$ and $a_3$ are arcs).

<figure><img src="image_5.png" /><figcaption>Figure 4: The clause gadget $W'$</figcaption></figure>

Let $\mathcal{F}$ be an instance of 3-SAT with variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$, the ordering of which induces an ordering of the occurrences of a variable $x$ and its negation $\bar{x}$ in these. With each variable $x_i$ we associate a private copy of $W[u_i, v_i, 2p_i, 2q_i]$, where $u_i, v_i$ are vertices, and $p_i$ (resp. $q_i$) is the number of clauses with $x_i$ appearing positively (resp. with $\bar{x}_i$ appearing).

Now with each clause $C_j$ we associate a copy of $W'[r_j, s_j, t_j, a_{j,1}, a_{j,2}, a_{j,3}]$ where $r_j, s_j$ and $t_j$ are three new vertices (private to $C_j$), and we identify $a_{j,1}, a_{j,2}$ and $a_{j,3}$ as follows:

Assume that $C_j$ contains the variables $x_i, x_k, x_l$ (where $x_i, x_k$ and $x_l$ can be negated or not). If $x_i$ is not negated in $C_j$ and this is the $r$th copy of $x_i$, then we identify the arc $a_{j,1}$ with $y_{i,6r-3}y_{i,6r-2}$. If $x_i$ is negated in $C_j$ and this is the $s$th copy of $\bar{x}_i$, we identify $a_{j,1}$ with $z_{i,6s-3}z_{i,6s-2}$. We identify $a_{j,2}$ and $a_{j,3}$ in a similar way.

Now we will prove that the obtained digraph $D'$ admits a (bipartite, cycle factor)-arc-partition if and only if $\mathcal{F}$ is satisfiable.

* Assume that $D'$ admits a (bipartite, cycle factor)-arc-partition $(A_1, A_2)$.

Let $\Phi$ be the truth assignment that we obtain by setting $x_i$ true if $u_iy_{i,1}$ belongs to $A_2$ (the cycle factor part) and false if it belongs to $A_1$ (the bipartite part) for each variable $x_i$. As we remarked previously, for each $k$, $y_{i,3k}y_{i,3k+1}$ and $u_iy_{i,1}$ belong to the same part. The same holds for $z_{i,3k}z_{i,3k+1}$ and $u_iz_{i,1}$.

Let $C_j$ be a clause of $\mathcal{F}$. We have seen that in the clause gadget associated with $C_j$, the arcs of the 7-cycle distinct from $a_1, a_2$, and $a_3$ must be in $A_1$. Since $A_1$ induces a bipartite graph on $D'$, we deduce that at least one arc of $\{a_{j,1}, a_{j,2}, a_{j,3}\}$ belongs to $A_2$. If the corresponding variable $x_i$ is not negated in $C_j$, then $y_{i,6r-3}y_{i,6r-2}$ belongs to $A_2$, implying that $u_iy_{i,1}$ belongs to $A_2$, and $x_i$ is true in $\Phi$. Similarly, if $x_i$ is negated in $C_j$, we deduce that $u_iz_{i,1}$ belongs to $A_2$ and $x_i$ is false in $\Phi$. Since $C_j$ was an arbitrary clause, we see that all clauses of $\mathcal{F}$ are satisfied by the truth assignment $\Phi$.

* Conversely, assume that $\mathcal{F}$ is satisfiable. Let $\Phi$ be a truth assignment of $\mathcal{F}$.

For each variable $x_i$, if $x_i$ is true in $\Phi$, let $E_i$ be the arcs of the cycle $uy_1y_2\dots y_{6p_i}v$ and of all the cycles $z_{i,3k-2}z_{i,3k-1}z_{i,3k}$ ($1 \le k \le 2q_i$). In an analogous way, if $x_i$ is false in $\Phi$, we define $E_i$ as the arcs of the cycles $uz_1z_2\dots z_{6q_i}v$ and $y_{i,3k-2}y_{i,3k-1}y_{i,3k}$ ($1 \le k \le 2p_i$). For each clause $C_j$, we define $\tilde{E}_j$ as the arcs of the 3-cycle $r_j, s_j, t_j$. Let $A_2$ be the union of all $E_i$ and $\tilde{E}_j$ and $A_1$ be all other arcs. We will show that $(A_1, A_2)$ is a (bipartite, cycle factor)-arc-partition of $D'$. Clearly, each vertex of $D'$ has exactly one leaving and one entering arc in $A_2$, so $(V(D'), A_2)$ is a cycle factor. Concerning the bipartite part, one can see that if $a$ and $a'$ are two arcs in $A_2$ that belong to two different clause gadgets, then $a$ and $a'$ belong to two different connected components of $(V(D'), A_2)$. Furthermore, each arc in a variable gadget which belongs to $A_2$ either belongs to a clause gadget or is adjacent to at most one other arc in $A_2$. Now, to prove that $(V(D'), A_2)$ is bipartite, it suffices to prove that the (non oriented) 7-cycle of each clause gadget does not have all of its arc in $A_2$. This is true because the corresponding clause has a true literal in $\Phi$.
**Remark 11.** In the previous proof, the obtained digraph $D'$ has maximum degree 4, showing that the problem is NP-complete even on digraphs of maximum degree at most 4. If $D$ has maximum degree at most 3, the problem becomes polynomial because if $D$ admits a cycle factor $C$, then $D - A(C)$ has maximum degree at most 1 and is obviously bipartite.

### 4.3.4 (bipartite, balanced)-arc-partition

We will use a reduction from 3-SAT which is similar to the one above. This time, let $R[u, v, p, q]$ be the digraph with vertices

$$V(R) = \{u, v, y_1, \dots, y_{2p}v, z_1, \dots, z_{2q}v, x_1, \dots, x_p, w_1, \dots, w_q, a, b, c\}$$

and the arcs of the two directed $(u, v)$-paths $uy_1, \dots, y_{2p}v$ and $uz_1, \dots, z_{2q}v$, all the arcs $y_{2i}x_i, x_iy_{2i-1}$, for $i \in \{1, \dots, p\}$ all the arcs $z_{2i}w_i, w_iz_{2i-1}$, for $i \in \{1, \dots, q\}$ and finally the arcs $va, ab, bu, ca$ and $cb$. Consider any (bipartite, balanced)-arc-partition $(A_1, A_2)$ of $R[u, v, p, q]$ induced by a (bipartite, balanced)-arc-partition of a larger digraph containing $R[u, v, p, q]$ as an induced subdigraph and where all arcs incident with the vertices $a, b, c$ are arcs of $R[u, v, p, q]$. As $c$ is a source (and will remain a source), none of its incident arcs can be in $A_2$. This implies that the arc $ab$ and therefore all arcs of the path $vabu$ are in $A_2$, and either $uy_1$ or $uz_1$ belongs to $A_2$.

Note also that each arc $y_{2i}y_{2i+1}$ (respectively $z_{2i}z_{2i+1}$) belongs to the same part as $uy_1$ and $y_{2p}v$ (respectively as $uz_1$ and $z_{2q}v$).

<figure><img src="image_6.png" /><figcaption>Figure 5: One of the two possible (bipartite, balanced)-arc-partitions of $R[u, v, 2, 1]$.</figcaption></figure>

Now, let $R'[r, s, t, a_1, a_2, a_3]$ be the digraph (the clause gadget) of Figure 6 ($r, s$ and $t$ are vertices, $a_1, a_2$ and $a_3$ are arcs). As $r, s$ and $t$ are sources (and will remain sources in our construction), none of their incident arcs can be in the balanced part of any good partition. So $a_1, a_2$ and $a_3$ are the only arcs in $R'$ which can be in the balanced part, and at least one of them has to be in the balanced part to avoid a 9-cycle in the bipartite part.

<figure><img src="image_7.png" /><figcaption>Figure 6: The clause gadget $R'$</figcaption></figure>
Let $\mathcal{F}$ be an instance of 3-SAT with variables $x_1, ..., x_n$ and clauses $C_1, ..., C_m$, and assume we have an ordering of the occurrences of a variable $x$ and its negation $\bar{x}$ in the clauses. With each variable $x_i$ we associate a copy of $R[u_i, v_i, 2p_i, 2q_i]$ where $x_i$ occurs $p_i$ times and $\bar{x}_i$ occurs $q_i$ times in the clauses of $\mathcal{F}$.

Now with each clause $C_j$ we associate a copy of $R'[r_j, s_j, t_j, a_{j,1}, a_{j,2}, a_{j,3}]$ where $r_j, s_j$ and $t_j$ are three new vertices private to $C_j$, and we identify $a_{j,1}, a_{j,2}$ and $a_{j,3}$ as follows:

Assume that $C_j$ contains the variables $x_i, x_k, x_l$ (where $x_i, x_k$ and $x_l$ can be negated or not). If $x_i$ is not negated in $C_j$ and this is the $r$th copy of $x_i$, then we identify $a_{j,1}$ with $y_{i,4r-2}y_{i,4r-1}$. If $x_i$ is negated in $C_j$ and this is the $r$th copy of $\bar{x}_i$, we identify $a_{j,1}$ with $z_{i,4r-2}z_{i,4r-1}$. We identify $a_{j,2}$ and $a_{j,3}$ in a similar way.

With the same kind of argument as in the previous proof, we can check that $\mathcal{F}$ is satisfiable if and only if the obtained digraph has a (bipartite, balanced)-arc-partition.

### 4.3.5 (bipartite, eulerian)-arc-partition

Let $D = (V, A)$ be an instance of the (bipartite, balanced)-arc-partition problem. Let $V = \{x_1, ..., x_{|V|}\}$ and let $D' = (V', A')$ be the digraph where:

$$V' = V \cup \{d\} \cup \{z_{i,1}, z_{i,2} | 1 \le i \le |V|\}$$

$$A' = A \cup \{dz_{i,1}, z_{i,1}x_i, x_i z_{i,2}, z_{i,2}d\}$$

We claim that $D$ admits a (bipartite, balanced)-arc-partition if and only if $D'$ admits a (bipartite, eulerian)-arc-partition.

Suppose first that $D$ has a partition $(A_1, A_2)$, where $A_1$ induces a bipartite digraph and $A_2$ a balanced digraph. Then $A'_2 = A' \setminus A_1$ is balanced in $D'$ because $A_2$ is balanced in $D$, and we add exactly one leaving and one entering arc in each $x_i, z_{i,1}$ and $z_{i,2}$ (and $d$ has exactly $|V|$ entering and leaving arcs). $A'_2$ is also strongly connected in $D'$ because each $x_i$ has a path to $d$ and from $d$. Thus $(A_1, A_2)$ is a (bipartite, eulerian)-arc-partition of $D'$.

Conversely, if $D'$ admits an (bipartite, eulerian)-arc-partition $(A'_1, A'_2)$, then each arc of $A'_1$ belongs to $A$ because each arc of $A' \setminus A$ is incident to $z_{i,1}$ or $z_{i,2}$, for some $i$ and is the only entering (or leaving) arc of this vertex. Now $A_2 = A \cap A'_2$ is balanced because we remove exactly one leaving and one entering arc of each vertex. Finally, $(A \cap A'_1, A_2)$ is a (bipartite, balanced)-arc-partition of $D$.

### 4.3.6 (bipartite, cycle)-arc-partition

We will show how to reduce the hamiltonian cycle problem in 2-regular digraphs problem to this arc-partition problem.

Let $D = (V, A)$ be 2-regular digraph. We construct $D' = (V', A')$ from $D$ as follows: to each vertex $v_i \in V$, we associate 3 copies $v_{i,1}, v_{i,2}$ and $v_{i,3}$, and the arcs $v_{i,1}v_{i,3}, v_{i,2}v_{i,1}$ and $v_{i,2}v_{i,3}$. To each arc $v_i v_j \in A$, we associate a new vertex $x_{ij}$ and the arcs $v_{i,3}x_{ij}$ and $x_{ij}v_{j,1}$.

Now, we will show that $D$ has a hamiltonian cycle if and only if $D'$ has a (bipartite, cycle)-arc-partition.

If $D$ has a hamiltonian cycle $C = v_1, v_2, ..., v_n$, consider the corresponding cycle of $D'$:

$$C' = v_{1,1}v_{1,3}x_{1,2}v_{2,1}v_{2,3}...v_{n,1}v_{n,3}$$

Clearly, $C'$ contains all arcs of the form $v_{i,1}v_{i,3}$, and then $D' \setminus A(C')$ is bipartite, with the following $(X, Y)$ bipartition:

$$X = \{v_{i,1}, v_{i,3} : v_i \in V\}$$

$$Y = \{v_{i,2} : v_i \in V\} \cup \{x_{ij} : v_i v_j \in A\}$$

Thus $(A(C'), A(D') \setminus A(C'))$ is a (bipartite, cycle)-arc-partition of $D'$.

Conversely, if $D'$ has such a partition, let $C'$ be the cycle such that $D' \setminus A(C')$ is bipartite. Clearly, $C'$ must contain every arc $v_{i,1}v_{i,3}$, because $C'$ cannot contain $v_{i,2}$ and $v_{i,1}v_{i,2}v_{i,3}$ is an odd cycle of $UG(D')$. Then, $C'$ corresponds to a hamiltonian cycle of $D$.
# 5 Remarks and open problems

In this paper, we completed the complexity classification of the $(P_1, P_2)$-arc-partition problem for 15 properties that we consider canonical for digraphs. However, many other properties could be also considered for $P_1$ or $P_2$, as for instance, having a perfect matching, being a spanning bipartite subdigraph, being planar, containing a cycle factor, being a (not necessarily spanning) collection of disjoint cycles, having $\delta^0 \ge k$, having maximum out-degree (in-degree or semi-degree) at most $k$, having no odd directed cycle (same as each strong component is bipartite). We mention here just a few problems that could be interesting to study. Possibly some are easy or already solved, the point is just to show some relevant problems.

**Problem 12.** What is the complexity of the following arc-partition problems?

* The (cycle factor, having no odd directed cycle)-arc-partition problem

* The (perfect matching, having no odd directed cycle)-arc-partition problem

* The (perfect matching, strong)-arc-partition problem

* The (bipartite, $\Delta^+ \le k$)-arc-partition problem

* The (perfect matching, having $B^+$)-arc-partition problem

We have seen that many of the, almost straightforward, NP-completeness proofs used the (non-trivial) fact that hamiltonian cycle problem is NP-complete for 2-regular digraphs or that hamiltonian path is NP-complete for cubic graphs. Hence it is interesting to see which of the $(P_1, P_2)$-arc-partition problems become tractable when restricted to digraphs of higher minimum degree. A natural general class to look at for this is digraphs with sufficiently high arc-connectivity. For a positive integer $k$, a digraph $D = (V, A)$ has **arc-connectivity** at least $k$ if $D - A'$ is strongly connected for any set $A' \subset A$ of at most $k-1$ arcs of $D$.

**Conjecture 13 (Thomassen [25]).** There is a constant $C$, such that every digraph with arc-connectivity at least $C$ has an out-branching and an in-branching which are arc-disjoint.

Conjecture 13 has been verified for semicomplete digraphs [2] and for locally semicomplete digraphs [8]. In both cases arc-connectivity 2 suffices. Recently it was shown that arc-connectivity 3 suffices for digraphs of independence number at most 2 [4]. For general digraphs Conjecture 13 is wide open and as far as we know it is not known whether already $C=3$ would suffice. Conjecture 13 has even been strengthened by as follows.

**Conjecture 14 (Bang-Jensen, Yeo [11]).** There is a constant $C$, such that every digraph with arc-connectivity at least $C$ has a (strong, strong)-arc-partition.

In [12] examples of 2-arc-strong 2-regular digraphs with no hamiltonian cycle are described. They show that arc-connectivity 2 is not sufficient in Conjecture 14.

**Question 1.**

* Does every 3-arc-strong digraph have a (strong, $\delta^+ \ge 1$)-arc-partition?

* Does every 3-arc-strong digraph have a (strong, $\delta^0 \ge 1$)-arc-partition?

* Does every 3-arc-strong digraph have a (strong, connected)-arc-partition?

The next result implies that every 2-arc-strong digraph has a pair of arc-disjoint cycles

**Proposition 15.** Every strong digraph $D = (V, A)$ with minimum out-degree at least 2 has a cycle $C$ such that $D - A(C)$ is strong.

*Proof.* Let $C$ be a cycle of $D = (V, A)$ such that the size of the largest initial component $D_1$ of $D' = D - A(C)$ is maximized. If $V(D_1) = V$ we are done so assume this is not the case. As $D$ is strong we have $V(C) \cap V(D_1) \ne \emptyset$ and $V(C) \cap (V - V(D_1)) \ne \emptyset$. Hence if any strong component of $D' - V(D_1)$ contains a cycle $C'$ then $C'$ is a better choice than $C$ (as all vertices of $V(D_1) \cup V(C)$ will belong to the same strong component of $D - A(C')$), contradiction, so $D' - V(D_1)$ has at most one non-trivial component. This contradicts that every vertex of $D$ has out-degree at least 2. $\square$
**Question 2.** Is it possible to extend the previous result to 2 vertex-disjoint cycles, increasing the arc-connectivity or min degree if necessary?

The hamiltonian path problem is NP-complete on 3-connected cubic graphs [17, page 199] so the first part of the next result is best possible.

**Theorem 16.** Every 2-edge-connected graph $G$ with $\delta^+(D) \ge 4$ has a (connected,spanning)-edge-partition. For every natural number $k \ge 3$ it is NP-complete to decide whether a connected graph of minimum degree at least $k$ has a (connected,spanning)-edge-partition.

*Proof.* Generalizing a result of [15] it was shown in [10] that every 2-edge-connected graph has a spanning tree $T$ such that $d_T(v) \le \frac{d(v)+3}{2}$. This implies that a 2-edge-connected graph of minimum degree at least 4 has a spanning tree which avoids at least one edge at each vertex and hence it has a (connected, spanning)-edge-partition.

To prove the second claim we show how to reduce the hamiltonian path problem for cubic graphs to the (connected,spanning)-edge-partition problem for graphs with minimum degree at least $k$, where $k \ge 3$. Let $G$ be a cubic graph on vertices $v_1, \dots, v_n$ and build the graph $H$ from $G$ and $n(k-3)$ copies $W_{1,1}, \dots, W_{1,k-3}, W_{2,1}, \dots, W_{n,1}, \dots, W_{n,k-3}$ of $K_{k+1}$ by adding one edge from $v_i$ to each of $W_{i,1}, \dots, W_{i,k-3}$. If $k=3$, then $H$ is just $G$ and $H$ has a (connected,spanning)-edge-partition if and only if $G$ has a hamiltonian path, so we may assume that $k > 3$. Now it suffices to note that each of the edges between $V(G)$ and the copies of $K_{k+1}$ are cut edges of $H$ and hence must belong to every spanning tree of $H$. Hence again we see that $H$ has a (connected,spanning)-edge-partition if and only if $G$ has a hamiltonian path. $\square$

**Theorem 17.** Every 2-arc-strong digraph $D$ with $\delta^+(D) \ge 5$ has a (strong, $\delta^+ \ge 1$)-arc-partition and every 2-arc-strong digraph $D$ with $\delta^+(D) \ge 5$ has a (strong, $\delta^0 \ge 1$)-arc-partition.

*Proof.* We prove the second claim as it is easy to check that the first claim follows from our arguments. It was shown in [10] that every 2-arc-strong digraph has an out-branching $B_s^+$ such that $d_{B_s^+}^+(v) \le d_D^+(v)/2 + 1$ and an in-branching $B_s^-$ such that $d_{B_s^-}^-(v) \le d_D^-(v)/2 + 1$, where we can choose the root $s$ arbitrarily. Now let $D = (V, A)$ be 2-arc-strong with $\delta^+(D) \ge 5$ and let $B_s^+, B_s^-$ be branchings as above. Let $A_1$ be the union of $A(B_s^+)$ and $A(B_s^-)$. Then $D_1 = (V, A_1)$ is strong and spanning. Let $A_2 = A - A_1$ and set $D_2 = (V, A_2)$. Then, noting that every vertex except $s$ has out-degree precisely one in $B_s^-$ and $s$ has out-degree zero in $B_s^-$, we have $d_{A_2}^+(v) \ge d_D^+(v) - (\lfloor d_D^+(v)/2 \rfloor + 1) - 1 \ge \lfloor d_D^+(v)/2 \rfloor - 2 \ge \lceil 5/2 \rceil - 2 = 1$. Similarly we see that $d_{A_2}^+(v) \ge 1$. $\square$

The first part of the result above can be improved as follows.

**Theorem 18.** Every 2-arc-strong digraph with minimum out-degree at least 4 has a (strong, $\delta^+ \ge 1$)-arc-partition.

*Proof.* Let $D = (V, A)$ be a 2-arc-strong digraph with minimum out-degree at least 4. Let $X$ be a subset of $V$, $A'$ be the arcs of $D[X]$ and $A_1, A_2$ be two disjoint subsets of $A'$. We say that $(X, A_1, A_2)$ is good if and only if there is a special vertex $x_0$ in $X$ such that the following holds :

* $D_1 = (X, A_1)$ is strongly connected,

* $\forall x \in X, x \ne x_0$, either $d_{A_2}^+(x) \ge 1$ or $d_A^+(x) \ge d_{A'}^+(x) + 2$,

* $d_{A_2}^+(x_0) \ge 1$ or $d_A^+(x_0) \ge d_{A'}^+(x_0) + 1$.

One can see that $D$ always has such a tuple : choose any vertex $x$ in $V$, let $X$ be the singleton $\{x\}$, and $A_1, A_2$ be two empty sets, $(X, A_1, A_2)$ is clearly good.

Now let $(X, A_1, A_2)$ be such a tuple which maximize the size of $X$. Assume that $|X| < |V|$, and let $x_0$ be the special vertex described above.

If $d_{A_2}^+(x_0) \ge 1$, then let $uv \in A$ be an arc from $X$ to $V \setminus X$ (such an arc exists because $D$ is 2-arc-strong). Let $P$ be a shortest path from $v$ to $X$, consider $X' = X \cup V(P)$, $A'_1 = A_1 \cup A(P) \cup \{uv\}$, and $A'_2 = A(D[X']) \setminus A'_1$. Clearly, $(X', A'_1)$ is strongly connected, and every vertex in $X'$, excepting $u$, either has at least one leaving arc in $A'_2$ or has at least two leaving arcs to $V \setminus X$. The vertex $u$
either has at least one leaving arc in $A'_2$ or has at least one leaving arcs to $V \setminus X$. Then $(X', A'_1, A'_2)$ is good (with special vertex $u$) and $|X'| > |X|$, which is a contradiction.

Now if $d_{A_2}^+(x_0) = 0$, then $d_A^+(x_0) \ge d_{A'}^+(x_0)+1$. Let $x_0v$ be an arc from $x_0$ to $V \setminus X$, and consider $P_1$ a shortest path from $X$ to $v$ in $D \setminus \{x_0v\}$, and $P_2$ a shortest path from $v$ to $X$ in $D \setminus \{x_0v\}$. Note that $P_1$ and $P_2$ exist because $D$ is 2-arc-strong. Then consider $X' = X \cup V(P_1) \cup V(P_2)$, $A'_1 = A_1 \cup A(P_1) \cup A(P_2)$, and $A'_2 = A(D[X']) \setminus A'_1$. Now $(X', A'_1, A'_2)$ is good (where the special vertex is the initial vertex of $P_1$). Note that the vertices that are on both $P_1$ and $P_2$ either have at least one leaving in $A'_2$ or have at least two leaving arcs to $V \setminus X$ because the minimum out-degree of $D$ is at least 4. Then $(X', A'_1, A'_2)$ is good and $|X'| > |X|$, which is a contradiction.

Then we know that $X = V$, and $(A_1, A_2)$ is clearly a (strong, $\delta^+ \ge 1$)-arc-partition of $D$. $\square$

**Problem 19.**

* Determine the minimum $r \in \{3,4\}$ such that every 2-arc-strong digraph $D$ with $\delta^+(D) \ge r$ has a (strong, $\delta^+ \ge 1$)-arc-partition.

* Determine the minimum $r \in \{3,4,5\}$ such that every 2-arc-strong digraph $D$ with $\delta^+(D) \ge r$ has a (strong, $\delta^0 \ge 1$)-arc-partition.

**Proposition 20.** For every natural number $k \ge 2$ it is NP-complete to decide whether a digraph $D$ with $\delta^0(D) \ge k$ has a (strong, $\delta^0 \ge 1$)-arc-partition and it is NP-complete to determine whether it has a (strong, $\delta^+ \ge 1$)-arc-partition.

*Proof.* The proof is very similar to the proof of the NP-completeness part in Theorem 16. This time we start from a 2-regular digraph $D$ on $n$ vertices and $(k-2)n$ disjoint copies of the complete digraph on $k+1$ vertices and join each vertex of $V(D)$ by one arc to and from $k-2$ private copies of the complete digraphs. The resulting digraph $D'$ has a (strong, $\delta^0 \ge 1$)-arc-partition if and only if $D$ has a hamiltonian cycle and the proof is complete. $\square$

**Lemma 21.** Every bipartite graph $G = (X, Y, E)$ has an edge-partition $E = E_1, E_2$ such that $d_{E_i}(v) \ge \lfloor d_G(v)/2 \rfloor$. Such a partition can be constructed in polynomial time.

*Proof.* Let $H$ be the bipartite graph that we obtain from $G$ by first replacing each vertex $x_i \in X$ by $r_v = \lfloor d_G(v)/2 \rfloor$ new vertices $x_{i,1}, \dots, x_{i,r}$ and distributing the edges incident to $x_i$ arbitrarily among $x_{i,1}, \dots, x_{i,r}$ such that every vertex except possibly $x_{i,r}$ has degree 2 (which will have degree 1 if $d_G(x_i)$ is odd). Then do the same with the vertices of $Y$ in the graph we obtained above. Then the maximum degree in $H$ is 2 so $H$ is a disjoint union of paths and even cycles. Now 2-colour these paths and cycles so that colours alternate and finally transfer that colouring to $G$ by contracting all copies of a vertex from $X$ ($Y$) into the original vertices. It is easy to check that if $E_i$ is the set of edges of colour $i$ then we have $d_{E_i}(v) \ge \lfloor d_G(v)/2 \rfloor$. $\square$

**Corollary 22.** Every digraph $D = (V, A)$ has an arc-partitioning $A = A_1 \cup A_2$ such that $d_{A_i}^+(v) \ge \lfloor d_D^+(v)/2 \rfloor$ and $d_{A_i}^-(v) \ge \lfloor d_D^-(v)/2 \rfloor$

*Proof.* This follows directly from Lemma 21 by considering the bipartite representation of $D = (V, A)$, that is, the bipartite graph whose vertex set consist of two copies $V_1, V_2$ of $V$ and which has an edge from $u_1 \in V_1$ to $v_2 \in V_2$ precisely when the arc $uv$ is in $A$. $\square$

**References**

[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. *Network flows*. Prentice Hall, Englewood Cliffs, NJ, 1993.

[2] J. Bang-Jensen. Edge-disjoint in- and out-branchings in tournaments and related path problems. *J. Combin. Theory Ser. B*, 51(1):1–23, 1991.

[3] J. Bang-Jensen, S. Bessy, F. Havet, and A. Yeo. Arc-disjoint in- and out-branchings in digraphs of independence number at most 2. *J. Graph Theory*, to appear.
[4] J. Bang-Jensen, S. Bessy, and A. Yeo. Non-separating spanning trees and out-branchings in digraphs of independence number 2. *CoRR*, abs/2007.02834, 2020.

[5] J. Bang-Jensen, N. Cohen, and F. Havet. Finding good 2-partitions of digraphs II. Enumerable properties. *Theor. Comput. Sci.*, 640:1–19, 2016.

[6] J. Bang-Jensen and G. Gutin. *Digraphs: Theory, Algorithms and Applications*. Springer-Verlag, London, 2nd edition, 2009.

[7] J. Bang-Jensen and F. Havet. Finding good 2-partitions of digraphs I. Hereditary properties. *Theor. Comput. Sci.*, 636:85–94, 2016.

[8] J. Bang-Jensen and J. Huang. Decomposing locally semicomplete digraphs into strong spanning subdigraphs. *J. Combin. Theory Ser. B*, 102:701–714, 2010.

[9] J. Bang-Jensen and S. Simonsen. Arc-disjoint paths and trees in 2-regular digraphs. *Discrete Applied Mathematics*, 161(16):2724–2730, 2013.

[10] J. Bang-Jensen, S. Thomassé, and A. Yeo. Small degree out-branchings. *J. Graph Theory*, 42(4):297–307, 2003.

[11] J. Bang-Jensen and A. Yeo. Decomposing $k$-arc-strong tournaments into strong spanning subdigraphs. *Combinatorica*, 24(3):331–349, 2004.

[12] J. Bang-Jensen and A. Yeo. Arc-disjoint spanning sub(di)graphs in digraphs. *Theor. Comput. Sci.*, 438:48–54, 2012.

[13] D. Bokal, G. Fijavz, M. Juvan, Kayl P.M., and Mohar B. The circular chromatic number of a digraph. *J. Graph Theory*, 46:227–240, 2004.

[14] M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, and I. Schlotter. Parameterized complexity of eulerian deletion problems. *Algorithmica*, pages 41–61, 2014.

[15] A. Czumaj and W.B. Strothmann. Bounded degree spanning trees. In *ESA 1997*, volume 1284 of *Lect. Notes Comput. Sci.*, pages 104–117. Springer, 1997.

[16] J. Edmonds. Edge-disjoint branchings. In *Combinatorial Algorithms*, pages 91–96. Academic Press, 1973.

[17] M.R. Garey and D.S. Johnson. *Computers and intractability*. W. H. Freeman, San Francisco, 1979.

[18] T. Kaiser. A short proof of the tree-packing theorem. *Discret. Math.*, 312(10):1689–1691, 2012.

[19] R.M. Karp. Reducibility among combinatorial problems. In *Complexity of computer computations (Proc. Symp., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)*, pages 85–103. Plenum, 1972.

[20] K. Khoshkhah, M. K. Ghadikolaei, J. Monnot, and D. O. Theis. Complexity and approximability of extended spanning star forest problems in general and complete graphs. *Theoretical Computer Science*, 775:1–15, 2019.

[21] B. Korte and J. Vygen. *Combinatorial Optimization*. Springer, Berlin, 2000.

[22] L. Lovász. On two min-max theorems in graph theory. *J. Combin. Theory Ser. B*, 21:96–103, 1976.

[23] C. Picouleau. Complexity of the Hamiltonian Cycle in Regular Graph Problem. *Theor. Comput. Sci.*, 131(2):463–473, 1994.

[24] A. Recski. *Matroid theory and its applications in electric network theory and in statics*. Springer-Verlag, Berlin, 1989.
[25] C. Thomassen. Configurations in graphs of large minimum degree, connectivity, or chromatic number. *Annals of the New York Academy of Sciences*, 555:402-412, 1989.

[26] W.T. Tutte. On the problem of decomposing a graph into *n* connected factors. *J. London Math. Soc.*, 36:221-230, 1961.