Daniel Gonçalves
email: daniel.goncalves@lirmm.fr

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

Alexandre Pinlou
email: alexandre.pinlou@lirmm.fr

Stéphan Thomassé
email: thomasse@lirmm.fr

On Spanning Galaxies in Digraphs

Keywords: spanning galaxy, even strong subdigraph, directed star arboricity, algorithms, fixed parameter tractable

In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph D has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the Spanning Galaxy problem is equivalent to the problem of deciding if a strong digraph has a strong digraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph D, which is the minimum number of galaxies needed to cover all the arcs of D. We show in particular that dst(D) ≤ ∆(D)+1 for every digraph D and that dst(D) ≤ ∆(D) for every acyclic digraph D.

Introduction

All digraphs considered here are finite and loopless. We rely on [START_REF] Bang-Jensen | Digraphs: theory and applications[END_REF] for classical notations and concepts. The out-neighbourhood (resp. in-neighbourhood) of a vertex u is denoted by N + (u) (resp. N -(u)). A digraph is said to be even if it has an even number of vertices.

A directed path in a digraph is a subdigraph P with vertex set {v 1 , . . . , v k } and arc set {v 1 v 2 , . . . , v k-1 v k }. It is said to go from v 1 to v k . A digraph D = (V, A) is strongly connected or strong if for every pair (u, v) ∈ V 2 there is a directed path from u to v.

The Spanning Galaxy problem is polynomial-time solvable on strong

digraphs (Corollary 12). In order to prove this, we show in Theorem 9 that a strong digraph has a spanning galaxy if and only if it contains an even strong subdigraph. We then describe (Theorem 11) a polynomial-time algorithm for deciding if a strong digraph has an even strong subdigraph.

4. The problems of testing if a digraph contains a spanning galaxy that uses or avoids, respectively, a prespecified arc is NP-complete, even if the given digraph is strong (Theorem 14). In contrast, we show in Theorem 13 that the problems of testing if a strong digraph contains an even strong subdigraph that uses or avoids, respectively, a prespecified arc is polynomialtime solvable.

5.

The Spanning Galaxy problem is W [START_REF] Alon | Star arboricity[END_REF]-hard when parameterized by the number of stars of the galaxy and Fixed Parameter Tractable when paramaterized by the number k of vertices of the digraph that are spanned (does a digraph contain a galaxy on at least k vertices?). See Section 5.

In Section 6, using the notion of spanning galaxy, we improve some results regarding directed star arboricity. In fact, our interest to spanning galaxy originated in this concept. The directed star arboricity of a digraph D, denoted by dst(D), is the minimum number of galaxies needed to cover A(D). Amini et al. [START_REF] Amini | WDM and directed star arboricity[END_REF] conjectured that every digraph D with maximum degree ∆ ≥ 3 satisfies dst(D) ≤ ∆. We prove this conjecture for acyclic digraphs and show that dst(D) ≤ ∆(D) + 1 for every digraph D.

Finally, we conclude with some related open questions.

Spanning Galaxy and Winning Diforest

Proposition 1. The Spanning Galaxy problem can be solved in linear time for arborescences.

Proof . If an arborescence T has no vertices, it vacuously admits a spanning galaxy. If T is restricted to its root, it has none. Now if T has at least two vertices, we consider a furthest leaf v from r and we denote by u the in-neighbour of v. By definition of v, all the out-neighbours of u are leaves. Thus, if T admits a spanning galaxy, this galaxy contains the star with root u whose leaves are the out-neighbours of u. Hence, T admits a spanning galaxy if and only if T -({u}∪N + (u)) does. This gives a simple linear-time algorithm for arborescences.

The proof of the above proposition also implies the following lemma.

Lemma 2. Every arborescence T contains a galaxy spanning every vertex except possibly the root.

The parity game is a widely studied game. Its restriction to arborescences is played on an arborescence T (with root r) by two players, Player 1 and Player 2, as follows. At the beginning of a play, a token is placed on the root r and is then moved over V (T ) following the transitional relation: if the token is placed on a vertex v, then the next position of the token is one of the out-neighbours of v. The players move the token alternatively (starting with Player 1) until the token reaches a leaf. A player wins if its opponent cannot move anymore. Since our arborescences are finite, one of the two players has a winning strategy.

If Player 1 has a winning strategy, we say that T is winning; otherwise, T is losing. By convention, an arborescence T with zero vertices is winning.

Lemma 3. An arborescence T admits a spanning galaxy if and only if T is winning.

Proof . This directly follows from:

• An arborescence T with one vertex is losing.

• Given an arborescence T with at least two vertices, where v is any furthest leaf from the root, and where u is the in-neighbour of v; T is winning if

and only if T -({u} ∪ N + (u)) is winning.
A diforest is winning if all its arborescences are winning, otherwise it is losing. Since stars are winning arborescences Lemma 3 implies the following: Lemma 4. A digraph D admits a spanning galaxy if and only if D contains a winning spanning diforest.

The directed path of length l, P l = (r, v 1 , v 2 , . . . , v l ), admits a spanning galaxy if and only if l is odd (recall that the length of a path is its number of arcs). Given two arborescences T and T ′ and a vertex v of T , we denote by T ∨ v T ′ the arborescence obtained by identifying v in T with the root of T ′ . When v is the root of T , we simply write T ∨ T ′ . Observe that T ∨ T ′ is winning if and only if T or T ′ is winning. Similarly, if T ′ is losing, then T ∨ v T ′ is winning if and only if T is winning.

Thus, we have the following two lemmas, which we will use in Section 6.

Lemma 5. For every arborescence T and every odd integer l, the arborescence T ∨ P l is winning.

Lemma 6. For every arborescence T , every vertex v of T , and every even integer l, the arborescence T ∨ v P l is winning if and only if T is winning.

Spanning Galaxy in Acyclic Digraphs

Theorem 7. The Spanning Galaxy problem is NP-complete, even when restricted to digraphs which are acyclic, planar, bipartite, subcubic, with arbitrarily large girth, and with maximum out-degree 2.

