J Bang-Jensen

Nathann Cohen
email: nathann.cohen@gmail.com

Frédéric Havet
email: frederic.havet@inria.fr

Finding good 2-partitions of digraphs II. Enumerable properties

Keywords: oriented, NP-complete, polynomial, partition, splitting digraphs, acyclic, semicomplete digraph, tournament, out-branching, feedback vertex set, 2-partition, minimum degree

Introduction

A k-partition of a (di)graph D is a partition of V (D) into k disjoint sets. Let P 1 , P 2 be two (di)graph properties, then a (P 1 , P 2 )-partition of a (di)graph D is a 2-partition (V 1 , V 2 ) where V 1 induces a (di)graph with property P 1 and V 2 a (di)graph with property P 2 . For example a (δ + ≥ 1, δ + ≥ 1)partition is a 2-partition of a digraph where each partition induces a subdigraph with minimum out-degree at least 1.

There are many papers dealing with vertex-partition problems on (di)graphs. Examples (from a long list) are [START_REF] Alon | Splitting digraphs[END_REF][START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF][START_REF] Bensmail | On the complexity of partitioning a graph into a few connected subgraphs[END_REF][START_REF] Bokal | The circular chromatic number of a digraph[END_REF][START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF][START_REF] Földes | Split graphs[END_REF][START_REF] Grigoriev | Connected feedback vertex set in planar graphs[END_REF][START_REF]Partition of graphs with condition on the connectivity and minimum degree[END_REF][START_REF] Kühn | Partitions of graphs with high minimum degree or connectivity[END_REF][START_REF] Kühn | Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle length[END_REF][START_REF] Le | Splitting a graph into disjoint induced paths or cycles[END_REF][START_REF] Lichiardopol | Vertex-Disjoint Subtournaments of Prescribed Minimum Outdegree or Minimum Semidegree: Proof for Tournaments of a Conjecture of Stiebitz[END_REF][START_REF] Liu | Bipartition of graph under degree constraints[END_REF][START_REF] Misra | FPT algorithms for connected feedback vertex set[END_REF][START_REF] Reid | Two complementary circuits in two-connected tournaments[END_REF][START_REF] Stiebitz | Decomposition of graphs and digraphs[END_REF][START_REF] Suzuki | A linear algorithm for bipartion of biconnected graphs[END_REF][START_REF] Thomassen | Graph decomposition with constraints on the connectivity and minimum degree[END_REF][START_REF] Van't Hof | Partitioning graphs into connected parts[END_REF]. In [START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF] a systematic study of the complexity 2-partition problems for digraphs was initiated and a full characterization was given for the case where one part in the 2-partition has a property from the set H defined in the abstract and the other from H ∪ E (also defined in the abstract). See Tables 1 and2. In this paper we provide the last entries in those tables by determining the complexity of those partition problems where both parts are required to have a given property from E. Each of these properties P are enumerable : any given digraph D has only a polynomial number of inclusionwise maximal induced subdigraphs with property P and all of those can be found in polynomial time (see [START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF]Lemma 2.2]).

For each of the 36 distinct 2-partition problems that we study, it can be checked in linear time whether the given digraph has this property. Hence all of them are in NP. Several of these 36 (P 1 , P 2 )partition problems are NP-complete and some results are somewhat surprising. For example, we show that the (δ + ≥ 1, δ ≥ 1)-partition problem is NP-complete. Some other problems are polynomialtime solvable because (under certain conditions) there are trivial (P 1 , P 2 )-partitions (V 1 , V 2 ) with |V 1 | = 1 (or |V 2 | = 1). Therefore, in order to avoid such trivial partitions we consider [k 1 , k 2 ]partitions, that is, partitions (V 1 , V 2 ) of V such that |V 1 | ≥ k 1 and |V 2 | ≥ k 2 . Consequently, for each pair of above-mentioned properties and all pairs (k 1 , k 2 ) of positive integers, we consider the (P 1 , P 2 )-[k 1 , k 2 ]-partition problem, which consists in deciding whether a given digraph D has a (P 1 , P 2 )-[k 1 , k 2 ]-partition. The results are summarized in the upper-left 8 × 8 subtable of Table 1 (all other results, in grey, are proved in [START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF]). Properties: conn. : connected; B + : out-branchable; B -: in-branchable; A: acyclic; C: complete; X: any property in 'being independent', 'being oriented', 'being semi-complete', 'being a tournament' and 'being symmetric'.

P 1 \ P 2 strong conn. B + B - δ ≥ 1 δ + ≥ 1 δ -≥ 1 δ 0 ≥ 1 A C X strong NPc NPc L NPc L NPc L NPc L NPc L NPc
Complexities: P: polynomial-time solvable; NPc : NP-complete for all values of k 1 , k 2 ; NPc L : NPcomplete for k 1 ≥ 2, and polynomial-time solvable for k 1 = 1. NPc R : NP-complete for k 2 ≥ 2, and polynomial-time solvable for k 2 = 1.

Table 1: Complexity of the (P 1 , P 2 )-[k 1 , k 2 ]-partition problem for some properties P 1 , P 2 .

The paper is organized as follows. We first introduce the necessary terminology. In Section 3 we handle the polynomial-time solvable cases. Then in Section 4 we handle the NP-complete cases and in Section 5 we investigate the impact of strong connectivity on the complexity of the partition problems. We prove that several of the NP-complete problems become polynomial-time solvable when the input is a strong digraph. We also point out that others are still NP-complete on strong digraphs. Our results are summarized in the upper 8 × 8 submatrix of Table 2. Finally we discuss a few other natural 2-partition problems and pose some open problems.

Notation and definitions