Proof . This problem is clearly in NP and we prove now that it is NP-hard for this restricted family of digraphs. Kratochvíl proved that Planar (3, ≤ 4)-Sat is NP-complete [START_REF] Kratochvíl | A special planar satisfiability problem and a consequence of its NP-completeness[END_REF]. In this restricted version of Sat, the variable-clause incidence graph of the input formula is planar, every clause is a disjunction of three literals, and every variable occurs in at most four clauses. We reduce Planar (3, ≤ 4)-Sat to the Spanning Galaxy problem. Given an instance I of Planar (3, ≤ 4)-Sat, we shall construct a planar digraph D I such that I is a satisfiable instance of Planar (3, ≤ 4)-Sat if and only if D I has a spanning galaxy. For this, we take one copy of the graph depicted in Figure 1(a) per variable of I, and one copy of the graph depicted in Figure 1(b) per clause of I. Whenever the literal x (resp. x) appears in a clause c in I, we identify one vertex labelled x (resp. x) of the variable gadget of x with a source of the clause gadget of c. Let us observe that the digraph D I is acyclic, planar, bipartite, subcubic, with maximum in-degree 3 and with maximum out-degree 2.

The variable gadget of x in the graph D I is connected to the rest of the graph by the vertices labelled by x or x. The vertices which are not labelled by x or x are called internal vertices of the variable gadget of x. One can observe that there are only two possible galaxies that span all the internal vertices of a variable gadget. Actually, these two galaxies span all the vertices of the variable gadget. Moreover, in the first galaxy, every vertex x is the root of a star and every vertex x is a leaf of a star; in the second one, every vertex x is a root of a star and every vertex x is a leaf of a star. In addition, one can observe that the previous remark, stating that the vertices x are roots of stars whenever the vertices x are leaves, holds for any odd paths linking a and b (resp. a and c, b and d, c and d). Therefore, the girth of the graph D I can be made arbitrarily large.

Let I be an instance of Planar (3, ≤ 4)-Sat. Suppose first that I is satisfiable by some truth assignment φ. Let us exhibit a spanning galaxy of D I . For every variable x, we span its gadget with a galaxy in such a way that the vertices labelled x are roots of stars if and only if φ(x) =True. In this way, we can span the internal vertices c of the clause gadgets. Indeed, since c is satisfied by φ, the vertex c has an in-neighbour x 1 which is the root of a star. We then add the arc x 1 c to our galaxy to span c. Suppose now that D I has a spanning galaxy T . Let φ be the truth assignment φ defined by φ(x) =True if and only if the vertices labelled x are roots of stars of T . Then φ satisfies I since every clause vertex c needs one of its in-neighbours to be the root of some star.

Spanning Galaxy and even strong subdigraph

Let D be a strong digraph. A handle h of D is a directed path (s, v 1 , . . . , v ℓ , t) from s to t (where s and t may be identical, or the handle possibly restricted to the arc st) such that:

• for all 1 ≤ i ≤ ℓ, d -(v i ) = d + (v i ) = 1,

and

• the digraph D \ h obtained from D by suppressing h, that is removing the arcs and the internal vertices of h, is strong.

The vertices s and t are the endvertices of h while the vertices v i are its inner vertices. The vertex s is the tail of h and t its head. The length of a handle is the number of its arcs, here ℓ + 1. A handle of length one is said to be trivial. For any 1 ≤ i, j ≤ ℓ, we say that v i precedes (resp. strictly precedes) v j on the handle h if i ≤ j (resp. (i < j)).

Given a strong digraph D, a handle decomposition of D starting at v ∈ V (D) is a triplet (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ), where (D i ) 0≤i≤p is a sequence of strong digraphs and (h i ) 1≤i≤p is a sequence of handles such that:

• V (D 0 ) = {v},
• for 1 ≤ i ≤ p, h i is a handle of D i and D i is the (edge-disjoint) union of D i-1 and h i , and

• D = D p .
A handle decomposition is uniquely determined by v and either (h i ) 1≤i≤p , or (D i ) 0≤i≤p . The number of handles p in any handle decomposition of D is exactly |A(D)| -|V (D)| + 1. The value p is also called the cyclomatic number of D. Observe that p = 0 when D is a singleton and p = 1 when D is a circuit. A digraph D with cyclomatic number two is called a theta.

The following lemma is straightforward.

Lemma 8. For every strong digraph D ′ of some strong digraph D, there is a handle decomposition (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) of D such that D ′ = D i for some i.

A handle is even if its length is even. A handle decomposition is even if one of its handles is even. A strong digraph is even if it has an even number of vertices. Handles, handle decompositions and strong digraphs are odd when they are not even. Given a digraph D, D is obtained from D by reversing every arc.

Theorem 9. Given a strong digraph D, the following are equivalent:

(1) D has a spanning galaxy.

(2) D has a spanning galaxy.

(3) D contains a winning spanning arborescence.

(4) D has an even handle decomposition.

(5) D contains an even circuit or an even theta. [START_REF] Downey | Fixed parameter tractability and completeness I: basic results[END_REF] D contains an even strong subdigraph.

Proof .

(3) ⇒ (1). Consider a digraph D containing a winning spanning arborescence T . Lemma 3 implies that T contains a spanning galaxy, which also spans D.

(4) ⇒ (3). Let (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) be an even handle decomposition of D. Let q be the largest integer such that h q is an even handle. Since D q-1 is strong, it contains a spanning arborescence T q-1 rooted at s q , the first vertex of h q . Now for every q ≤ r ≤ p, we define a spanning arborescence T r of D r as follows. For every h r = (s r , v 1 , . . . , v ℓ , t r ), we let T r = T r-1 ∨ sr P r where P r is the path (s r , v 1 , . . . , v ℓ ), i.e. the handle h r minus its last arc. By Lemma 5, the arborescence T q is winning since T q-1 ∨ sq P q is T q-1 ∨ P q . Therefore, by Lemma 6, T r is winning, for every q ≤ r ≤ p. Thus T p is a winning spanning arborescence of D.

(1) ⇒ (4). By way of contradiction, suppose that there exists a strong digraph D with no even handle decomposition admitting a spanning galaxy. Observe that in particular, D has no even circuit. Choose such a D with minimum number of arcs. Let F be a spanning galaxy of D. Observe that (o) every trivial handle st of D belongs to E(F ), otherwise deleting the arc st from D leaves a strong digraph spanned by F and with no even handle decomposition, against the minimality of D.