Notation follows [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. In this paper graphs and digraphs have no parallel edges/arcs and no loops. We use the shorthand notation [k] for the set {1, 2, . . . , k}. Let D = (V, A) be a digraph with vertex set V and arc set A. We use |D| to denote |V (D)|. Given an arc uv ∈ A we say that u dominates v and v is dominated by u. If uv or vu (or both) are arcs of D, then u and v are adjacent. If none of the arcs exist in D, then u and v are non-adjacent. The underlying graph of a digraph D, denoted U G(D), is obtained from D by suppressing the orientation of each arc and deleting multiple copies of the same edge (coming from directed 2-cycles). A digraph D is connected if U G(D) is a connected graph, and the connected components of D are those of U G(D).

A (u, v)-path is a directed path from u to v, and for two disjoint non-empty subsets X, Y of V an (X, Y )-path is a directed path which starts in a vertex x ∈ X and ends in a vertex y ∈ Y and whose internal vertices are not in X ∪ Y . A digraph is strongly connected (or strong) if it contains a (u, v)-path for every ordered pair of distinct vertices u, v. A strong component of a digraph D is a maximal subdigraph of D which is strong. An initial (resp. terminal) strong component of D is a strong component X with no arcs entering (resp. leaving) X in D. P 1 \ P 2 strong conn. The legend is the same as in Table 1, but we have one more complexity type: NPc * : NP-complete for k 1 , k 2 ≥ 2, and polynomial-time solvable for k 1 = 1 or k 2 = 1. We also emphasize with a bold P, the problems that are polynomial-time solvable on strong digraphs and NP-complete in the general case. The subdigraph induced by a set of vertices X in a digraph D, denoted D X , is the digraph with vertex set X and which contains those arcs from D that have both end-vertices in X. When X is a subset of the vertices of D, we denote by

B + B - δ ≥ 1 δ + ≥ 1 δ -≥ 1 δ 0 ≥ 1 A C X
D -X the subdigraph D V -X . If D is a subdigraph of D, for convenience we abbreviate D -V (D ) to D -D .
A digraph is acyclic if it does not contain any directed cycles. An oriented graph is a digraph without directed 2-cycles. A semicomplete digraph is a digraph with no non-adjacent vertices and a tournament is a semicomplete digraph which is also an oriented graph. Finally, a complete digraph is a digraph in which every pair of distinct vertices induce a directed 2-cycle.

The in-degree (resp. out-degree) of v, denoted by

d - D (v) (d + D (v)), is the number of arcs from V \ {v} to v (v to V \ {v}). The degree of v, denoted by d D (v) is given by d D (v) = d + D (v) + d - D (v).
Finally the minimum out-degree, respectively minimum in-degree, minimum degree is denoted by δ + (D), respectively δ -(D) , δ(D) and the minimum semi-degree of D, denoted by δ 0 (D), is defined as δ 0 (D) = min{δ + (D), δ -(D)}. A vertex is isolated if it has degree 0.

An out-tree rooted at the vertex s, also called an s-out-tree, is a connected digraph T such that d - T (s) = 0 and d - T (v) = 1 for every vertex v different from s. Equivalently, for every v ∈ V (T ) \ {s} there is a unique (s, v)-path in T . The directional dual notion is the one of in-tree. An in-tree rooted at the vertex s, or s-in-tree, is a digraph T such that d + T (s) = 0 and d + T (v) = 1 for every vertex v different from s.

An s-out-branching (resp. s-in-branching) is a spanning s-out-tree (resp. s-in-tree). We say that a subset X ⊆ V (D) is out-branchable (resp. in-branchable) if D X has an s-out-branching (resp. s-in-branching) for some s ∈ X.

Let D be a digraph. For a set S of vertices of D, we denote by Reach + D (S), or simply Reach + (S) if D is clear form the context, the set of vertices that can be reached from S in D, that is, the set of vertices v for which there exists an (S, v)-path in D. Similarly, we denote by Reach - D (S), or simply Reach -(S), the set of vertices that can reach S in D, that is, the set of vertices v for which there exists a (v, S)-path in D. For sake of clarity, we write Reach + D (x) (resp. Reach - D (x) in place of Reach + D ({x}) (resp. Reach - D ({x}). The following lemma is well-known and easy to prove.

Polynomial cases

In all of this subsection (k 1 , k 2 ) denotes a fixed (not part of the input) pair of positive integers. Several results are stated for two pairs of properties and in that case the corresponding 2-partition problems transform into each other by a reversal of all arcs in the digraph. Hence it suffices to show that the problem corresponding to the first pair is polynomial-time solvable. Also, in order to save some space, we make no effort to obtain the best possible complexity but establish only that the problem at hand is polynomially solvable.

Polynomial-time solvable [k 1 , k 2 ]-partition problems

We first deal with the cases where the partition problem in question is polynomial for all fixed lower bounds k 1 , k 2 on the sizes of the two sets in the partition.

We first prove that the (connected, connected)-[k 1 , k 2 ]-partition problem is polynomial-time solvable. The algorithm relies on the following lemma. Assume now that D contains two disjoint connected subdigraphs D 1 and D 2 or order k 1 and k 2 respectively.

Set U 1 := V (D 1 ) and U 2 := V (D 2 ). As long as there

U 1 ∪ U 2 = V (D), there must be a vertex x ∈ V (D) \ (U 1 ∪ U 2 ) adjacent to a vertex y in U 1 ∪ U 2 . If x is adjacent to a vertex in U 1 , then we set U 1 := U 1 ∪ {x}.
Otherwise, x is adjacent to a vertex in U 2 , and we set U 1 := U 1 ∪ {x}. Observe that doing so, at each step D U 1 and D U 2 are connected. Hence at the end of the procedure, we obtain a (connected, connected)-

[k 1 , k 2 ]-partition of D. Theorem 3.2 Deciding whether a digraph has a (connected, connected)-[k 1 , k 2 ]-partition is polynomial- time solvable.
Proof: The algorithm relies on Lemma 3.1. Given a digraph D, it proceeds as follows. We first compute the connected components of D.

• If there are more than two of them, then D is clearly a 'no'-instance, so we return 'No'.

• If there are two connected components C 1 , C 2 , then the only (connected, connected)-partitions of D are (V (C 1 ), V (C 2 )) and (V (C 2 ), V (C 1 )). Therefore we check whether one of this two is a [k 1 , k 2 ]-partition and return 'Yes' in the affirmative and 'No' otherwise.

• If D is connected, then for all pair of disjoint subsets U 1 , U We now prove that the (δ

≥ 1, δ ≥ 1)-[k 1 , k 2 ]
-partition problem is polynomial-time solvable. The algorithm relies on Corollary 3.5, which derives from the following two lemmas.

(δ ≥ 1, δ ≥ 1)-partition (V 1 , V 2 ) of D such that U 1 ⊆ V 1 and U 2 ⊆ V 2 .
Proof: Assume that there are two disjoint subsets (U 1 , U 2 ) such that δ(D U 1 ) ≥ 1 and

δ(D U 2 ) ≥ 1. Initialize V 1 := U 1 and V 2 := U 2 . As long as V 1 ∪ V 2 = V (D), pick a vertex v ∈ V (D) \ (V 1 ∪ V 2 ). Since δ(D) ≥ 1, v has a neighbour w in D. If w ∈ V 1 , then set V 1 := V 1 ∪ {v}. Otherwise set V 2 := V 2 ∪ {v, w}. Observe that doing so at each step we have δ(D V 1 ) ≥ 1 and δ(D V 2 ) ≥ 1. Hence, at the end, (V 1 , V 2 ) is a (δ ≥ 1, δ ≥ 1)-partition of D.
(δ ≥ 1, δ ≥ 1)-[k 1 , k 2 ]-partition is polynomial-time solvable.
Proof: The algorithm on a given digraph D is the following. For every pair

U 1 , U 2 of disjoints subsets of V (D) such that |U 1 | ∈ {k 1 , k 1 + 1} and |U 2 | ∈ {k 2 , k 2 + 1}, we check whether δ(D U 1 ) ≥ 1 and δ(D U 2 ) ≥ 1.
In the affirmative for one such pair we return 'Yes', otherwise we return 'No'.

As there are O(n k1+k2+2 ) possible such pairs, the algorithm runs in polynomial time. Its validity follows from Corollary 3.5.

Theorem 3.7 Deciding whether a digraph has an (out-branchable,

δ ≥ 1)-[k 1 , k 2 ]-partition (resp. (in-branchable, δ ≥ 1)-[k 1 , k 2 ]-partition) is polynomial-time solvable.
Proof: By directional duality, it suffices to prove that the (out-branchable,

δ ≥ 1)-[k 1 , k 2 ]-partition problem is polynomial-time solvable.
Let D be a digraph. We shall describe a polynomial-time procedure that, given a set U 1 of k 1 vertices such that D U 1 is out-branchable, decides whether there is an (out-branchable,

δ ≥ 1)- [k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 )
. Then taking the O(n k1 ) k 1 -subsets of V (D), one after another checking whether D U 1 is out-branchable, and if yes running this procedure, we obtain the desired algorithm. Note that the condition V 1 ⊆ Reach + (U 1 ) and the fact that D U 1 is out-branchable implies that D V 1 has an out-branching with root in U 1 .

The procedure proceeds as follows. Let U 1 be a set of k 1 vertices such that D U 1 has an outbranching B + 1 . Let S be the set of isolated vertices in D -U 1 . If each vertex of S has in-degree at least 1, and |D -(U 1 ∪ S)| ≥ k 2 , we return 'Yes'. Otherwise we return 'No'.

The procedure clearly runs in polynomial time. Let us now prove that it is valid. Observe first that in any (out-branchable,

δ -≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 ), the vertices of S cannot be in V 2 because their degree in D -U 1 is 0. Hence V 2 ⊆ V (D) \ (U 1 ∪ S), so |D -(U 1 ∪ S)| ≥ k 2 .
Moreover, all vertices of S must be in V 1 . So they must have an in-neighbour (in the path from U 1 to them) and so they must have in-degree at least 1. Hence when the procedure returns 'No', there is no (out-branchable,

δ -≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 ).
Assume now that each vertex of S has in-degree at least 1, and |D -

(U 1 ∪ S)| ≥ k 2 .
The procedure returns 'Yes'. Let us show that this is valid. Each vertex s of S has in-degree at least 1. Since it is isolated in D -U 1 its in-neighbours in D are in U 1 . Hence one can extend B + 1 into an out-branching of W 1 = V 1 ∪ S by adding S and one arc entering s for each vertex s ∈ S. Now all vertices of W 2 = V (D) \ (U 1 ∪ S) have degree at least 1 in D -U 1 , and thus also in D W 2 , because the vertices of S are isolated. Hence

δ(D W 2 ) ≥ 1. Therefore, since |W 2 | ≥ k 2 , (W 1 , W 2 ) is an (out-branchable, δ -≥ 1)-[k 1 , k 2 ]-partition with U 1 ⊆ W 1 ⊆ Reach + (U 1 ). Theorem 3.8 Deciding whether a digraph has an (out-branchable, connected)-[k 1 , k 2 ]-partition (resp. (in-branchable, connected)-[k 1 , k 2 ]-partition) is polynomial-time solvable.
Proof: Again it suffices to describe a polynomial-time algorithm that given a digraph D decides whether it has an (out-branchable, connected)-[k 1 , k 2 ]-partition is polynomial-time solvable.

Let D be a digraph. We shall describe a polynomial-time procedure that, given a set U 1 of k 1 vertices such that D U 1 is out-branchable, decides whether there is an (out-branchable, connected)-

[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 )
. Then taking the O(n k1 ) k 1 -subsets of V (D), one after another checking if D U 1 is out-branchable, and if yes running this procedure, we obtain the desired algorithm.

The procedure proceeds as follows. Let U 1 be a set of k 1 vertices such that D U 1 is out-branchable. We compute the connected components of D -U 1 . For each such component C we check whether |C| ≥ k 2 and Reach + D-C (U 1 ) = V (D -C). In the affirmative for one of the components, we return 'Yes', otherwise we return 'No'.

The procedure clearly runs in polynomial time. Let us now prove that it is valid. We need to prove that D has an (out-branchable, connected)

-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 ) if and only if there exists a connected component C of D -U 1 such that |C| ≥ k 2 and Reach + D-C (U 1 ) = V (D -C).
Assume first that there exists a connected component

C of D -U 1 such that |C| ≥ k 2 and Reach + D-C (U 1 ) = V (D -C). Since U 1 ⊆ V (D -C), we have |V (D -C)| ≥ k 1 . Moreover, as Reach + D-C (U 1 ) = V (D -C) and U 1 is out-branchable, by Lemma 2.1, D -C is out-branchable. Hence (V (D -C), V (C)) is an (out-branchable, connected)-[k 1 , k 2 ]-partition with U 1 ⊆ V (D -C) ⊆ Reach + (U 1 ). Assume now that D has an (out-branchable, connected)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 ). Since D V 2 is a connected subgraph of D -U 1 , it is contained in a connected component C of D -U 1 . Thus |C| ≥ |V 2 | ≥ k 2 . Now V (D -C) ⊆ V 1 . Let v be a vertex of D -C. As V 1 ⊆ Reach + (U 1 ), there is a (U 1 , v)-path in D. Observe that since C is a connected component of D -U 1 , a shortest (U 1 , v)-path contains no arc in C. Therefore v ∈ Reach + D-C (U 1 ). Hence Reach + D-C (U 1 ) = V (D -C
) and the algorithm above correctly answers 'Yes'.

Theorem 3.9 Deciding whether a digraph has an (out-branchable,

δ -≥ 1)-[k 1 , k 2 ]-partition ((in- branchable, δ + ≥ 1)-[k 1 , k 2 ]-partition) is polynomial-time solvable.
Proof: It suffices to describe a polynomial-time algorithm that given a digraph D decides whether it has an (out-branchable,

δ -≥ 1)-[k 1 , k 2 ]-partition is polynomial-time solvable.
Observe that if the digraph has such a partition, then every vertex except possibly one (the root of the out-branching) has in-degree at least 1. Hence if D has more than one vertex with in-degree 0, we return 'No'. Henceforth we may assume that all vertices except possibly one, denoted by s, have in-degree at least 1.

We shall describe a procedure that given a set U 1 of k 1 vertices, containing s if it exists, and such that D U 1 is out-branchable, decides whether there is an (out-branchable,

δ -≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 )
. Then taking the O(n k1 ) possible such U 1 one after another and running this procedure, we obtain the desired algorithm.

The procedure proceeds as follows. We initialize W 1 := U 1 . As long as there is a vertex v with in-degree 0 in D -U 1 , we add it to W 1 . This is valid as such vertices v cannot be in V 2 in a desired partition (V 1 , V 2 ). Observe moreover that each time we add such a v, it has in-degree at least 1 in D, because it is not s. Hence, there is an arc from W 1 to v. So by Lemma 2.1, at each step D W 1 is out-branchable. This process will terminate with either δ

-(D -W 1 ) ≥ 1 or D -W 1 is empty. If |D -W 1 | ≥ k 2 , then we return 'Yes', because (W 1 , V (D)\W 1 ) is an (out-branchable, δ -≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 ). If |D -W 1 | < k 2 , then we return 'No'. Indeed for every (out-branchable, δ -≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 ⊆ Reach + (U 1 ), the set V 1 must contain W 1 , so V 2 ⊆ V (D -W 1 ) so k 2 ≤ |V 2 | ≤ |D -W 1 | < k 2 .
Hence no such partition exists. Theorem 3.10 Deciding whether a digraph has an (out-branchable,out-branchable

)-[k 1 , k 2 ]-partition ((in-branchable, in-branchable)-[k 1 , k 2 ]-partition) is polynomial-time solvable.
Proof: An s-out-tree with at least k vertices clearly contains as an induced subdigraph an sout-tree with exactly k vertices. Hence, by Lemma 2.1, D has an (out-branchable, out-branchable

)- partition (V 1 , V 2 ) such that |V i | ≥ k i and D V i is out-branchable for i = 1, 2 if and only if D contains two vertex-disjoint out-trees T 1 , T 2 such that |V (T 1 )| = k 1 , |V (T 2 )| = k 2 and Reach + D (V (T 1 )∪V (T 2 )) = V (D)
. Thus, by trying, for (at most) all possible choices of disjoint vertex sets X 1 , X 2 with |X i | = k i whether D X 1 and D X 2 are out-branchable and Reach

+ D (X 1 ∪ X 2 ) = V (D), we can decide in polynomial time (since k 1 , k 2 are constants) whether D has an (out-branchable, out-branchable)- [k 1 , k 2 ]-partition. Theorem 3.11 Deciding whether a digraph has a (connected, δ ≥ 1)-[k 1 , k 2 ]-partition is polynomial- time solvable.
Proof: Let us describe a polynomial-time algorithm that given a digraph D decides whether it has a (connected,

δ ≥ 1)-[k 1 , k 2 ]-partition.
Observe that if D has an isolated vertex v, then necessarily v must be in the connected part of a (connected, δ ≥ 1)-partition, and so {v} must be the connected part. Henceforth, if k 1 ≥ 2, we return 'No', and if k 1 = 1 we check whether D -v is connected or not. In the affirmative, we return 'Yes', otherwise we return 'No'. Henceforth, we may assume that D has no isolated vertices.

We shall describe a procedure that given a set

U 1 of k 1 vertices such that D U 1 is connected, decides whether there is a (connected, δ ≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 .
Since every connected graph of order at least k 1 contains a connected subdigraph of order exactly k 1 , taking the O(n k1 ) U 1 sets of order k 1 , checking if they are connected and in the affirmative running this procedure, we obtain the desired algorithm.

The procedure proceeds as follows. We initialize W 1 := U 1 . As long as there is a vertex v with degree 0 in D -W 1 , we add it to W 1 . This is valid as

such vertices v cannot be in V 1 in a desired partition (V 1 , V 2 ). Observe moreover that each time we add such a v, it has a neighbour in W 1 , because it is not isolated in D. So, at each step D W 1 is connected. Once at this stage, δ(D -W 1 ) ≥ 1 or D -W 1 is empty. If |D -W 1 | ≥ k 2 , then we return 'Yes', because (W 1 , V (D) \ W 1 ) is a (connected, δ ≥ 1)-[k 1 , k 2 ]-partition with U 1 ⊆ W 1 . If |D -W 1 | < k 2 , then we return 'No'. Indeed for every (connected, δ ≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) with U 1 ⊆ V 1 , the set V 1 must contain W 1 . Hence V 2 ⊆ V (D -W 1 ) so k 2 ≤ |V 2 | ≤ |D -W 1 | < k 2 .
Hence no such partition exists. If there is a vertex v with out-degree at least 2, then applying applying the induction to D \ a for any arc a leaving v, we obtain the result. So we may assume that d

+ (v) = 1 for all v ∈ V (D).
If there is a vertex v with in-degree 0, then δ + (D -v) ≥ 1. By the induction hypothesis the result holds for D -v and so for D. Henceforth, we may assume that d

-(v) ≥ 1 for all v ∈ V (D). Since d + (v) = 1 for all v ∈ V (D), and v∈V (D) d + (v) = v∈V (D) d -(v), we have d + (v) = d -(v) = 1 for all v ∈ V (D).
Consequently, D is the disjoint union of directed cycles. Let C 1 , . . . , C p be those cycles, with

|C 1 | ≥ • • • ≥ |C p |. Let q be the smallest integer such that q i=1 |C i | ≥ k. If q = 1, then C 1 is a cycle of length at least k and (i) holds. If q ≥ 2, then |C q | ≤ |C 1 | ≤ k -1 and q-1 i=1 |C i | ≤ k -1. Thus q i=1 |C i | ≤ 2k -2. Then D = q i=1 C i satisfies δ + (D ) ≥ 1 and |D | ≤ 2k -2, so (ii) holds.
We shall now prove that the (δ

+ ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition problem is polynomial-time solvable. By directional duality, this implies that the (δ -≥ 1, δ -≥ 1)-[k 1 , k 2 ]
-partition problem is polynomial-time solvable. In order to prove this result, we need some preliminary results. Lemma 3.13 Let k 1 and k 2 be two positive integers, and let D be a digraph with δ

+ (D) ≥ 1. D has a (δ + ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition if and only if one of its subdigraphs has a (δ + ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]- partition.
Proof: The necessity is trivial since D is a subdigraph of itself. Let us now prove the sufficiency.

Assume that a subdigraph of D has a (δ

+ ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition. Consider the largest subdigraph D of D that has a (δ + ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition (U 1 , U 2 ).
Suppose for a contradiction that D = D. Set S = V (D) \ V (D ). Then every vertex s ∈ S has no out-neighbour in U 1 otherwise D V (D ) ∪ {s} would have the (δ

+ ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition (U 1 ∪ {s}, U 2 ), a contradiction. Similarly, every s ∈ S has no out-neighbour in U 2 . It follows that D S has minimum out-degree 1. Hence (U 1 ∪ S, U 2 ) is a (δ + ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition of D, a contradiction.
Lemmas 3.12 and 3.13 immediately yield the following. (iv) D has two disjoint subdigraphs D 1 and

Corollary 3.14 A digraph D has a (δ + ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-
(ii) D has a subdigraph D 1 such that δ + (D 1 ) ≥ 1, k 1 ≤ |D 1 | ≤ 2k 1 -2, and D -D 1 has a directed cycle of length at least k 2 ; (iii) D has a subdigraph D 2 such that δ + (D 2 ) ≥ 1, k 2 ≤ |D 2 | ≤ 2k 2 -2,
D 2 such that δ + (D i ) ≥ 1 and k i ≤ |D i | ≤ 2k i -2 for i = 1, 2. A vertex v is said to be big if d + (v) ≥ 3, or d -(v) ≥ 3, or d + (v) = d -(v) = 2.
The Directed Grid Theorem proved by Kawayarabashi and Kreutzer [START_REF] Kawarabayashi | The directed grid theorem[END_REF] implies the following (See [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF].). Theorem 3.15 Let F be a planar digraph with no big vertices. Deciding whether a given digraph contains a subdivision of F is polynomial-time solvable. Theorem 3.16 Let k 1 and k 2 be two positive integers. Deciding whether a digraph has a (δ

+ ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition is polynomial-time solvable.
Proof: We rely on Corollary 3.14. In fact, we show that each of the statement (i)-(iv) can be checked in polynomial time.

The fact that (i) can be checked in polynomial time follows from Theorem 3.15. It suffices to apply it to the disjoint union of a directed cycle of length k 1 and a directed cycle of length k 2 , which is clearly a planar graph with no big vertices.

(ii) To check (ii), we proceed as follows. For every set S such that k 1 ≤ |S| ≤ 2k 1 -2, we check whether δ + (D S ) ≥ 1 and D -S contains a directed cycle of length at least k 2 , which can be done by Theorem 3. [START_REF]Partition of graphs with condition on the connectivity and minimum degree[END_REF]. If the answer is 'Yes' for one such S, then we return 'Yes', otherwise we return 'No'. Checking whether δ + (D S ) ≥ 1 can be one in constant time since S has bounded size, and as there are O(n 2k1-2 ) possible sets S 1 , the procedure runs in polynomial time.

(iii) can be checked in the same way as (ii) (iv) can be checked in time O(n 2k1+2k2-4 ) by brute force. For each pair of disjoints sets S 1 and

S 2 such that k 1 ≤ |S 1 | ≤ 2k 1 -2 and k 2 ≤ |S 2 | ≤ 2k 2 -2, we check whether δ + (D S 1 ) ≥ 1 and δ + (D S 2 ) ≥ 1.
Each check can be done in constant time and there are O(n 2k1+2k2-4 ) possible pairs of sets (S 1 , S 2 ).

Polynomial [1,k]-partition problems

We now deal with those cases where the one vertex graph satisfies one of the two properties and where this implies that the [1,k]-versions of the partition problem are polynomial-time solvable while the [k 1 , k 2 ]-partition version are NP-complete for k 1 ≥ 2. The NP-completeness proofs will be given in the next subsection. Proposition 3.17 Let k be a positive integer. Deciding whether a digraph has a (strong, out-

branchable)-[1, k]-partition (resp. (strong, in-branchable)-[1, k]-partition) is polynomial-time solvable.
Proof: By the remark above, it suffices to describe a polynomial-time algorithm that decides whether a digraph D has a (strong, out-branchable)-[1, k]-partition.

Let D be a digraph. If |D| < k + 1, then the answer is clearly 'No'. Henceforth, we may assume that |D| ≥ k + 1.

Observe that the strong part of a (strong, out-branchable)-partition is contained in a strong component of D and that its out-branchable part contains vertices of at most one initial strong component. In particular, a digraph with a (strong, out-branchable)-partition has at most two initial strong components.

We compute the strong components of D.

• If D has more than two initial strong components, then we return 'No'.

• If D has two initial components C 1 and C 2 , then by the above observation, the strong part of a (strong, out-branchable)-partition must be C 1 or C 2 . So for i = 1, 2, we check whether

(V (C i ), V (D -C i )) is a (strong, out-branchable)-[1, k]-partition.
• If a digraph D has a (strong, δ + ≥ 1)-partition, then it has at most one vertex with out-degree 0. Moreover, if it has such a vertex x, then either ({x}, V (D) \ {x}) is a (strong, δ + ≥ 1)-[1, k]-partition or x is the unique out-neighbour of some vertex y = x in which case D is a 'No'-instance.

So we may assume that δ + (D) ≥ 1. For every vertex x, we check whether δ + (D -x) ≥ 1. In the affirmative for some x, then we return 'Yes' because ({x},

V (D) \ {x}) is a (strong, δ + ≥ 1)-[1, k]- partition.
Otherwise, δ + (D -x) = 0 for every x ∈ V (D). In that case, we claim that D is a disjoint union of directed cycles Z 1 , . . . , Z p , p ≥ 1. Indeed, consider a spanning subdigraph D such that d + D (v) = 1 for every vertex v. D contains no vertex x with in-degree 0 because δ + (D -x) = 0. Hence D is the disjoint union of cycles Z 1 , . . . , Z p . Now there is no arc uv in A(D)\A(D ) for otherwise δ + (D -x) = 0 for x the out-neighbour of u in D . This proves our claim. Consequently D is a 'Yes'-instance if and only if one of the Z j has length at most |D| -k, which can be checked in linear time. • If D has more than two connected components, then it is clearly a 'No'-instance, so we return 'No'.

• If D has exactly two connected components C 1 and C 2 , then the only possible (strong,connected)partition of D are (V (C 1 ), V (C 2 )) and (V (C 2 ), V (C 1 )). Hence D is a 'Yes'-instance if and only if one of these two partition is a (strong,connected)-[1, k]-partition, which can be checked in linear time.

• If D is connected, then for any leaf s of a spanning tree of V (D), we have ({x}, V (D) \ {x}) is a (strong,connected)-[1, k]-partition. So we return 'Yes'.

The algorithm is similar for the (strong, δ ≥ 1)-partition problem. If |D| < k + 1, then the answer is clearly 'No'. Henceforth, we may assume that |D| ≥ k + 1. We determine the isolated vertices of D.

• If D has two or more isolated vertices, then D is clearly a 'No'-instance, so we return 'No'.

• If D has precisely one isolated vertex x, then ({x}, V (D)\{x}) is a (strong, δ ≥ 1)-[1, k]-partition, so we return 'Yes'.

• Assume now D has no isolated vertex, that is δ(D) ≥ 1. If D has a connected component C with at least 3 vertices, then for any leaf x of a spanning tree of C, ({x}, V (D) \ {x}) is a (strong, δ ≥ 1)-[1, k]-partition, so we return 'Yes'. Otherwise, all connected components of D have order 2. In such a case D is a 'Yes'-instance if and only if |D| ≥ k + 2 and one its components is strong (i.e. a directed 2-cycle). This can be easily checked in linear time.

NP-complete cases

All the NP-completeness proofs below are variations of the same idea. They are based on ring digraphs which we define below.

Variants of 3-SAT used in the proofs

Let us recall the definition of the 3-SAT problem(s): An instance is a boolean formula

F = C 1 ∧ C 2 ∧ . . . ∧ C m over the set of n boolean variables x 1 , . . . , x n . Each clause C i is of the form C i = ( i,1 ∨ i,2 ∨ i,3
) where each i,j belongs to {x 1 , x 2 , . . . , x n , x1 , x2 , . . . xn } and xi is the negation of variable x i . Our NP-completeness proofs will use reductions from the 3-SAT problem and the two following variants of the 3-SAT problem: a) 2-IN-3-SAT, where exactly two of the three literals in each clause should be safisfied; and b) NOT-ALL-EQUAL-3-SAT (NAE-3-SAT), where every clause must have at least one true and at least one false literal. These variants are both NP-complete [START_REF] Schaefer | The complexity of satisfiability problems[END_REF].

In all of the NP-completeness proofs below we will use the following easy fact: for any pair of fixed integers k, k and any given instance F of 3-SAT, 2-IN-3-SAT or NAE-3-SAT, we can always add new variables and clauses whose number only depends on k, k such that the resulting formula F has at least max{k, k } clauses and at least max{k, k } variables and F is satisfiable if and only if F is satisfiable. In all the proofs below we may hence assume that the 3-SAT instances that we use in the reductions satisfy that min{n, m} ≥ max{k 1 , k 2 }, where k 1 , k 2 are the lower bounds on the two sides of the partition. It will be clear from the proofs that this ensures that the partitions (V 1 , V 2 ) that we obtain from a satisfying truth assignment will always satisfy that |V i | ≥ k i for i = 1, 2.

Ring digraphs and 3-SAT

A ring digraph (see Fig. 1) is the digraph that one obtains by taking two or more copies of the complete bipartite digraph on four vertices {a 1 , a 2 , b 1 , b 2 } and arcs {a 1 b 1 , a 1 b 2 , a 2 b 1 , a 2 b 2 } and joining these in a circular manner by adding a path P i,1 from the vertex b i,1 to a i+1,1 and a path P i,2 from b i,2 to a i+1,2 where b i,1 is the ith copy of b 1 etc and indices are 'modulo' n (b n+1,j = b 1,j for j ∈ [2] etc). Ring digraphs form an important structure in many of our NP-completeness proofs below.

We start by showing how we can associate a ring digraph to a given 3-SAT formula. Let F = C 1 ∧ C 2 ∧ . . . ∧ C m be an instance of 3-SAT consisting of m clauses C 1 , . . . , C m over the same set of n boolean variables x 1 , . . . , x n .

For each variable x i the ordering of the clauses above induces an ordering of the occurrences of x i , resp xi in the clauses. Let q i (resp. p i ), i ∈ [n], denote the number of times x i (resp. xi ) occurs in the clauses Let R(F) = (V, A) be the ring digraph defined as follows. Its vertex set is

V ={a 1,1 , . . . a n,1 , a 1,2 . . . , a n,2 }∪ {b 1,1 , . . . , b n,1 , b 1,2 , . . . , b n,2 }∪ n i=1 {v i,0 , v i,1 , . . . , v i,qi+1 , v i,0 , v i,1 , . . . , v i,pi+1 }
Its arc set A consists of the following arcs:

a1,2 a1,1 b1,2 b1,1 v 1,1 v1,1 v1,2 a2,2 a2,1 b2,2 b2,1 v 2,1 v2,1 v2,2 a3,2 a3,1 b3,2 b3,1 v 3,1 v3,1 v3,2 a4,2 a4,1 b4,2 b4,1 v 4,1 v4,1 v4,2 Figure 1: A ring digraph • n i=1 {a i,1 b i,1 , a i,1 b i,2 , a i,2 b i,1 , a i,2 b i,2 } (the directed complete bipartite graphs) • the arcs of the paths P i,1 , P i,2 , i ∈ [n] where P i,1 = b i,1 v i,0 v i,1 . . . v i,qi+1 a i+1,1 and P i,2 = b i,2 v i,0 v i,1 . . . v i,pi+1 a i+1,2
, where a n+1,j = a 1,j for j = 1, 2.

For 1 ≤ j ≤ m, we associate to the jth clause C j = ( j,1 ∨ j,2 ∨ j,3 ) the set W j consisting of three vertices of R(F) representing the occurrences of the literals of C j in F: if j,1 = x i for some i ∈ [n] and this is the rth occurrence of x i in the clauses, then W j contains the vertex v i,r . If j,1 = xi for some i ∈ [n] and this is the rth occurrence of xi in the clauses, then W j contains the vertex v i,r . The other two vertices of W j are defined similarly.

The following observation which forms the base of many of our proofs is easy to prove (for a proof of result a very similar to this see [7, Claim 1]).

Theorem 4.1 Let F be a 3-SAT formula and let R(F) be the corresponding ring digraph. Then the following holds:

• R(F) contains a directed cycle which intersects all the sets W 1 , . . . , W m if and only if F is a 'Yes'-instance of 3-SAT.

• R(F) contains two disjoint directed cycles R 1 , R 2 , each of which intersects all the sets W 1 , . . . , W m if and only if F is a 'Yes'-instance of NAE-3-SAT.

The reductions

In our proofs we shall use different superdigraphs of the ring digraph R(F) for a given 3-SAT formula.

It will be clear from their definitions that each of these digraphs can be constructed in polynomial time in the size of the given 3-SAT instance F. Thus in the proofs below we will not mention that the reductions are polynomial but only prove the correctness of the reductions.

We group together those problems for which the same polynomial reduction works. Note that each time we state two problems, they are equivalent in terms of complexity by reversing all arcs in the digraphs. Below, we only consider the first part of those claims.

i) (strong, connected)-[k 1 , k 2 ]-partition for k 1 ≥ 2 and k 2 ≥ 1, (ii) (strong, δ ≥ 1)-[k 1 , k 2 ]-partition for k 1 ≥ 2 and k 2 ≥ 1, (iii) (strong, δ -≥ 1)-[k 1 , k 2 ]-partition and (strong, δ + ≥ 1)-[k 1 , k 2 ]-partition for k 1 ≥ 2 and k 2 ≥ 1, (iv) (δ 0 ≥ 1, δ -≥ 1)-[k 1 , k 2 ]-partition and (δ 0 ≥ 1, δ + ≥ 1)-partition for k 1 , k 2 ≥ 1, (v) (δ 0 ≥ 1, δ ≥ 1)-[k 1 , k 2 ]-partition for k 1 , k 2 ≥ 1, (vi) (δ + ≥ 1, δ ≥ 1)-[k 1 , k 2 ]-partition and (δ -≥ 1, δ ≥ 1)-partition for k 1 , k 2 ≥ 1, (vii) (δ + ≥ 1, connected)-[k 1 , k 2 ]-partition and (δ -≥ 1,connected)-partition for k 1 , k 2 ≥ 1, and (viii) (δ 0 ≥ 1, connected)-[k 1 , k 2 ]-partition for k 1 , k 2 ≥ 1.
Proof: We show how to reduce 3-SAT to each of these problems. Let F = C 1 ∧ C 2 ∧ . . . ∧ C m be an instance of 3-SAT consisting of clauses C 1 , . . . , C m over n boolean variables x 1 , . . . , x n . By the remark in Section 2, we may assume that n, m ≥ max{k 1 , k 2 }.

The digraph R 1 (F) is obtained from R(F) with the following modifications:

• For all i ∈ [n], add a new vertex d i and two arcs a i,1 d i , a i,2 d i .

• For all j ∈ [m], add a new vertex c j and all arcs from W j to c j .

We shall use the digraph R 1 (F) in all the proofs. We only give the full details in the proof of (i) as all the other proofs are very similar.

We show that R 1 (F) has a (strong,connected)-[k 1 , k 2 ]-partition if and only if F is satisfiable. First observe that, for all i ∈ [n], every strong subdigraph S of D of order at least 2 contains at least one vertex in {a i,1 , a i,2 } and at least one in {b i,1 , b i,2 } since each of these sets is a cycle transversal (kills all directed cycles) of D. Also no strong subdigraph can contain any of the vertices d 1 , . . . , d n , c 1 , . . . , c m as these all have out-degree zero. Every strong subdigraph S contains either all or none of the internal vertices of P i,1 and similarly for P i,2 for i ∈ [n]. Furthermore, if some strong subdigraph S contained both P i,1 and P i,2 for some i ∈ [n], then D -S would not be connected since the vertex

d i would be isolated. So, if (V 1 , V 2 ) is a (strong, connected)-[k 1 , k 2 ]-partition of R 1 (F), then, for all i ∈ [n], either V (P i,1 ) ⊆ V 1 and V (P i,2 ) ⊆ V 2 , or V (P i,1 ) ⊆ V 2 and V (P i,2 ) ⊆ V 1 . Suppose now that D has a (strong,connected)-[k 1 , k 2 ]-partition (V 1 , V 2 )
. Let φ : {x 1 , . . . , x n } → {true, f alse} be the truth assignment defined by φ(x i ) = true whenever D V 1 does not contain the path P i,1 (in which case, it contains P i,2 ). Since the vertex c j , j ∈ [m] belongs to the connected digraph D V 2 , at least one of the three paths that c j is connected to (via the arcs from W j ) is not in D V 1 , implying that C j is satisfied by φ and we have a satisfying truth assignment. For the other direction, starting from a satisfying truth assignment φ for F, we simply form V 1 by putting V (P i,2 ) in V 1 if t(x i ) = f alse and otherwise we put V (P i,1 ) in V 1 . In both cases, exactly one of the four arcs from {a i,1 , a i,2 } to {b i,1 , b i,2 } belongs to D V 1 and these link up the paths we put in

D V 1 so that D V 1 is, in fact, an induced directed cycle. Set V 2 = V (D) \ V 1 .
It is easy to see that D V 2 is connected, and that both V 1 and V 2 have size at least n ≥ max{k 1 , k 2 }. This completes the proof of (i).

The proofs of (ii) and (iii) are very similar to the proof above: in every desired 2-partition (V 1 , V 2 ) all the vertices d 1 , . . . , d n , c 1 , . . . , c m must belong to V 2 . Now, if both of a i,1 , a i,2 were in V 1 , then d i would be an isolated vertex in D V 2 and if they were both in V 2 , then D V 1 would not be strong.

So exactly one of a

i,1 , a i,2 is in V 1 for every i ∈ [n]. This again implies that precisely one of b i,1 , b i,2 is in V 1 for each i ∈ [n].
Hence again, if we let vertices of the path P i,2 be in V 1 if and only if x i is true and conversely, we see that F is satisfiable if and only if we have the desired 2-partition.

The proofs of (iv)-(viii) are also almost identical to the proof above. It suffices to note that the part V 1 which should satisfy δ 0 ≥ 1, respectively δ + ≥ 1 plays the same role as the strong part V 1 did above, because if D V 1 has minimum out-degree or minimum semi-degree at least 1, then |V 1 | ≥ 2. Note that once we have put the vertex a i,g , g ∈ [2] in V 2 , all the vertices of P i-1,g must also be in V 2 since they have no out-neighbours left in V (D) \ V 2 .

Theorem 4. [START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF] The following 2-partition problems are NP-complete.

• add new vertices {s, s , t, t , x , y } ∪ {c 1 , . . . , c m , c1 , . . . , cm };

• add new arcs {ss , sb 1,1 , sb 1,2 , x b 1,1 x b 1,2 , t t, a 1,1 t, a 1,2 t, a 1,1 y , a 1,2 y } ∪ ( j∈[m] {c j v, vc j | v ∈ W j }).
We shall show that the digraph R 4 (F) has an (out-branchable,in-branchable)-[k 1 , k 2 ]-partition if and only if F is a 'Yes'-instance of NAE-3-SAT.

By construction of R 4 (F), for any (out-branchable,in-branchable

)-[k 1 , k 2 ]-partition (V 1 , V 2 ) of R 4 (F)
, we have that t ∈ V 2 and s ∈ V 1 . Thus the vertex s (resp. t) must be the root of the outbranching (resp. in-branching) in D V 1 (resp. D V 2 ). Furthermore, we must have x ∈ V 2 , y ∈ V 1 and for eevry j ∈ [m], c j ∈ V 2 and cj in V 1 . Consequently, for each i ∈ [n] exactly one of the vertices a i,1 , a i,2 and exactly one of the vertices b

i,1 , b i,2 is in V 1 (resp. V 2 ) (D V 1 contains
a path from s to y and D V 2 contains a path from x to t). Combined with the distribution of the clause vertices this implies that each of

D V 1 , D V 2 contains a directed path from {b 1,1 , b 1,2 } to {a 1,1 , a 1,2
} which intersect all the sets W 1 , . . . , W m . Now the result follows from Theorem 4.1.

Theorem 4.6 Let k 1 , k 2 be two positive integers. The following partition problems are all NPcomplete:

(A) (δ 0 ≥ 1, δ 0 ≥ 1)-[k 1 , k 2 ]-partition, (B) (strong, δ 0 ≥ 1)-[k 1 , k 2 ]-partition, (C) (strong, strong)-[k 1 , k 2 ]-partition. Proof: Let F = C 1 ∧ C 2 ∧ . . . ∧ C m
be an instance of 3-SAT consisting of clauses C 1 , . . . , C m over n boolean variables x 1 , . . . , x n . We may assume that every variable x i appears in some clause as the literal x i and in some other clause as the literal xi and no variable appears twice in the same clause (negated or not). Clauses of the last kind can be removed and if x i does not appear, say, as literal x i we can add two clauses C(x i ) = (x i ∨ y i ∨ y i ), C (x i ) = (x i ∨ ȳi ∨ ȳ i ) to F where y i , y i are new variables only used in these two clauses. Clearly the new formula is satisfiable if and only if the old one is.

Let R 5 (F) be the digraph obtained from R(F) by

• adding new vertices {s, t, t , t , α, α , α , β, β , β } ∪ {c 1 , . . . , c m } ∪ {c 1 , . . . , c m } ∪ {c 1 , . . . , c m }, and

• adding new arcs {sb 1,1 , sb 1,2 , tb 1,1 , tb 1,2 , a 1,1 α , α α , α α, a 1,2 β , β β , β β, αs, αt , βs, βt , t t , t t}∪

( j∈[m] {sc j , c j c j , c j c j }) ∪ ( j∈[m] {c j v | v ∈ W j }).
We first show that the digraph R 5 (F) represents a reduction from 3-SAT to the (δ 0 ≥ 1, c m ,c m ,c m and s belong to the same set V i because every path into a clause vertex c j goes through the vertex s and uses the path sc j c j c j . W.l.o.g. i = 1. Starting from b n,1 , b n,2 we see that these vertices must belong to different sets of the partition: if they belong to the same set V j , then first observe that we would have V (P n,1 ), V (P n,2 ) ⊆ V 2 since b n,1 , b n,2 have out-degree at least 1 in D V 2 . Now, arguing backwards, we first see that all vertices of P n-1,1 , P n-1,2 must also be in V j and then that all vertices of P n-2,1 , P n-2,2 must belong to V j and so on, implying that all vertices of the ring subdigraph R(F) are in V j . But then, one after another in the following order, α , α , α, β , β , β, s, t , t , t are also in V j because all their in-neighbours are in V j . Hence j = 1 and V 2 = ∅, a contradiction. Hence b n,1 , b n,2 are in different sets and together with our assumption that

δ 0 ≥ 1)- [k 1 , k 2 ]-partition problem. Note that for every (δ 0 ≥ 1, δ 0 ≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ) of R 5 (F) all the vertices c 1 , c 1 , c 1 . . . ,
s ∈ V 1 this easily implies that t, t , t ∈ V 2 . Hence (V 1 , V 2 ) is a (δ 0 ≥ 1, δ 0 ≥ 1)-[k 1 , k 2 ]-partition if and only if V 1 contains precisely one of the paths P i,1 , P i,2 for each i and V 1 ∩ W j = ∅ for each j ∈ [m]. By Theorem 4.1, this implies that R 5 (F) has a (δ 0 ≥ 1, δ 0 ≥ 1)-[k 1 , k 2 ]-partition if and only if F is satisfiable.
Note that a strong digraph D has minimum semi-degree 1, unless it has order 1. Observe moreover that all (δ 0 ≥ 1, δ 0 ≥ 1)-partitions described above are also (strong, strong)-partitions. Hence to prove (B) and (C) we just need to prove that R 5 (F) has no (strong, δ 0 ≥ 1)-partition in which the strong part has cardinality 1. In other words, we need to prove that δ 0 (R 5 (F) -x) = 0 for every vertex x ∈ V (R 5 (F)).

Suppose for a contradiction that there is a vertex x such that δ 0 (R 5 (F) -x) ≥ 1. Then x must be a vertex of the ring subdigraph R(F): indeed deleting s leaves each c j with in-degree 0, deleting t leaves t with out-degree 0, deleting α (resp. β, t ) leaves α (resp. β , t ) with out-degree 0, deleting t , (resp. α , β , α , β ) leaves t , (resp. α , β , α , β ) with degree 1, and finally deleting one of the vertices c j , c j , c j clearly leaves a vertex of degree 1. So x must be a vertex on one of the paths P i,j , i ∈ [n], j ∈ [2] of R(F). But then either the predecessor of x on P i,j has out-degree 0 in R 5 (F) -x, or its successor on P i,j has in-degree 0 in R 5 (F) -x. Here we used that the vertices v i,0 , v i,qi+1 , v i,0 , v i,pi+1 have degree 2 in R(F), because p i , q i ≥ 1 since both literals x i and xi appear at least once in the clauses.

Theorem 4.7 The following 2-partition problems are NP-complete.

(i) (δ + ≥ 1, δ -≥ 1)-[k 1 , k 2 ]-partition for k 1 , k 2 ≥ 1; (ii) (strong, δ + ≥ 1)-[k 1 , k 2 ]-partition and (strong, δ -≥ 1)-[k 1 , k 2 ]-partition for k 1 ≥ 2 and k 2 ≥ 1; (iii) (δ 0 ≥ 1, δ + ≥ 1)-[k 1 , k 2 ]-partition and (δ 0 ≥ 1, δ -≥ 1)-[k 1 , k 2 ]-partition for k 1 , k 2 ≥ 1.
Proof: We show how to reduce 3-SAT to each of these problems. Let

F = C 1 ∧ C 2 ∧ . . . ∧ C m be an instance of 3-SAT consisting of clauses C 1 , . . . , C m over n boolean variables x 1 , . . . , x n . The digraph R 6 (F) is obtained from R(F) by adding new vertices {c - 1 , . . . , c - m } ∪ {c + 1 , . . . , c + m } ∪ {a + , a -, b 1 , b 2 } and arcs ( j∈[m] {c + j v | v ∈ W j })∪( j∈[m] {vc - j | v ∈ W j })∪{c - j a -| j ∈ [m]}∪{a + c + j | j ∈ [m]} ∪ {a + b 1 , b 1 a -, a -b 2 , b 2 a + }.
We shall use the digraph R 6 (F) in all the proofs. We only give the full details in the proof of (i) as the two other proofs are very similar.

Let us prove that R 6 (F) has a (δ

+ ≥ 1, δ -≥ 1)-[k 1 , k 2 ]
-partition if and only if F is satisfiable. By Theorem 4.1, it suffices to prove that R 6 (F) has a (δ + ≥ 1, δ -≥ 1)-[k 1 , k 2 ]-partition if and only if R(F) has a directed cycle intersecting all the sets W 1 , . . . , W m .

Assume first that R 6 (F) has a (δ + ≥ 1, δ -≥ 1)-[k 1 , k 2 ]-partition. Observe that a + and a -are either both in V 1 or both in V 2 . Indeed if a + ∈ V 1 and a -∈ V 2 (resp. a + ∈ V 2 and a -∈ V 1 ) , then b 1 (resp. b 2 ) cannot be in any part. By reversing all arcs and interchanging k 1 , k 2 if necessary, we may assume that a -and a + are both in V 1 . Then every c

+ j ∈ V 1 because its unique in-neighbour is a + . Now D V 2 contains a directed cycle C 2 . But this cycle must be in the ring digraph R(F) because all directed cycles in R 6 (F) -{a + , a -} are in R(F). Consider C 1 = R(F) -C 2 . It is a directed cycle and V 1 ∩ R(F) ⊆ V (C 1 ). In particular, the out-neighbour of each c + j in D V 1 is in V (C 1 )
. Hence C 1 intersects all the sets W 1 , . . . , W m . Reciprocally, assume that there exists a directed cycle C 1 which intersects all the sets W 1 , . . . , W m . Set

V 2 = V (R(F)) \ V (C 1 ) and V 1 = V (R 6 (F)) \ V 2 . Clearly, D V 2 is a directed cycle and D V 1 is
strong (and thus has minimum out-degree at least 1) because it is covered by the directed cycles C 1 , (a + , b 1 , a -, b 2 , a + ) and the directed paths (a + , c + j , v, c - j , a -) for all j ∈ [m] and v ∈ W j . This proves (i)

The proofs of (ii) and (iii) are very similar. We just need to observe that a strong digraph with order at least 2 and every digraph with minimum semi-degree at least 1 contains a directed cycle.

The impact of strong connectivity

In this section, we revisit some of the NP-complete problems from the previous sections to see what happens in the strong case. Several of our NP-completeness proofs in the previous sections involved digraphs (e.g. R 1 (F)) which are very far from being strongly connected. For some of the proofs the digraphs in the reduction where in fact strong (e.g. R 5 (F) or R 6 (F) ), so it is natural to ask which of the problems remain NP-complete when we restrict to strongly connected digraphs.

There are many problems where demanding the input digraph to be strong changes the complexity from NP-complete to polynomial. One example is the problem of deciding whether the underlying graph of a digraph D contains two cycles C, C so that C is a directed cycle in D whereas C may not be a directed cycle. This problem was shown to be polynomial for strong digraphs in [START_REF] Bang-Jensen | On the problem of finding disjoint cycles and dicycles in a digraph[END_REF] and NP-complete for non-strong digraphs in [START_REF] Bang-Jensen | Vertex-disjoint directed and undirected cycles in general digraphs[END_REF]. Another example is the problem of deciding whether a digraph contains a spanning galaxy [START_REF] Concalves | On spanning galaxies in digraphs[END_REF].

Handle decompositions

Let D be a digraph. A handle h of D is a directed path (s, v 1 , . . . , v , t) from s to t or a directed cycle when

s = t, such that d -(v i ) = d + (v i ) = 1 for all 1 ≤ i ≤ .
The vertices s and t are the end-vertices of h while the vertices v i are its internal vertices. The set of internal vertices of h is denoted Int(h). The vertex s is the initial vertex of h and t its terminal vertex. The length of a handle is the number of its arcs, here + 1. A handle of length 1 is said to be trivial.

Given a strongly connected digraph D and a subdigraph D of D, a handle decomposition of D starting at D is a pair ((h i ) 1≤i≤p , (D i ) 0≤i≤p ), where (D i ) 0≤i≤p is a sequence of digraphs and (h i ) 1≤i≤p is a sequence of paths or cycles such that:

• D 0 = D ,
• for 1 ≤ i ≤ p, h i is a handle of D i and D i is the (arc-disjoint) union of D i-1 and h i , and

• D = D p .
A handle decomposition is uniquely determined by either D and (h i ) 1≤i≤p , or (D i ) 0≤i≤p . The number of handles p in any handle decomposition of D starting at D is exactly

|A(D)| - |A(D )| -|V (D)| + |V (D )|. Observe that p = 0 when D = D is a singleton and p = 1 when D is a directed cycle.
The following lemma is easy and well known (see e.g. [2, Section 5.3]).

Lemma 5.1 Let D be a strong digraph. For any subdigraph D , there exists a handle decomposition of D starting at D , say (h i ) 1≤i≤p , (D i ) 0≤i≤p ). Moreover, if D is strong, then D i is strong for all 0 ≤ i ≤ p.

5.2

Polynomial-time solvable problems for all k 1 , k 2 Lemma 5.2 Let D be a strong digraph, and let

P 1 ∈ {strong, δ + ≥ 1, δ -≥ 1, δ 0 ≥ 1} and P 2 ∈ {connected, δ ≥ 1}. If a subdigraph D of D admits a (P 1 , P 2 )-partition (V 1 , V 2 ), then D contains a (P 1 , P 2 )-partition (V 1 , V 2 ) such that V 1 ⊆ V 1 and V 2 ⊆ V 2 . Proof: Let (V 1 , V 2 ) be a (P 1 , P 2 )-partition of a subdigraph D of D. By Lemma 5.1, there is a handle decomposition ((h i ) 1≤i≤p , (D i ) 0≤i≤p ) of D starting at D . Set (X 0 , Y 0 ) = (V 1 , V 2 )
. Now for every i > 0, we can extend the (P

1 , P 2 )-partition (X i-1 , Y i-1 ) of D i-1 into a (P 1 , P 2 )-partition (X i , Y i ) of D i as follows: if an end-vertex of h i is in Y i-1 , then set (X i , Y i ) = (X i-1 , Y i-1 ∪ Int(h i )), otherwise h i avoids Y i-1 and we set (X i , Y i ) = (X i-1 ∪ Int(h i ), Y i-1
). This is trivially correct. Moreover, for all Proof:

1 ≤ i ≤ p, we have X i-1 ⊆ X i and Y i-1 ⊆ Y i . So V 1 ⊆ X p and V 2 ⊆ Y p . Hence (X p , Y p ) is the desired partition (V 1 , V 2 ) of D.
Assume that (V 1 , V 2 ) is a (P, connected)-[k 1 , k 2 ]-partition of D.
Trivially (by trimming leaves from a spanning tree), V 2 contains a subset V 2 of cardinality k 2 such that D V 2 is connected. Moreover, D -V 2 contains D V 1 , which has property P. Hence, in D -V 2 , the maximal subdigraph with property P containing all vertices of V 1 has size at least k 1 . Conversely, assume that there is a set V 2 with |V 2 | ≥ k 2 such that D V 2 is connected and D -V 2 has a maximal subdigraph D 1 with property P of size at least k

1 . Set V 1 = V (D 1 ). Then (V 1 , V 2 ) is a (P, connected)-[k 1 , k 2 ]-partition of D V 1 ∪ V 2 . Thus, by Lemma 5.2, (V 1 , V 2 ) can be extended into a (P, connected)-[k 1 , k 2 ]-partition (V 1 , V 2 ) of D with V 1 ⊆ V 1 and V 2 ⊆ V 2 . In particular, |V 1 | ≥ |V 1 | ≥ k 1 and |V 2 | ≥ |V 2 | ≥ k 2 .
Corollary 5.4 Let k 1 and k 2 be two positive integers and let P ∈ {strong, δ + ≥ 1, δ -≥ 1, δ 0 ≥ 1}. There is a O(n k2+2 ))-time algorithm that solves the (P, connected)-[k 1 , k 2 ]-partition problem for strong digraphs.

Proof: The algorithm proceeds as follows. For every set V 2 of size k 2 , we first check whether D V 2 is connected (This can be done in constant time). If not, we proceed to the next k 2 -subset. Assume now that D V 2 is connected. We use the O(n 2 )-time algorithm of [START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF]Lemma 2.2] In the very same way as Corollary 5.3 implied Corollary 5.4, Corollary 5.5 imply the following.

Corollary 5.6 Let k 1 and k 2 be two fixed positive integers, and let

P ∈ {strong, δ + ≥ 1, δ -≥ 1, δ 0 ≥ 1}.
There is a O(n k2+3 )-time algorithm that solves the (P, δ ≥ 1)-[k 1 , k 2 ]-partition problem for strong digraphs.

Assume first that R 7 (F) has an (out-branchable, strong)-

[k 1 , k 2 ]-partition (V 1 , V 2 ). Let B 1 be an out-branching of D V 1 . We claim that x ∈ V 1 . Indeed, all arcs of D -V (R(F)) are incident to x; hence if V 1 ∩ V (R(F)) = ∅, then V 1 necessarily contains x because |V 1 | ≥ 2 and D V 1 is connected. Now if there is a vertex y in V 1 ∩ V (R(F))
, then consider the (x, y)-bond with vertex set {x, y, z 1 , z 2 }. The two vertices z 1 and z 2 must be in V 1 because their out-degree in D -y is 0. One of the vertices z 1 , z 2 is not the root of B 1 and thus has an in-neighbour in B 1 . As it is the unique in-neighbour of z 1 and z 2 , vertex x is in V 1 . This proves our claim. Now the vertices of m j=1 {c j , c j } are in V 1 because their out-degree in D -x is 0, and for each y ∈ V (R(F)) all internal vertices of the (x, y)-bond are also in V 1 , because their in-degree in D -x is 0. Consequently, D V 2 is a subdigraph of R(F). Moreover, D V 2 is strong and of order at least 2, so it contains a directed cycle

D 2 . Let D 1 = R(F) -D 2 . Since R(F) is a ring digraph, D 1 is a directed cycle. In addition, V 1 ∩ V (R(F)) ⊆ V (D 1 )
. Now, for all j ∈ [m], one of the two vertices c j , c j is not the root of B 1 , and so has an in-neighbour in D 1 . Thus at least one vertex of W j is in V 1 . Consequently, D 1 intersects all the sets W 1 , . . . , W m .

Reciprocally, assume that there exists a directed cycle D 1 in R(F) which intersects all the sets

W 1 , . . . , W m . Set V 2 = V (R(F)) \ V (D 1 ) and V 1 = V (R 7 (F)) \ V 2 . Clearly, D V 2 is a directed cycle and D V 1 is
strong (and thus is out-branchable).

Theorem 5.12 Deciding whether a strong digraph has an (out-branchable,

δ + ≥ 1)-[k 1 , k 2 ]-partition (resp. (in-branchable, δ -≥ 1)-[k 1 , k 2 ]-partition) is NP-complete for all k 1 , k 2 ≥ 2.
Proof: The reduction is from 3-SAT, and we here assume that we are given an instance F consisting of m clauses C 1 , . . . , C m over n variables x 1 , .., x n and m clauses C 1 , ..., C m . As mentioned in Section 2, we may assume that min{n, m} ≥ max{k 1 , k 2 }. Furthermore, free to add copies of clauses, we may assume that every clause appears twice. We build a strong digraph D(F) starting from a circular strip on the vertices vertices {b i , b i }, 1 ≤ i ≤ n, where all arcs exist from {b Let us now prove that D(F) has an (out-branchable, δ + ≥ 1)-[k 1 , k 2 ]-partition if and only if F is satisfiable.

• A satisfying truth assignment to F yields a good bipartition, by putting in V 2 all the vertices of {s} ∪ {c 1 , . . . , c m }, as well as all b i (resp. b i ) such that x i (resp. x i ) is true. We then put in V 1 all b i (resp. b i ) such that x i (resp. x i ) is false. This easily extends in an (out-branchable,

δ + ≥ 1)-[k 1 , k 2 ]-partition of D(F).
• Assume now that D(F) has an (out-branchable,

δ + ≥ 1)-[k 1 , k 2 ]-partition (V 1 , V 2 ). Note that if b i+1 (resp. b i+1 ) is in V 1 ,
1 = x 1 ∨ x 2 ∨ x 3 and C 2 = x 5 ∨ x 6 ∨ x 7 thus one vertex in {b i , b i } is also in V 1 . This ensures that V 1 contains at least one of b i , b i for each i ∈ [n].
The first gadget ensures that s belongs to V 2 : suppose s ∈ V 1 , then all in-neighbours of s and then in turn all of i∈[n] {b i , b i } are in V 1 . By the remark above, this implies that every vertex of the second gadget is in V 1 . This implies that V 2 ⊆ {c 1 , . . . , c m }, a contradiction since this is an independent set in D(F). So s ∈ V 2 and this implies that all the c i vertices (except at most one) also belong to V 2 . Because each clause appears twice, at least one of the vertices corresponding to each such pair is in V 2 and has an out-neighbour in V 2 . Hence, assigning true to each variable x i such that b i ∈ V 2 and f alse to the other, we obtain a truth assignment satisfying F.

Theorem 5.13 Deciding whether a strong digraph has an (out-branchable, in-branchable

)-[k 1 , k 2 ]- partition is NP-complete for all k 1 , k 2 ≥ 2.
Proof: Reduction from 3-SAT. Let F = C 1 ∧ C 2 ∧ . . . ∧ C m be an instance of 3-SAT consisting of clauses C 1 , . . . , C m over n boolean variables x 1 , . . . , x n . Let R 8 (F) be the digraph obtained from R 6 (F) as follows. For each vertex v of V (R 6 (F)), we create two disjoint sets A + (v) and A -(v), each of three vertices. Hence

V (R 8 (F)) = V (R 6 (F)) ∪ v∈V (R6(F )) (A + (v) ∪ A -(v)
). R 8 (F)) has the following arcs: for each vertex v ∈ V (R 6 (F)), it contains all arcs from v to A + (v) and all arcs from A + (v) to N + R6(F ) (v). See Figure 4. Similarly, it contains all arcs from A -(v) to v and all arcs from

N - R6(F ) (v) to A -(v). v v 1 v 2 v 3 v 4 v 5 =⇒ v v 1 v 2 v 3 v 4 v 5 Figure 4: Constructing R 8 (F) from R 6 (F)
Let us first assume that R 8 (F) admits an (out-branchable, in-branchable)-

[k 1 , k 2 ]-partition (V 1 , V 2 ). Claim: If v ∈ V 2 , then at least one vertex of N + R6(F ) (v) also belongs to V 2 .
Proof of the claim: Assume to the contrary that all vertices of N + R6(F ) (v) are in V 1 . Then at most one vertex of A + (v) of the three central vertices can belong to V 1 , because an out-branchable digraph has at most one source. Thus, at least two of them belong to V 2 , which is impossible as the two of them would be sinks the in-branchable digraph induced by V 2 . Reciprocally, assume that F is satisfied by a truth assignment φ. Let (V 1 , V 2 ) be the (δ + ≥ 1, δ -≥ 1)-partition of R 6 (F) obtained as follows : let C 1 be a directed cycle C 1 which intersects all the sets W 1 , . . . , W m . (Such a cycle can be obtained from φ as shown in the proof of Theorem 4.7.) Set

Similarly to the claim, if

v ∈ V 1 , then at least one vertex of N - R6(F ) (v) also belongs to V 1 . Conse- quently, the partition (V 2 ∩ V (R 6 (F)), V 1 ∩ V (R 6 (F)) is a (δ + ≥ 1, δ -≥ 1)-partition of R 6 (F),
V 2 = V (R(F)) \ V (C 1 ) and V 1 = V (R 6 (F)) \ V 2 .
We now show that such a partition may be extended into an (out-branchable, in-branchable)-[k 1 , k 2 ]-partition (V 1 , V 2 ) of R 8 (F), by adding the vertex of the sets A + (v) and A -(v) appropriately: By construction R 6 (F) V 2 is a directed cycle and thus has an in-branching B -rooted at some vertex that we call r. Let r be the out-neighbour of r in R 6 (F) V 2 . Furthermore R 6 (F) V 1 is strong (see the proof of Theorem 4.7) and hence has an out-branching rooted at some vertex s. Let s be any in-neighbour of

s in R 6 (F) V 1 . Now we can extend (V 1 , V 2 ) to a partition (V 1 , V 2 ) of R 8 (F) by adding all vertices of A + (v), A -(v) to V i whenever v ∈ V i .
We claim that this partition is (out-branchable, in-branchable): to show this, it is sufficient to show that every vertex in V 1 can be reached from s in R 8 (F) V 1 and every vertex in V 2 can reach r in R 8 (F) V 2 . Let us observe the following.

• Every vertex v ∈ V 1 -s has an arc uv entering it in B + so u can reach A -(v) in R 8 (F) V 1 . • v ∈ V 1 can reach A + (v) • s can reach A -(s).
Together, these observations imply that R 8 (F) V 1 has an out-branching rooted at s. Analogously one can prove that every vertex in V 2 can reach r in R 8 (F) V 2 , implying that R 8 (F) V 2 has an in-branching. [START_REF] Bang-Jensen | Vertex-disjoint directed and undirected cycles in general digraphs[END_REF] Concluding remarks and open problems

Faster and FPT algorithms

In this paper, we gave polynomial algorithms for many [k 1 , k 2 ]-partition problems for k 1 and k 2 fixed. However, the proposed algorithms are only polynomial when k 1 and k 2 are fixed and generally have a typical running time of O(n α•k1+β•k2+γ ) for some constants α, β, γ. This means that the [k 1 , k 2 ]partition problem is in XP with respect to the parameter (k 1 , k 2 ). A natural question is then to ask whether some of those problems can be solved in polynomial time or when this is not the case, then in FPT time when k 1 and k 2 are not fixed. Problem 6.1 For which pairs (P 1 , P 2 ) of properties among the ones studied in this paper, does there exist an algorithm that, given a digraph D and two positive integers k 1 , k 2 , decides whether D admits a (P 1 , P 2 )-[k 1 , k 2 ]-partition in polynomial time? Which ones can be solved in FPT time (i.e. f (k 1 , k 2 )n c )-time with f a computable function and c a constant.

Partitions with other properties

Of course, one can consider (P 1 , P 2 )-partition problems for different properties P 1 , P 2 than the ones we considered in this paper and its companion [START_REF] Bang-Jensen | Finding good 2-partitions of digraphs I[END_REF]. A first possibility is to consider properties that are the union of several properties we considered as examplified in the next subsection. Again imposing the strong connectivity may change the complexity as shown in Subsection 6.2.2. Another possibility is to consider completely different properties like having bounded maximum degree. This is discussed briefly in Subsection 6.2.3. 6.2.1 (connected and δ + ≥ 1, connected and δ + ≥ 1)-partitions Proposition 6.2 There exists a polynomial-time algorithm that decides whether a given digraph D has a (connected and δ + ≥ 1, connected and δ + ≥ 1)-partition.

Proof: If D has more than two connected components or there is a vertex with out-degree 0, then we return 'No' because D is clearly a 'No'-instance. Henceforth we assume that D has at most two connected components and minimum out-degree at least 1. First, using McCuaig's algorithm [START_REF] Mccuaig | Intercyclic digraphs[END_REF], we check in polynomial time whether D has two disjoint directed cycles C 1 , C 2 . If there are no such cycles, then D is 'No'-instance. Assume now that two such cycles exist. Let W 1 be the set of vertices that can reach V (C 1 ) by a directed path in D -V (C 2 ) and let D 2,1 , . . . , D 2,k be the connected components of D -W 1 where V (C 2 ) ⊆ V (D 2,1 ). Note that we have δ + (D 2,i ) ≥ 1 for i ∈ [k] since every vertex of V (D) \ W 1 has all its out-neighbours in V (D) \ W 1 . Hence if k = 1 we are done, so assume k > 1. If there is at least one arc between W 1 and each of V (D 2,2 ), . . . , V (D 2,k ) (by definition of W 1 such arcs will have tail in W 1 ), then (V (D 2,1 ), V \ V (D 2,1 )) is the desired partition so assume w.l.o.g that there is no arc from W 1 to V (D 2,k ). Then all of D 2,1 , . . . , D 2,k-1 are adjacent to W 1 (as D has at most two connected components) and (V (D 2,k ), V (D) \ V (D 2,k )) is the desired partition. Proof: Suppose first that D is strong. Then using handle-decompositions as above, we observe that D has the desired partition if and only if its underlying graph U G(D) contains two cycles C, C such that C is also a (directed) cycle in D. One direction is clear and the other follows by starting from such a pair C, C and then adding (internal parts of) handles to either the part containing C or the one containing C . In [START_REF] Bang-Jensen | On the problem of finding disjoint cycles and dicycles in a digraph[END_REF], a polynomial algorithm for deciding the existence of cycles C, C as above (and constructing such when they exist). Combining this with the handle adding process above, we obtain the desired algorithm.

In [START_REF] Bang-Jensen | Vertex-disjoint directed and undirected cycles in general digraphs[END_REF], it was shown that deciding the existence of cycles C, C as above is NP-complete for general (non-strong) digraphs so we may expect that the (strong, connected with a cycle)-partition problem is NP-complete for non-strong digraphs. This follows from the proof of Theorem 4.2(i), because the proof actually shows that the non-strong part of the (strong, connected)-partition that exists if and only if F is satisfiable will also contain a cycle (which is even a directed cycle). It follows from Theorem 3.15 that we can decide the existence of disjoint directed cycles of lengths at least p 1 respectively p 2 in polynomial time.

Partitions where we upper bound (maximum) degrees

One may also consider the properties of having maximum degree at most p. This property is clearly hereditary. Note moreover that inducing a digraph with maximum degree (at most) 0 is equivalent to be an independent set.

Observe that if D is a symmetric digraph, then there is a one-to-one correspondence between the (∆ + ≤ p, ∆ + ≤ p)-partition of D and the p-improper 2-colourings of U G(D). Cowen et al. [START_REF] Cowen | Defective coloring revisited[END_REF] proved that for any p ≥ 1, deciding if a graph has a p-improper 2-colouring is NP-complete. This implies that the (∆ + ≤ p, ∆ + ≤ p)-partition problem is NP-complete for any positive p. In fact, their proof can be easily modified to show the following. Theorem 6.7 Let p 1 , p 2 be two non-negative integers such that p 1 + p 2 ≥ 1, and let k 1 , k 2 be two positive integers. The (∆ + ≤ p 1 , ∆ + ≤ p 2 )-[k 1 , k 2 ]-partition problem is NP-complete.

Thomassen [START_REF] Thomassen | Even cycles in directed graphs[END_REF] constructed a class D of out-regular digraphs (same out-degree at all vertices) that have no even directed cycle. Alon [START_REF] Alon | Splitting digraphs[END_REF] pointed out that the digraphs in D have no 2-partition (V 1 , V 2 ) such that ∆ + (D V i ) < ∆ + (D) for i ∈ [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. He also proved that it is always possible to split V (D) into k ≥ 3 sets such that each of the induced subdigraphs has smaller maximum out-degree than D.

It is an easy fact that every graph G contains a spanning bipartite graph B(G) in which the degree of each vertex is at least half of its degree in G. Alon's observation implies that there are digraphs (in particular all digraphs in D) for which we cannot even guarantee out-degree at least one in any spanning bipartite subdigraph. Problem 6.8 What is the complexity of deciding whether a given digraph D has a 2-partition (V 1 , V 2 ) with ∆ + (D V i ) < ∆ + (D)?

Lemma 2 . 1

 21 Let D be a digraph. If S is a set of vertices such that D S is out-branchable and Reach + D (S) = V (D), then D has an out-branching with root in S.

Lemma 3 . 1

 31 Let k 1 , k 2 be fixed positive integers and let D be a connected digraph. D admits a (connected, connected)-[k 1 , k 2 ]-partition if and only if it contains two disjoint connected subdigraphs D 1 and D 2 of order k 1 and k 2 respectively. Proof: Clearly, every connected digraph or order at least k contains a connected subdigraph of order k. Therefore, if D admits a (connected, connected)-[k 1 , k 2 ]-partition, then D contains two disjoint connected subdigraphs D 1 and D 2 or order k 1 and k 2 respectively.

Lemma 3 . 3

 33 Let k be positive integer. Every digraph D with δ(D) ≥ 1 and |D| ≥ k has a subdigraph D with δ(D ) ≥ 1 and |D | ∈ {k, k + 1}. Proof: By induction on |D|, the result holding trivially when |D| ∈ {k, k + 1}. Assume now that |D| ≥ k + 2. Let C be a connected component of D, let T be a spanning tree of C and let v be a leaf of T . If |C| = 2, then δ(D -C) ≥ 1 and |D -C| ≥ k. Hence by the induction hypothesis, there is a subdigraph D of D -C, and thus also of D, with δ(D ) ≥ 1 and |D | ∈ {k, k + 1}. If |C| ≥ 3, then δ(C -v) ≥ 1, because every vertex in C -v has a neighbour distinct from v in T . Thus δ(D -v) ≥ 1 and |D -v| ≥ k. Hence by the induction hypothesis, there is a subdigraph D of D -v, and thus also of D, with δ(D ) ≥ 1 and |D | ∈ {k, k + 1}. Lemma 3.4 Let D be a digraph with with δ(D) ≥ 1. If there are two disjoint subsets (U 1 , U 2 ) such that δ(D U 1 ) ≥ 1 and δ(D U 2 ) ≥ 1, then there exists a

Lemmas 3 .Corollary 3 . 5 Theorem 3 . 6

 33536 3 and 3.4 directly imply the following. Let k 1 , k 2 be fixed positive integers and let D be a digraph with δ(D) ≥ 1. D admits a (δ ≥ 1, δ ≥ 1)-[k 1 , k 2 ]-partition if and only if it contains two disjoint subdigraphs D 1 and D 2 such that |D 1 | ∈ {k 1 , k 1 + 1} and |D 2 | ∈ {k 2 , k 2 + 1} respectively. Deciding whether a digraph has a

Lemma 3 .

 3 12 Let D be a digraph with δ + (D) ≥ 1 and let k ≤ |D| be an integer. One of the following holds : (i) D has a directed cycle of order at least k; (ii) D has a subdigraph D with δ + (D ) ≥ 1 and k ≤ |D | ≤ 2k -2. Proof: We prove the result by induction on |V (D)| + |A(D)|, the result holding trivially when |D| ≤ 2k -2. Henceforth we assume that |D| ≥ 2k -1.

  and D -D 2 has a directed cycle of length at least k 1 ;

  If D has a unique initial strong component, then D has an out-branching. Take a leaf v of this out-branching. ({v}, V (D -v)) is is a (strong, out-branchable)-[1, k]-partition. Thus we return 'Yes'. Proposition 3.18 Let k be a positive integer. The (strong, δ + ≥ 1)-[1, k]-partition problem (resp. (strong, δ -≥ 1)-[1, k]-partition problem) is polynomial-time solvable. Proof: Let D be a digraph. If |D| < k + 1, then the answer is clearly 'No'. Henceforth, we may assume that |D| ≥ k + 1.

Proposition 3 . 19

 319 Let k be a positive integer. The (strong, connected)-[1, k]-partition problem and the (strong, δ ≥ 1)-[1, k]-partition problems are polynomial-time solvable. Proof: We first consider the (strong, connected)-[1, k]-partition problem. Let D be given. We compute the connected components of D. If |D| < k + 1, then the answer is clearly 'No'. Henceforth, we may assume that |D| ≥ k + 1.

Theorem 4 . 2

 42 The following 2-partition problems are NP-complete.

(

Corollary 5 . 3

 53 Let k 1 and k 2 be two positive integers and let P ∈ {strong,δ + ≥ 1, δ -≥ 1, δ 0 ≥ 1}. A strong digraph D admits a ( P, connected)-[k 1 , k 2 ]-partition if and only if there is a set V 2 with |V 2 | = k 2 such that D V 2 isconnected and D -V 2 has a maximal subdigraph with property P of size at least k 1 .

Figure 2 :

 2 Figure 2: The second gadget

Figure 3 :

 3 Figure 3: The digraph D(F) when F has the clausesC 1 = x 1 ∨ x 2 ∨ x 3 and C 2 = x 5 ∨ x 6 ∨ x 7

  which yields a truth assignment satisfying F as shown in the proof of Theorem 4.7.

Problem 6 . 3

 63 Is the |V i | ≥ k i , i = 1, 2, version of the problem above polynomially solvable for all fixed values of k 1 , k 2 ?6.2.2 (strong,connected with an underlying cycle)-partitionsWe say that a digraph D has an underlying cycle if U G(D) has a cycle. Theorem 6.4 The (strong, connected with an underlying cycle)-partition problem is NP-complete for general digraphs and polynomial-time solvable for strong digraphs

Problem 6 . 5

 65 What is the complexity for strong digraphs and fixed positive integers k 1 , k 2 of the (strong, connected with an underlying cycle)-[k 1 , k 2 ]-partition problem? This seems related to the following problem which is also open. Problem 6.6 What is the complexity of deciding, for fixed positive integers k 1 , k 2 whether the underlying graph of a strong digraph contains cycles C i such that |V (C i )| ≥ k i and C 1 is a directed cycle in D?

Table 2 :

 2 Complexity of the (P

1 , P 2 )-[k 1 , k 2 ]-partition problem on strong digraphs.

  partition if and only if one of the following holds: (i) D has two disjoint directed cycles C 1 and C 2 of length at least k 1 and k 2 respectively;

  to find the maximal subdigraph D * of D -V 2 with property P. If D * has size at least k 1 , then we return 'Yes'. If not, then we proceed to the next k 2 -subset Y .If after examining all sets Y , no partition is returned, we return 'No'.The validity of this algorithm follows Corollary 5.3. Its running time is clearly O(n k2+2 ).Similarly to the proof of Corollary 5.3, Lemma 5.2 and Proposition 3.3 yield the following corollary. Let k 1 and k 2 be two fixed positive integers, and letP ∈ {strong, δ + ≥ 1, δ -≥ 1, δ 0 ≥ 1}. A strong digraph D admits a (P, δ ≥ 1)-[k 1 , k 2 ]-partition if and only if there is a set V 2 with |V 2 | ∈ {k 2 , k 2 + 1} such that δ(D V 2 ) ≥ 1 and D -V 2 hasa maximal subdigraph with property P of size at least k 1 .

	Corollary 5.5

Sophia Antipolis, France, project COATI. Hospitality and financial support from Labex UCN@Sophia, Sophia Antipolis is gratefully acknowledged. The research of Bang-Jensen was also supported by the Danish research council under grant number 1323-00178B Partially supported by ANR under contract STINT ANR-13-BS02-0007.

• For all j ∈ [m], add a new vertex c j and all arcs from W j to c j .

• For all j ∈ [m], add a vertex f j and an arc c j f j .

We first prove (a) by showing that

we have the following properties: all vertices of {s, t, x, y} ∪ {c 1 , . . . , c m , f 1 , . . . , f m } must belong to V 2 and (as in the proof of Theorem 4.2) V 1 (being of size larger than 1) must contain a directed cycle which uses either P i,1 or P i,2 for i ∈ [n]. The vertex s must be the root of the out-branching in D V 2 since it is the unique in-neighbour of t. As a 1,1 , a 1,2 , t are the only out-neighbours of s, exactly one of the vertices a 1,1 , a 1,2 belongs to V 2 and the other to V 1 . As x, y ∈ V 2 , there is a directed path from s to {x, y} in V 2 , implying that precisely one of b n,1 , b n,2 belongs to V 2 and if b n,j ∈ V 2 then all vertices of P n,j are also in V 2 for j ∈ [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. Now the claim follows as in the proof of Theorem 4.2(i): we assign to the variable x i the value true if and only if

Conversely, if there is a truth assignment satisfying F, we obtain a (strong, out-branchable)-[k 1 , k 2 ]-partition by the above correspondence. For each j ∈ [m], at least one vertex of W j is in V 2 and now it is easy to see that s can reach all vertices in D V 2 .

The proof of (b) is very similar as the same arguments as above imply that in any (δ

be an instance of 3-SAT consisting of clauses C 1 , . . . , C m over n boolean variables x 1 , . . . , x n . Let R 3 (F) be the digraph obtained from R(F) with the following modifications:

• For all j ∈ [m], add a new vertex c j and all arcs from c j to W j .

• Add two vertices s * , t * and the arcs

the vertices s * , t * and all the vertices d 1 , . . . , d n belong to V 2 and for each j ∈ [m] at least one vertex in W j is in V 1 (because the c j vertices all have in-degree 0 and they cannot be root of the out-branching as s * has no in-neighbour). As in the proof above we now see that D V 1 must contain precisely one directed cycle W and this must meet all of the sets W 1 , . . . , W m (in order to c j have out-degree at least 1). The rest of the proof should be clear now (it follows from Theorem 4.1). Let R 4 (F) be the digraph obtained from R(F) as follows :

Proposition 5.9 Let k be a positive integer and P be a property in {strong, δ 0 ≥ 1, δ + ≥ 1,in-branchable} (resp. {strong, δ 0 ≥ 1, δ -≥ 1,out-branchable}). Deciding whether a strong digraph has an (out-branchable, P)-[1, k]-partition (resp. (in-branchable,P)-[1, k]-partition) is polynomial-time solvable.

Proof: Let us describe a polynomial-time algorithm that decides whether a digraph D has an (outbranchable, P)-[1, k]-partition for P ∈ {strong, δ 0 ≥ 1, δ + ≥ 1,in-branchable}.

If |D| ≤ 2k -2, we use brute force and try all possible partitions and check whether one of them is an (out-branchable, P)-[1, k]-partition. Henceforth we assume that |D| ≥ 2k -1.

We compute a handle decomposition ((h i ) 1≤i≤p , (D i ) 0≤i≤p ). Let q be the last index such that h q has length at least 2. If |D q-1 | ≥ k, then by Lemma 5.7, D has an (out-branchable, strong)-[1, k]partition, which is also an (out-branchable, P)-[1, k]-partition, so we return 'Yes'. Henceforth, we assume |D q-1 | ≤ k -1, and so h q has length at least k.

Let u and v be respectively the initial and terminal vertices of h q . Since D q-1 is strong, there is a directed (v, u)-path in D q-1 , whose union with h q is a cycle C. Now C has length at least k since it contains h q . If C is not Hamiltonian in D, then by Lemma 5.7, D has an (out-branchable, strong)-[1, k]-partition, so we return 'Yes'. Henceforth, we assume that C is a Hamiltonian directed cycle of D. For each pair u, v of vertices such that vu / ∈ A(C), we check whether C[u, v] has property P and order at least k. If it is the case for at least one such pair, then we return 'Yes', otherwise we return 'No'. This is valid by Lemma 5.8.

Remark 5.10 For sake of simplicity, we made no attempt to optimize the complexity of the above algorithm. But faster algorithms may be designed. For example, in the above algorithm for (outbranchable, strong)-partition, we might have to check for Ω(|V (D)| 2 ) pairs whether C[u, v] is strong, which can be done in linear time. We can design a faster algorithm: similarly to Lemma 5.8, one can prove the following: There is an (out-branchable, strong)-

NP-completeness

The aim of this subsection is to prove for any P ∈ { strong, δ 0 ≥ 1, δ + ≥ 1 in-branchable}, and any k 1 , k 2 ≥ 2, the (out-branchable, P)-[k 1 , k 2 ]-partition problem is NP-complete. We prove it for P ∈ { strong, δ 0 ≥ 1} in Theorem 5.11, for P = (δ + ≥ 1) in Theorem 5.12 and for P =in-branchable in Theorem 5.13. (ii) Deciding whether a strong digraph has an (out-branchable,

Proof: The two proofs are identical, so we only give the proof of (i). (Observe that a digraph with δ 0 ≥ 1 has necessarily at least two vertices so the condition k 2 ≥ 1 is equivalent to k 2 ≥ 2 in (ii).)

We shall show a reduction from 3-SAT using ring digraphs and the following concept. An (a, b)-bond in a digraph D is an induced subdigraph with vertex set {a, b, z 1 , z 2 } and arc set {az 1 , az 2 , z 1 b, z 2 b} such that d Let us prove that R 7 (F) has an (out-branchable, strong)-[k 1 , k 2 ]-partition if and only if F is satisfiable. By Theorem 4.1, it suffices to prove that R 7 (F) has an (out-branchable, strong)-[k 1 , k 2 ]partition if and only if R(F) has a directed cycle intersecting all the sets W 1 , . . . , W m .