Consider a handle decomposition (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) of D which minimizes the number of trivial handles. Let q be the largest integer such that h q = (v 0 , . . . , v ℓ+1 ) is non trivial (here we adopt the notation s := v 0 and t := v ℓ+1 ). Hence, every handle h i is trivial for every q < i ≤ p. Moreover, since h q is odd and non trivial, we have ℓ ≥ 2. Since the number of trivial handles in this decomposition is minimum, we have the following straightforward properties.

(i) there is no arc

v i v j with j ≥ i + 2, except possibly v 0 v l+1 ; (ii) for 2 ≤ i ≤ ℓ, the vertex v i has no in-neighbour in D q-1 ; (iii) for 1 ≤ i ≤ ℓ -1, the vertex v i has no out-neighbour in D q-1 .
In addition, Observation (iii) implies that:

(iv) v 1 has no in-neighbours in D q-1 -v 0 .
Indeed if u is such an in-neighbour, both arcs uv 1 and v 0 v 1 would be trivial handles of D. Hence, according to the previous observation, they both are in

E(F ) which is impossible. Furthermore, (v) there is no arc v j v i with 0 ≤ i < j ≤ ℓ + 1.
We prove (v) as follows. An arc v j v i is short if there is no distinct arc v j ′ v i ′ for which i ≤ i ′ < j ′ ≤ j. By way of contradiction, consider a short arc v j v i which minimizes i. By (i) and since there is no even circuit, the vertices v i , v i+1 , . . . , v j induce an odd circuit. Moreover, since deleting the arc v j v i leaves D strongly connected, we have v j v i ∈ F (by (o)). Hence there is at least one vertex in X = {v i+1 , . . . , v j-1 } which has a neighbour in F -X. Let i ′ be the smallest index of such a vertex. By (i), (ii), (iii), (iv) and the choice of v j v i , we have either j = l + 1 and an arc v l x with x ∈ V (D q-1 ), or there is an arc v j ′ v i ′ such that i < i ′ < j < j ′ . In the first case, v l v l+1 is a trivial handle and so by (o), it is in E(F ). This is a contradiction to v l+1 v i in E(F ). Hence we may assume that we are in the second case. If i ′ -i is odd then (v j , v i , v i+1 , . . . , v i ′ ) is an even handle on the circuit (v i ′ , v i ′ +1 , . . . , v j ′ ), contradicting the fact that D has no even handle decomposition. If i ′i is even then X ′ = {v i+1 , . . . , v i ′ -1 } has odd cardinality, and both arcs v j ′ v i ′ and v j v i are in E(F ). Hence there must be a vertex in X ′ which has a neighbour in F -X ′ , contradicting the definition of i ′ . This proves (v).

The above properties imply that the only arc entering S = {v 1 , . . . , v ℓ } is v 0 v 1 and the only arcs leaving S are those leaving

v ℓ . Moreover (v 0 , v 1 , . . . , v ℓ ) is an induced path. If {v 1 v 2 , v 3 v 4 , . . . , v ℓ-1 v ℓ } ⊆ E(F ) then the digraph D q-1
would also be a counterexample, contradicting the minimality of D. Thus E(F ) contains the arcs v 0 v 1 , v 2 v 3 , . . . , v ℓ-2 v ℓ-1 and all the arcs leaving v ℓ (by (iv)). Hence v 1 has only v 0 as in-neighbour (by (o)). Thus the digraph obtained from D by contracting v 0 v 1 and v 1 v 2 has a spanning galaxy and no even handle decomposition. This contradicts the minimality of D.

(4) ⇒ [START_REF] Brandt | Multicasting using WDM in Multifiber Optical Star Networks[END_REF]. By way of contradiction, suppose that there are strong digraphs with an even handle decomposition containing no even circuits nor even thetas. Consider such a digraph D with an even handle decomposition (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) minimizing p. It is clear, by minimality of p that the only even handle of this decomposition is h p . Otherwise D p-1 would contradict the minimality of p.

In the remainder, we denote by s and t the tail and the head respectively of the handle h p . Claim 1. p > 2.

If p = 1, then D would be an even circuit. If p = 2, then h 1 has odd length and thus D would either be an even theta or contain an even circuit. This proves Claim 1.

By Lemma 8, there is a handle decomposition (s, (h ′ i ) 1≤i≤p , (D ′ i ) 0≤i≤p ) of D starting at s and such that h ′ p = h p . For every 1 < i < p, let us denote by s i the tail of h ′ i and by t i its head.

Claim 2. For every

1 < i < p, the endvertices of h ′ i are inner vertices of h ′ i-1 .
Suppose for a contradiction that the claim does not hold. Let q be the largest integer such that one of the two endvertices of h ′ q is not an inner vertex of h ′ q-1 . One of the endvertices of h ′ q is an inner vertex of h ′ q-1 . Otherwise h ′ q-1 would be a handle of D and the digraph obtained from D by suppressing h ′ q-1 would contradict the minimality of p. By directional duality, we may assume that s q is an inner vertex of h ′ q-1 and t q is not. Let us divide h ′ q-1 into two paths, the path R with tail s q-1 and head s q and the path S with tail s q and head t q-1 . Then S is a handle of D and the digraph obtained from D by suppressing S contradicts the minimality of p (the handles h ′ q-1 and h ′ q are replaced by the concatenation of R and h q ). This proves Claim 2. Claim 3. For every 1 < i < p, the vertex t i precedes s i on h ′ i-1 .

Suppose not. Then s i stricly precedes

t i on h ′ i-1 . Let R be the subpath of h ′ i-1
with tail s i and head t i . Then R is a handle of D and the digraph obtained form D by suppressing R contradicts the minimality of p (the handles h ′ i-1 and h ′ i are replaced by a single handle going from s i-1 to t i-1 containing h ′ i ). This proves Claim 3.

The circuit h ′

1 can be divided into two paths: P 1 with tail s 2 and head t 2 and P 2 with tail t 2 and head s 2 . If s 2 and t 2 are identical, we assume that P 2 has no arc. If s ∈ V (P 2 ), then according to Claims 2 and 3, P 1 is a handle of D which suppression leaves a digraph with an even handle decomposition and no even circuit or theta. This contradicts the minimality of D. If s / ∈ V (P 2 ), then it is an internal vertex of P 1 . Let P 3 be the subpath of P 1 with tail s and head t 2 . Then by Claims 2 and 3, P 3 is a handle of D which suppression leaves a digraph with an even handle decomposition and no even circuit or theta. This contradicts the minimality of D.

(5) ⇒ (6). Trivial since even circuits and thetas are strong digraphs with an even number of vertices.

(6) ⇒ (4). By Lemma 8 consider a handle decomposition (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) of D such that some digraphs D i have an even number of vertices. Let q be the smallest integer such that D q has an even number of vertices. Then the handle h q has an odd number of inner vertices, thus has even length. This comes from the characterization of factor critical graphs by Lovász [START_REF] Lovász | A note on factor-critical graphs[END_REF]. A non-oriented graph G is factor critical, if for every v ∈ V (G) the graph Gv has a perfect matching and Lovász showed that a graph G is factor critical if and only if it has an odd handle decomposition.

Theorem 11. Deciding if a strong digraph contains an even strong subdigraph is polynomial-time solvable.

Proof . Let us describe a polynomial-time algorithm to decide whether a strong digraph D contains an even strong subdigraph (ESS for short). The algorithm performs as follows. We first find a handle decomposition (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) where h q = (x 0 , x 1 , . . . , x ℓ ) is the last non-trivial handle. If there exists an arc with tail y in V (D q-1 ) and head x i , 2 ≤ i ≤ ℓ-1, then replacing the two handles h q and (y, x i ) by (y, x i , . . . x ℓ ) and (x 0 , . . . , x i ) we obtain a new decomposition with less trivial handles. If there exists an arc with tail x i , 1 ≤ i ≤ ℓ-2, and head y in V (D q-1 ), then replacing the two handles h q and (x i , y) by (x 0 , . . . , x i , y) and x i , . . . x ℓ ) we obtain a new decomposition with less trivial handles. If there exists a handle x i x j = x 0 x ℓ , then replacing the two handles h q and (x i x j ) by (x 0 , . . . , x i , x j , . . . , x ℓ ) and (x i , . . . , x j ) we obtain a new decomposition with less trivial handles. The three above operations are done in constant time and since the initial number of trivial handles is polynomial, one can compute in polynomial time a handle decomposition where there are no such arcs. If the decomposition has an even handle then return "YES" thanks to Theorem 9. We can then suppose in the remainder that ℓ is odd. Let D ′ be the digraph obtained from D q-1 by adding all the arcs between N - D (x 1 ) and N + D (x ℓ-1 ). Let S = {x 1 , x 2 , . . . , x ℓ-1 } be the set of inner vertices of h q .

E ′ = D ′ [V (E) \ S] is an ESS of D ′ . Indeed, if |V (E)| = |V (E ′ )|,
the handle h q is a subdigraph of E; however h q is odd so |V (h q )| is even, and thus |V (E ′ )| = |V (E)| -|V (h q )| + 2 is also even. Furthermore, since the paths of E from N - D (x 1 ) to N + D (x ℓ-1 ) are replaced by single arcs in E ′ , E ′ is strong. Finally, it is also clear that given any ESS

F ′ of D ′ one of the graphs D[V (F ′ )] or D[V (F ′ ) ∪ S] is an ESS of D -according to whether or not there is an arc uv in A(F ′ )∩ N - D (x 1 ) × N + D (x ℓ-1
) . This proves Claim 4.

Checking if D[S]

has an ESS can be done in polynomial time. We first check if there exists a backward arc (i.e. an arc x b x a such that a < b) such that a and b have distinct parity. If there is such an arc, the graph D[{x a , x a+1 , . . . , x b }] is an ESS.

If there exists no such arc, we distinguish two types of backward arcs x b x a of D[S]: the arcs where a and b are both even, called e-arcs, and those where a and b are both odd, called o-arcs. Observe that the vertex set F of an ESS of D[S] is of the form {x i , x i+1 , . . . , x j }. Indeed, since there is no arc x a x b with a + 1 < b in D[S] and since there is a path from the vertex with smaller index in V (F ) (here x i ) to the one with higher index (here x j ), all the vertices between x i and x j are in F .

Furthermore since F is even, i and j have distinct parity. Consider a set A of backward arcs such that the union of the directed path {x i , x i+1 , . . . , x j } and A is strong, and such that in addition A is minimum with respect to inclusion. The arcs of A, when ordered increasingly according to the index of their tail, are such that two consecutive arcs x c x a and x d x b satisfy a < b < c < d. Note that since i and j have distinct parity, there exists two consecutive backward arcs of distinct types (one is an e-arc and the other one is an o-arc), say x c x a and x d x b . Then D[x a , x a+1 , . . . , x d ] is an ESS.

Hence to summarize D[S] contains an ESS if and only if it contains an ESS with at most two backward arcs. So this can be checked in polynomial time.

In the case of D ′ , we check whether it contains an ESS or not by applying the algorithm recursively.

Theorems 9 and 11 imply the following.

Corollary 12. The Spanning Galaxy problem is polynomial-time solvable for strong digraphs.

Prescribing an arc

Thomassen [START_REF] Thomassen | Even cycles in directed graphs[END_REF] showed that it is NP-complete to decide whether a digraph D has an even circuit containing a given arc. On the other hand, there is a polynomial-time algorithm to decide whether a digraph D has an even circuit avoiding a given arc uv, it suffices to test whether D \{uv} has an even circuit or not (by [START_REF] Mccuaig | Pólya's permanent problem[END_REF][START_REF] Robertson | Permanents, Pfaffian orientations, and even directed circuits[END_REF]). Similarly, one can decide in polynomial time whether a digraph D has an even circuit or an even theta avoiding a given arc uv, by testing the strong components of D \ {uv}. We now show that one can also decide in polynomial time if a strong digraph has an even strong digraph containing a given arc.

Theorem 13. It is polynomial-time decidable whether a strong digraph has an even strong digraph (ESS) containing (resp. avoiding) a given arc.

Proof . The algorithm to decide if a strong digraph D has an ESS avoiding a given arc uv is very simple. It just has to check if some strong connected component of D \ {uv} has an ESS.

The algorithm to decide if a strong digraph D has an even strong subdigraph containing a given arc uv is very similar to the algorithm described in the proof of Theorem 11. Indeed, consider a handle decomposition (u, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) such that uv ∈ h 1 and such that the number of trivial handles is minimized.

If

h 1 = (x 0 = u, x 1 = v, x 2 , . . . , x l-1 , x l = u)
is the last (and only) nontrivial handle, then the other arcs of D are arcs x i x j with 0 < j < i ≤ l. Thus D has only one path from v to u, namely (v, x 2 , . . . , x l-1 , u). So, every strong digraph containing uv spans D and D has an ESS containing uv if and only if D is even, which is easily checked. Now suppose that the last non-trivial handle is h q = (x 0 , x 1 , . . . , x l ) with q > 1. Then there is no arc from D q-1 to {x 2 , . . . , x ℓ-1 }, from {x 1 , . . . , x ℓ-2 } to D q-1 , nor arc x i x j = x 0 x l with i + 1 < j. If h q is even then one of D q-1 or D q is an even strong subdigraph containing uv. Thus assume h q is odd, and consider the digraph D ′ obtained from D q-1 by adding all the arcs between N - D (x 1 ) and N + D (x l-1 ). One can verify that D has an ESS containing uv if and only if D ′ has an ESS containing uv. Thus the algorithm just has to consider the smaller strong digraph D ′ .

We now prove that the similar variants of the Spanning Galaxy problem are NP-complete.

Theorem 14. It is NP-complete to decide, given a strong digraph and one of its arc, whether there exists a spanning galaxy containing (resp. avoiding) this arc.

Proof . The reduction from the Spanning Galaxy problem in the acyclic case is straightforward. Given an acyclic digraph D, we construct D ′ from D by adding a disjoint directed path (a 1 , a 2 , a 3 , a 4 ), all possible arcs from a 4 to sources of D, and all possible arcs from sinks of D to a 1 . Note that D ′ is strong. Observe that D ′ has a spanning galaxy F containing the arc a 1 a 2 (resp. avoiding a 2 a 3 ) if and only if D has a spanning galaxy.

Parameterizations of Galaxy Problems

The Spanning Galaxy problem being hard in the general case, it is natural to ask if some parameterized version is tractable. A first attempt could be to ask for a fixed parameter tractable algorithm on parameter k (i.e. admitting an algorithm in time O(f (k)n c ) for some constant c) deciding if a digraph admits a spanning galaxy with at most k stars. Unfortunately, the problem k-Domination (which is W[2]-complete [START_REF] Downey | Fixed parameter tractability and completeness I: basic results[END_REF]) admits a straightforward reduction to this problem. Indeed, every minimal dominating set A of a graph G (with no isolated vertex) corresponds to the set of roots of a spanning galaxy of the digraph D obtained from G by replacing each edge ab ∈ E(G) by the arcs ab and ba. Hence the Spanning Galaxy problem is at least as hard as k-Domination, thus it is W [2]-hard.

However, the following problem is easier to handle: This problem is very easily fixed parameter tractable, but we will show a much stronger result. Indeed, there is a polynomial-time algorithm (in size of D) which transforms every instance (D, k) of k-GALAXY into an instance (D ′ , k ′ ) which is equivalent to (D, k) and such that k ′ ≤ k and D ′ has at most 2k -2 vertices. This algorithm is called a (2k -2)-kernelization algorithm, and the output D ′ is called a kernel. Observe that applying a brute force algorithm on D ′ to check if it admits a galaxy spanning at least k ′ vertices takes O(f (k)) time. Hence the existence of the kernelization algorithm gives an FPT algorithm for k-GALAXY running in O(f (k) + n c ) time.

The general idea of the proof is the following. Given an input (D, k), first grow a galaxy by some local procedures in order to obtain a galaxy that is locally maximal. Then we compute some matchings in order to get a larger galaxy. When no more improvement is obtained, we stop the process and we check if the largest obtained galaxy has at least k vertices. If so, (D, k) is a "Yes" instance of the k-Galaxy problem and we return the small "Yes" instance (S k , k) with S k the star of order k. If not, we can find a kernel.

A galaxy F of D is locally maximal if it satisfies the following conditions: Given a galaxy G one can compute a locally maximal galaxy lm(G) spanning at least as many vertices as G with the following polynomial-time algorithm.

Algorithm 1 (lm(G)).

Step 1: F := G.

Step

2: If uv ∈ D \ F then V (F ) := V ∪ {u, v}; E(F ) := E(F ) ∪ {uv}; Go to Step 2.
Step 3:

If uv ∈ A(F ), uw ∈ A(D) and w / ∈ V (F ) then V (F ) := V ∪ {w}; E(F ) := E(F ) ∪ {uw};
Go to Step 2.

Step 4:

If tu ∈ E(F ), uv, uw ∈ A(D) and v, w / ∈ V (F ), then V (F ) := V ∪ {v, w}; E(F ) := E(F ) \ {tu} ∪ {uv, uw}; If d + F (t) = 0, V (F ) := V (F ) \ {t}; Go to Step 2. Step 5: If uv, uw ∈ E(F ), wx ∈ A(D) and x / ∈ V (F ), then V (F ) := V (F ) ∪ {x}; E(F ) := E(F ) \ {uw} ∪ {wx}; Go to Step 2.
Step 6: Return F . This procedure being defined, one can now describe the kernelization algorithm.

Algorithm 2 (Ker(D, k)).

Step 1: G := (∅; ∅);

Step 2: G := lm(G);

Step 3: Step 6:

N + G = {v ∈ V (D) \ V (G) | ∃u ∈ V (G), uv ∈ A(D)}; N - G = V (D) \ (V (G) ∪ N + G );
If |V (G)| ≥ k, return (S k , k).
Step

7: Else, return (D[V (G) ∪ N + (G) ∪ V (M )], k).
Theorem 15. Algorithm 2 is a (2k -2)-kernelization of the k-Galaxy problem.

Proof . As one can compute lm(G) and the maximum matching in a graph in polynomial time, Algorithm 2 runs in polynomial time. Indeed it goes back at most |V (D)| times to Step 2 (from Step 5) since the order of the galaxy strictly increases each time.

Let us now show that (D, k) is a "Yes" instance of the k-Galaxy problem if and only if Ker(D, k) is. This is trivially true when Algorithm 2 stops at Step 6. Hence we may assume that it stops at Step 7.

The galaxy G (at the end of the running) is a locally maximal galaxy because of Step 2. Condition (a) implies that N - G is a stable set of D. Note that

N + G may contain in-neighbours of V (G) while N - G contains no out-neighbours of V (G). D ′ = D V (G)∪N + (G)∪V (M ) is a subdigraph of D. Hence if Ker(D, k) = (D ′ , k) is a "Yes" instance, so is (D, k).
Reciprocally, we shall prove that if (D, k) is a "Yes" instance so is (D ′ , k). Suppose not. Then there is a galaxy G * of D such that D ′ does not contain a galaxy spanning |V (G * )| vertices. Among the possible choices of G * , select one which minimizes its number of vertices in N - G \ M , and then which minimizes its number of arcs between

N - G \ M and V (G). Since G * ⊂ D ′ , G * has a vertex u ∈ N - G \ M
, and thus G * has an arc

uv 1 with v 1 ∈ V (G). Since uv 1 /
∈ M there is an arc u 1 v 1 in M . We inductively define the vertices u i and v i , for i ≥ 2, as follows. If u i-1 does not belong to G * then u j and v j are not defined for j ≥ i. Otherwise, let v i be any vertex such that u i-1 v i is an arc of G * . Note that v i = v j with j < i (otherwise it would have two incoming arcs in G * ) and that v i ∈ V (M ), otherwise the path (v i , u i-1 , v i-1 , . . . , u 1 , v 1 , u) would be an augmenting path with respect to M , contradicting the maximality of M . Thus let u i be the vertex such that u i v i ∈ M . Let t be the greater index for which the vertices u t and v t are defined. Then u t / ∈ V (G * ) and we can replace the arcs uv 1 and u i-1 v i , for 2 ≤ i ≤ t, by the arcs u i v i , for 1 ≤ i ≤ t. Note that since u t was not previously spanned, the obtained galaxy spans at least as many vertices as G * and covers more arcs of M , a contradiction to the choice of G * .

Directed Star Arboricity

Recall that the directed star arboricity of a digraph D, denoted by dst(D), is the minimum number of galaxies needed to cover A(D). This notion has been introduced in [START_REF] Guiduli | On incidence coloring and star arboricity of graphs[END_REF] and is an analog of the star arboricity defined in [START_REF] Algor | The star arboricity of graphs[END_REF].

Let us denote the maximum multiplicity of an edge in a multigraph G by µ(G). By Vizing's theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF], one can colour the edges of a multigraph with ∆(G)+µ(G) colours so that two edges have different colours if they are incident. Since the multigraph underlying a digraph has maximum multiplicity at most two, for any digraph D, dst(D) ≤ ∆+2. Amini et al. [START_REF] Amini | WDM and directed star arboricity[END_REF] conjecture the following:

Conjecture 16 (Amini et al. [START_REF] Amini | WDM and directed star arboricity[END_REF]). Every digraph D with maximum degree ∆ ≥ 3 satisfies dst(D) ≤ ∆.

The condition ∆ ≥ 3 in the above conjecture is necessary since the odd circuits have maximum degree 2 and directed star arboricity 3. This conjecture would be tight since every digraph with a vertex with in-degree ∆ (and out-degree 0) has directed star arboricity at least ∆. In [START_REF] Amini | WDM and directed star arboricity[END_REF], Amini et al. proved that Conjecture 16 holds when ∆ = 3.

A nice galaxy in a digraph G is a galaxy spanning all the vertices of maximum degree. To prove Conjecture 16 by induction on the maximum degree, it suffices to show that every digraph with maximum degree ∆ ≥ 4 has a nice galaxy.

Conjecture 17 (Amini et al. [START_REF] Amini | WDM and directed star arboricity[END_REF]). Every digraph with maximum degree ∆ ≥ 4 has a nice galaxy.

Amini et al. [START_REF] Amini | WDM and directed star arboricity[END_REF] showed the conjecture for 2-diregular digraphs. In this section, we prove Conjecture 17 for acyclic digraphs, which implies Conjecture 16 for acyclic digraphs. We also prove that every digraph has a galaxy spanning the vertices with in-degree at least two and derive that dst(D) ≤ ∆(D) + 1 for every digraph D.

Acyclic digraphs

In this subsection, we settle Conjecture 17 for acyclic digraphs and derive that Conjecture 16 holds for acyclic digraphs. To do so, we need the following lemma on odd-cycles+matching graphs. An odd-cycles+matching graph is the disjoint union of odd cycles and a matching.

Lemma 18. Every graph with at least one edge has an odd-cycles+matching subgraph spanning all the vertices of maximum degree.

Proof . Let G be a graph of maximum degree ∆ and V ∆ be the set of vertices of degree ∆. The result holds trivially if ∆ = 1 so we may assume that ∆ ≥ 2. Let H be an odd-cycles+matching subgraph that spans the maximum number of vertices of V ∆ . Let C 1 , . . . , C p be the odd cycles of H and M its matching. Suppose by way of contradiction that there is a vertex v in V ∆ \ V (H). An alternating v-path is a path starting at v such that every even edge is in M (and so every odd edge is not in M ). Let A 0 (resp. A 1 ) be the set of vertices u such that there exists a v-alternating path of even (resp. odd) length ending at u. Note that v ∈ A 0 as (v) is an alternating v-path of length 0.

Claim 5. A 0 ⊂ V ∆ .
Suppose that A 0 ⊂ V ∆ . Then there is a vertex x ∈ A 0 \ V ∆ . Let P be the even alternating v-path ending at x. Then the odd-cycles+matching subgraph obtained from H by replacing the matching M by M ′ = M △P spans one more vertex of V ∆ , namely v, than H. This is a contradiction.

Claim 6. A 1 ⊆ V (H).
vertices of maximum degree. The subdigraph D ′ of D which is an orientation of H is the union of oriented odd circuits and a matching. Each oriented circuit is not directed because D is acyclic, and thus has a spanning galaxy. Hence D ′ has a spanning galaxy, which is a nice galaxy of D. By induction, D ′ has an arc-partition into k -1 galaxies F 1 , . . . , F k-1 . Thus (F 1 , . . . , F k ) is an arc-partition of D into k galaxies.

Galaxy spanning the vertices with in-degree at least two

Let D be a digraph. The out-section of a vertex x is the set S + (x) of vertices y to which there exists a directed path from x. An out-generator of D is a vertex x ∈ V (D) such that S + (x) = V (D). Note that if D is strong, every vertex is an out-generator. Every out-generator is the root of a spanning arborescence, so by Lemma 2 we get the following: In order to prove this theorem, we need the following folklore proposition. We give its proof for sake of completeness.

Proposition 23. Let D be a strong digraph with minimum in-degree 2. Then there is a vertex x such that Dx is strong.

Proof . Consider a handle decomposition minimizing the number of trivial handles. Let (x 0 , . . . , x l ) be the last non-trivial handle. The vertex x l-1 has in-degree at least two, hence the other arcs entering x l-1 are trivial handles. If l is greater than 2, any of these trivial handles, together with x 0 , . . . , x l would result in two non-trivial handles -which is impossible by assumption. Thus l = 2, and then the vertex x 1 can be deleted.

Proof of Theorem 22. We prove the result by induction on the number of arcs.

If D has an arc a entering a vertex of in-degree either 1 or more than 2, then by induction D \ a has a galaxy G spanning all the vertices with in-degree at least 2 in D \ a. But the vertices with in-degree at least 2 in D have also in-degree at least 2 in D \ a. Hence G spans all the vertices with in-degree at least 2 in D \ a.

Henceforth, we assume that every vertex of D has in-degree 2 or 0. Suppose first that D contains a vertex v of in-degree 0. Set D + = D[S + (v)] and D ′ = D -D + . By definition of out-section, there are no arcs leaving D + . So the vertices of D ′ have the same in-degree in D ′ and D. By the induction hypothesis, there is a galaxy F ′ spanning all the vertices of D ′ with in-degree 2 and by Corollary 21, there is a galaxy F + spanning all the vertices of D + with indegree 2. The union of F ′ and F + is the desired galaxy.

Suppose now that all the vertices of D have in-degree 2. Consider an initial strong component C of D, that is a strong component C such that all the arcs with head in C have their tail in C. By Proposition 23, there exists a vertex

v of C such that C -v is strong. Let S + be the out-section of v in D -(C \ {v}) and T = S + D (v) \ S + and D ′ = D -S + D (v). Note that v is an out-generator of D[S + ] and D 1 = D[T ∪ {v}]. Moreover since C -v is strong, every vertex of C -v is an out-generator of D 2 = D[T ].
By the induction hypothesis, there is a galaxy F ′ spanning all the vertices of D ′ with in-degree 2. By Corollary 21, there is a galaxy F + of D[S + ] spanning all the vertices of S + \ {v} in which v is either not spanned or a root. If v is a root of F + then, by Corollary 21, there is a galaxy F 1 of D 1 spanning all the vertices of T in which v is either not spanned or a root. The union of F ′ , F + and F 1 is a spanning galaxy of D. If v is not a root of F + , let u be an in-neighbour of v. By Corollary 21, there is a galaxy F 2 of D 2 spanning all the vertices of T \ {u} in which u is either not spanned or a root. The union of F ′ , F + , F 2 and the arc uv is a spanning galaxy of D.

Note that Theorem 22 implies the result of Amini et al. [START_REF] Amini | WDM and directed star arboricity[END_REF] that a 2-diregular digraph has a spanning galaxy.

Theorem 24. Let D be a digraph with maximum degree ∆ ≥ 2. Then dst(D) ≤ ∆ + 1.

Proof . Set D 0 = D. For every i from 1 to ∆ -2, let F i be a galaxy spanning all the vertices of in-degree at least 2 in D i-1 and D i = D i-1 \ E(F i ). Observe that a vertex of D ′ = D ∆-2 has either in-degree at most one or in-degree 2 and out-degree 0. Now we just have to prove that dst(D ′ ) ≤ 3. For this, choose one arc entering each vertex with in-degree two and denote the set of these arcs by F . In the graph D ′ \ F every vertex has in-degree exactly 1. Consider a 3-colouring of the arcs of D ′ \ F such that each colour class induces a galaxy. This is possible because D ′ \ F is a disjoint union of functional graphs. Then for every arc xy of F , at most two colours are forbidden, one by the other arc entering x, and another by the arc entering y. Indeed, x has no out-neighbour except y and y has in-degree at most one (since d + (y) > 0).

Open questions

Deciding if a strong digraph has an even strong subdigraph is polynomialtime solvable. By Theorem 9, this is equivalent to deciding if strong digraph contains an even circuit or an even theta. Deciding whether a strong digraph contains an even circuit can be solved in polynomial time [START_REF] Mccuaig | Pólya's permanent problem[END_REF][START_REF] Robertson | Permanents, Pfaffian orientations, and even directed circuits[END_REF]. Hence a natural question is the following.

Problem 25. Can we decide in polynomial time whether a strong digraph contains an even theta? One can also search for even thetas or circuits using or avoiding a prespecified arc. Thomassen [START_REF] Thomassen | Even cycles in directed graphs[END_REF] showed that it is NP-complete to decide whether a digraph D has an even circuit containing a given arc. Theorem 13 states that it is polynomial-time decidable if a digraph has an even strong subdigraph containing a given arc. Hence it is natural to ask the following two questions.

Problem 26. Can we decide in polynomial time whether a digraph has an even theta containing a given arc?

Problem 27. Can we decide in polynomial time whether a digraph has an even circuit or an even theta containing a given arc ?

Observe that Theorems 13 and 9 do not imply an affirmative answer to Problem 27. Indeed, there are even strong subdigraphs with some arcs in no even circuit nor even theta. For example, consider the even digraph with vertex set {a 1 , . . . , a 8 } and edges {a i a i+1 | 1 ≤ i ≤ 6} ∪ {a 4 a 1 , a 5 a 8 , a 8 a 4 , a 7 a 5 }. It is easy to check that the arcs a 5 a 6 , a 6 a 7 and a 7 a 5 are in no even circuit and in no even theta.

It is easy to find a polynomial-time algorithm to decide whether a digraph D has an even circuit avoiding a given arc uv: it suffices to test whether D \ {uv} has an even circuit or not. Similarly, one can decide in polynomial time whether a digraph D has an even circuit or an even theta avoiding a given arc uv, by testing if one of the strong components of D \ {uv} contains an even strong subdigraph. But we do not know about the complexity of testing if a digraph has an even theta avoiding a prespecified arc.

Problem 28. Can we decide in polynomial time whether a digraph has an even theta avoiding a given arc ?

  The gadget for the variable x.

2 (

 2 b) The gadget for the clause c = (x 1 ∨x 2 ∨x 3 ).

Figure 1 :

 1 Figure 1: The gadgets for Theorem 7.

( 4 )

 4 ⇔ (2). It is clear that a strong digraph D has an even handle decomposition if and only if D does. Thus, since (4) ⇔ (1), a strong digraph D has an even handle decomposition if and only if D has a spanning galaxy.Since every vertex v of every strong digraph D is the root of an arborescence T , by Lemma 2, for every strong digraph D and every vertex v of D, D has a galaxy spanning every vertex except possibly v. This can be improved as follows.Theorem 10. A strong digraph D has either a spanning galaxy or for every v ∈ V (D), D has a matching spanning every vertex except v.

Claim 4 .

 4 D has an ESS if and only if D[S] has an ESS or D ′ has an ESS. Since every subdigraph of D[S] is a subdigraph of D, if D[S] has an ESS, then D has an ESS. Therefore, we may suppose that D[S] does not have an ESS. For every ESS E of D, the digraph

  k-Galaxy problem Instance: A digraph D and an integer k. Parameter: k. Question: Does D have a galaxy spanning at least k vertices?

( a )

 a The vertices of V (D) \ V (F ) form a stable set. (b) If uv ∈ A(F ) and uw ∈ A(D), then we have w ∈ V (F ). (c) If u ∈ V (F ) and uv, uw ∈ A(D), at least one of v and w belong to V (F ).(d) If uv, uw ∈ A(F ) and wx ∈ A(D), then x ∈ V (F ).

Step 4 :

 4 Compute a maximum matching M in the bipartite graph induced by the arcs from N -(G) to V (G); Step 5: If |V (M )| > |V (G)| then G := M and go to Step 2;

G

  has at most k -1 vertices because of Step 6. Since G is locally maximal, we have |N + (G)| ≤ |V (G)|/2 because of the conditions (b), (c) and (d). Finally, |V (M )| ≤ |V (G)| because of Step 5 and |V (M )\V (G)| = |V (M )|/2 by definition of M . Hence |V (D ′ )| ≤ 2|V (G)| ≤ 2k -2.

Corollary 20 .

 20 If D is an acyclic digraph then dst(D) ≤ ∆(D). Proof . We prove the result by induction on ∆(D), the result holding trivially when ∆(D) = 1. Suppose now ∆(D) = k > 1. By Theorem 19, D has a nice galaxy F k . Hence D ′ = D \ E(F k ) has maximum degree at most k -1.

Corollary 21 .

 21 Let v be an out-generator of a digraph D. Then D contains a galaxy F spanning all the vertices of Dv. Theorem 22. Every digraph D has a galaxy spanning all the vertices with indegree at least 2.

Suppose by way of contradiction that a vertex x ∈ A 1 is in V (G) \ V (H). Let P be an odd alternating v-path ending at x. Then the odd-cycles+matching subgraph obtained form H by replacing the matching M by M ′ = M △P spans one more vertex of V ∆ , namely v, than H. This is a contradiction.

Suppose by way of contradiction that a vertex x ∈ A 1 is in p i=1 C i , say in C p . Then C px has a matching M 1 . Let P be an odd alternating v-path ending at x. This path of odd length has a perfect matching M 2 = P \ M . Thus the disjoint union of C 1 , . . . , C p-1 and (M \ P ) ∪ M 1 ∪ M 2 is an odd-cycles+matching subgraph spanning one more vertex of V ∆ , namely v, than M . This is a contradiction.

Indeed, M matches every vertex of A 0 , except v, with a vertex of A 1 , and vice versa.

Suppose to the contrary that there exist two adjacent vertices x and y in A 0 . Let P x and P y be two even alternating v-path ending at x and y, respectively. We choose x, y, P x and P y in such a way that |V (P x ) ∪ V (P y )| is minimum. Note that P x and P y may share common vertices and arcs at the beginning. If xy ∈ M , then x is the predecessor of y in P y and vice-versa. In this case let Q y = P xy and Q x = P yx. Otherwise let Q x = P x and Q y = P y . In both cases, Q x and Q y are alternating v-paths of same parity. Note that by minimality of |V (P x ) ∪ V (P y )| there exists only one vertex z ∈ V (Q x ) ∩ V (Q y ) (possibly z = v) and three paths Q v-z , Q z-x and Q z-y , going respectively from v to z, from z to x and from z to y such that

Note that we necessarily have z ∈ A 0 since every odd vertex in Q x and Q y is followed by its neighbour in M . Let C p+1 be the odd cycle formed by the paths Q z-x and Q z-y , and by the edge xy. Then the odd-cycles+matching subgraph obtained from H by replacing the matching M by M ′ = M △Q v-z and adding the odd cycle C p+1 spans one more vertex of V ∆ than H. This is a contradiction. By Claim 9, all the edges with an end in A 0 have the other end in A 1 and thus, by Claims 5 and 8, there are |A 0 | × ∆ = (|A 1 | + 1) × ∆ edges between A 0 and A 1 . This is impossible because the vertices in A 1 have degree at most ∆. This contradicts the existence of v and thus proves the Lemma.