domain: info math

text:
Stéphane Bessy
email: stephane.bessy@lirmm.fr

Florian Hörsch
email: florian.hoersch@tu-ilmenau.de

Ana Karolinna
email: karolmaia@ufc.br

Dieter Rautenbach
email: dieter.rautenbach@uni-ulm.de

Ignasi Sau
email: ignasi.sau@lirmm.fr

FPT algorithms for packing k-safe spanning rooted sub(di)graphs

Keywords: 2012 ACM Subject Classification Design and analysis of algorithms → Fixed parameter tractability Digraphs, packing problems, arborescences, branching flows, safe spanning trees, parameterized complexity, fixed-parameter tractability

We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced" spanning rooted substructures in graphs and digraphs, which generalize classic packing problems such as detecting the existence of mutiple arc-disjoint spanning arborescences. Namely, given a positive integer k, a digraph D = (V, A), and a root r ∈ V , we first consider the problem of finding two arc-disjoint k-safe spanning r-arborescences, meaning arborescences rooted at a vertex r such that deleting any arc rv and every vertex in the sub-arborescence rooted at v leaves at least k vertices. Then, we consider the problem of finding two arc-disjoint (r, k)-flow branchings meaning arc sets admitting a flow that distributes one unit from r to every other vertex while respecting a capacity limit of n -k on every arc. We show that both these problems are FPT with parameter k, improving on existing XP algorithms. The latter of these results answers a question of Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016]. Further, given a positive integer k, a graph G = (V, E), and r ∈ V , we consider the problem of finding two edge-disjoint (r, k)-safe spanning trees meaning spanning trees such that the component containing r has size at least k when deleting any vertex different from r. We show that this problem is also FPT with parameter k, again improving on a previous XP algorithm. Our main technical contribution is to prove that the existence of such spanning substructures is equivalent to the existence of substructures with size and maximum (out-)degree both bounded by a (linear or quadratic) function of k, which may be of independent interest.

Introduction

This article deals with finding certain disjoint substructures in graphs and digraphs. Throughout the article, when given a graph or a digraph, we use n for its number of vertices. All graphs and digraphs considered in this paper are loopless, but may have multiple edges or arcs. Given a graph G = (V, E), we say that an edge e = uv is incident to u and v. For some X ⊆ V , we denote by d G (X) the number of edges that are incident to exactly one vertex in X. For some v ∈ V , we use N G (v) for the set of vertices w such that there is an edge in E between v and w. Further, we use δ G (v) for the set of edges incident to v and

d G (v) for |δ G (v)|. A vertex v ∈ V with d G (v) = 1 is called a leaf of G.
A rooted graph is a graph G = (V + r, E) with a special vertex r called the root. Note that r / ∈ V and V (G) = V + r. If G = (r, ∅), we say that r is a terminal of G. Otherwise, the set of terminals in G is the set of leaves in V .

Given a digraph D = (V, A) and some X ⊆ V , we use δ - D (X) (resp. δ + D (X)) for the set of arcs entering (resp. leaving) X. We use d - D (X) (resp. d + D (X)) for |δ - D (X)| (resp. |δ + D (X)|). For a single vertex v, we abbreviate δ + D ({v}) (resp. δ - D ({v}),

d + D ({v}), d - D ({v})) to δ + D (v) (resp. δ - D (v), d + D (v), d - D (v)). We call d - D (v) (resp. d + D (v)
) the in-degree (resp. out-degree) of v. We use N + D (v) for the set of vertices w such that there is an arc in A from v to w. A vertex v ∈ V with d + (v) = 0 is called a sink of D. Subscripts may be omitted when they are clear from the context. The underlying graph of D is obtained by replacing each arc of A by an edge between the same two vertices. A rooted digraph is a digraph D = (V + r, A) with a special vertex r, called the root, whose in-degree is 0. As before, observe that r / ∈ V and V (D) = V + r.

Packing k-safe spanning r-arborescences. The first objects we deal with are called arborescences. We remark here that the term out-branching is used in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] to describe the same object. An r-arborescence is a directed graph X = (V + r, A) such that the underlying graph of X is a tree, the in-degree of r is 0 in X, and the in-degree of all other vertices is 1 in X. We say that r is the root of X. Observe that every v ∈ V is the root of a unique maximal subarborescence of X. We denote this subarborescence by B v X . Given a digraph D, an r-arborescence X that is a subdigraph of D is spanning in D if it has the same vertex set as D. The following is a fundamental result in digraph theory.

▶ Theorem 1 (Edmonds [6]). Let D = (V + r, A) be a rooted digraph and k a positive integer. There exists a set of k arc-disjoint spanning r-arborescences in D if and only if d - D (X) ≥ k for every ∅ ̸ = X ⊆ V.

A number of alternative proofs of Theorem 1 have been found, several of which are algorithmic and yield polynomial-time algorithms to find the desired arc-disjoint spanning r-arborescences, if they exist [START_REF] Edmonds | Some well-solved problems in combinatorial optimization[END_REF][START_REF] Lovász | Connectivity in digraphs[END_REF].

This naturally raises the question whether we also can efficiently find spanning arborescences satisfying some extra properties. This consideration, as well as practical applications concerning protection against arc failures, motivated Bang-Jensen and Yeo [START_REF] Bang | Balanced branchings in digraphs[END_REF] to introduce the notion of k-safe spanning arborescences. For a positive integer k, an r-arborescence X = (V + r, A) is called k-safe if n -|V (B v X )| ≥ k for every v ∈ V . Notice that it is enough that only the out-neighbours of r satisfy this latter condition for X to be k-safe. They proved a negative result showing that in general even the problem of finding a single k-safe spanning r-arborescence is hard. More specifically, they showed that deciding whether a rooted digraph D = (V + r, A) has an (n -k)-safe spanning r-arborescence is NP-complete for any fixed k ≥ 3.

In this light, a characterization in the shape of Theorem 1 clearly seems out of reach. It nevertheless remains interesting to investigate the possibility of finding arc-disjoint k-safe spanning r-arborescences for small values of k. This question has been dealt with by Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]. On the negative side, they implicitly proved the following result, which shows that there is little hope to algorithmically find arc-disjoint k(n)-safe spanning r-arborescences if k is a function that does not grow too slowly. While a polynomial-time algorithm for the problem they consider would not imply P = NP, it would imply the failure of the Exponential Time Hypothesis (ETH for short) of Impagliazzo and Paturi [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF], stating that there is an ε > 0 such that there is no algorithm for solving a 3-Sat formula with ℓ variables and m clauses in time 2 εℓ • (ℓ + m) O (1) .

▶ Theorem 2 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Suppose that the ETH holds, let ε > 0 be arbitrary and let k : Z ≥0 → Z ≥0 be a function such that (log(n)) 1+ε ≤ k(n) ≤ n 2 for every n > 0. Further, suppose that there exists a constant C * such that for every integer c ≥ C * there exists an n such that k(n) = c. Then there is no algorithm running in time n O (1) for deciding whether a given rooted digraph D = (V + r, A) has two arc-disjoint k(n)-safe spanning r-arborescences.

In particular, it is possible to obtain the following lower bound for the running time of any algorithm deciding whether a given rooted digraph D = (V + r, A) has two arc-disjoint k(n)-safe spanning r-arborescences.

▶ Corollary 3. Unless the ETH fails, there is no algorithm deciding whether a given rooted digraph D = (V + r, A) has two arc-disjoint k-safe spanning r-arborescences that runs in (1) time for some ε > 0 and c > 0.

2 c•k 1-ε • n O
Indeed, if an algorithm as above existed, for k(n) := (log(n)) 1+ε , we would obtain an algorithm running in time 2 c•(log(n)) (1+ε) (1-ε) • n O (1) = n O (1) , contradicting Theorem 2.

On the positive side, they show that the problem becomes tractable when fixing the value of k. While the main results considered in this article hold for finding an arbitrary number of disjoint objects, we only present the case where we want to find just two of them, in order to avoid technicalities. In Section 7 we discuss the generalization to more than two objects.

▶ Theorem 4 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Deciding whether a given rooted digraph D = (V + r, A) contains two arc-disjoint k-safe spanning r-arborescences is XP with parameter k.

The definition of the classes XP and FPT can be found in Subsection 2.5. Our first contribution is to improve Theorem 4 by showing that the problem is fixed-parameter tractable (FPT). (1) . Further, if they exist, the two arc-disjoint k-safe spanning r-arborescences can be computed within the same running time.

▶ Theorem 5. Deciding whether a given rooted digraph

D = (V + r, A) contains two arc- disjoint k-safe spanning r-arborescences is FPT with parameter k. More precisely, it can be solved in time 2 O(k 2 •log k) • n O
Packing (r, k)-flow branchings. The second structure we consider, which was introduced by Bang-Jensen and Bessy [START_REF] Bang-Jensen | arc-)disjoint flows in networks[END_REF], builds a connection between the theory of finding arc-disjoint spanning arborescences and flow problems. A flow in a rooted digraph

X = (V + r, A) is a function z : A → Z ≥0 . For some A ′ ⊆ A, we abbreviate a∈A ′ z(a) to z(A ′ ). Recall that n = |V |+. Given a capacity function c : A → Z ≥0 , an (r, n -c)-branching flow is a flow z : A → Z ≥0 such that z(a) ≤ c(a) for every a ∈ A, z(δ + (r)) -z(δ -(r)) = n -1 and z(δ -(v)) -z(δ + (v)) = 1 for every v ∈ V .
In other words, the idea is that z reaches all vertices of X from r and each vertex other than r retains one unit of flow. If X admits an (r, n -c)-branching flow, we say that X is an (r, n -c)-flow branching. If for some positive integer k, we have c(a) = n -k for all a ∈ A, we speak of an (r, k)-branching flow and an (r, k)-flow branching. Given a digraph D, an (r, k)-flow branching X that is a subdigraph of D is spanning in D if it has the same vertex set as D. If D admits a k-safe spanning r-arborescence, then it is easy to see that D is an (r, k)-flow branching, but the converse is not necessarily true, as pointed out in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]. In particular, observe that the underlying graph of an arc-minimal (r, k)-flow branching is not necessarily acyclic.

Bang-Jensen and Bessy [START_REF] Bang-Jensen | arc-)disjoint flows in networks[END_REF] showed that the problem of deciding if a rooted digraph has two arc-disjoint spanning flow branchings is NP-complete if every arc has capacity at most two. This result has been strengthened in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] to the case of capacities all being equal to some fixed k ≥ 2. The following result is proven in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]. It shows that there is little hope to algorithmically find arc-disjoint spanning (r, k(n))-flow branchings if k is a function that does not grow too slowly. It can be viewed as an analogue of Theorem 2 for (r, k)-flow branchings.

▶ Theorem 6 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Suppose that ETH holds, let ε > 0 be arbitrary and let k :

Z ≥0 → Z ≥0 be a function such that (log(n)) 1+ε ≤ k(n) ≤ n
2 for every n > 0. Further, suppose that there exists a constant C * such that for every integer c ≥ C * there exists an n such that k(n) = c. Then there is no algorithm running in time n O (1) for deciding whether a given rooted digraph D = (V + r, A) has two arc-disjoint spanning (r, k(n))-flow branchings.

In a similar way as Corollary 3 can be concluded from Theorem 2, the following result is obtained from Theorem 6. ▶ Corollary 7. Unless the ETH fails, there is no algorithm deciding whether a given rooted digraph D = (V + r, A) has two arc-disjoint spanning (r, k)-flow branchings that runs in (1) time for some ε > 0 and c > 0.

2 c•k 1-ε • n O
On the other hand, the problem of finding arc-disjoint spanning (r, k)-flow branchings for some small values of k turns out to be more tractable. The study of such spanning flow branchings has surprisingly many similarities with the study of k-safe spanning arborescences. Bang-Jensen and Bessy [START_REF] Bang-Jensen | arc-)disjoint flows in networks[END_REF] showed that the case k = 1 can be solved in polynomial time. This result was again generalized by Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], who proved that the problem can be solved in polynomial time for every fixed value of k ≥ 1. The following result can be viewed as an analogue of Theorem 4 for (r, k)-flow branchings.

▶ Theorem 8 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Deciding whether a given rooted digraph D = (V + r, A) contains two arc-disjoint spanning (r, k)-flow branchings is XP with parameter k.

The authors of [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] ask whether the above problem is FPT. Our second contribution is an affirmative answer to this question. (1) . Further, if they exist, the two arc-disjoint spanning (r, k)-flow branchings can be computed within the same running time.

▶ Theorem 9. Deciding whether a given rooted digraph

D = (V + r, A) contains two arc- disjoint spanning (r, k)-flow branchings is FPT with parameter k. More precisely, it can be solved in time 2 O(k 2 •log k) • n O
Packing (r, k)-safe spanning trees. Finally, we consider a similar problem in undirected graphs that has also been introduced in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]. Given a graph G = (V, E), a spanning tree is a subgraph T of G that is a tree with V (T ) = V . The theory of finding edge-disjoint spanning trees is also pretty rich. The most fundamental result is the following one.

▶ Theorem 10 (Tutte [START_REF] William | On the problem of decomposing a graph into n connected factors[END_REF]). Let G = (V, E) be a graph and p a positive integer. Then G has p edge-disjoint spanning trees if and only if

q i=1 d G (V i ) ≥ 2p(q -1) for every partition {V 1 , . . . , V q } of V .
An algorithmic proof of Theorem 10, yielding a polynomial-time algorithm for finding the spanning trees, if they exist, can be found as the proof of Theorem 10.5.1 in [START_REF] Frank | Connections in Combinatorial Optimization[END_REF]. Again, we may wish to also find edge-disjoint spanning trees satisfying certain extra properties. Given a rooted tree T = (V + r, E) and some v ∈ V , we use

C v T for the subgraph of T -v that arises from deleting the component of T -v containing r. Observe that v / ∈ V (C v T ). We say that T is (r, k)-safe if for every v ∈ V , we have |V -V (C v T )| ≥ k.
▶ Theorem 11 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Deciding whether a given rooted graph G = (V + r, E) contains two edge-disjoint (r, k)-safe spanning trees is XP with parameter k.

Again, we improve Theorem 11 as follows.

▶ Theorem 12. Deciding whether a given rooted graph G = (V + r, E) contains two edgedisjoint (r, k)-safe spanning trees is FPT with parameter k. More precisely, it can be solved in time 1) . Further, if they exist, the two edge-disjoint (r, k)-safe spanning trees can be computed within the same running time.

2 O(k 2 •log k) • n O(
Since a hardness result in the spirit of Theorem 2 and Theorem 6 was not provided in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], we fill this gap and prove the following theorem, whose proof is inspired by the one of [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]Theorem 5.2]. It shows that the problem is hard even if we want to find one single (r, k)-safe spanning tree.

▶ Theorem 13. Let p ≥ 1 be a fixed positive integer. Deciding whether a given rooted graph G = (V + r, E) has p edge-disjoint (r, k)-safe spanning trees is NP-complete. Moreover, let ε > 0 be arbitrary and let k :

Z ≥0 → Z ≥0 be a function such that (log(n)) 2+ε ≤ k(n) ≤ n
2 for all n > 0. Further, suppose that there exists a constant C * such that for every integer c ≥ C * there exists an n such that k(n) = c. Then, assuming the ETH, there is no algorithm running in time n O (1) for deciding whether a given rooted graph has p edge-disjoint (r, k(n))-safe spanning trees.

Again, in a similar way as Corollary 3 can be concluded from Theorem 2, the following result is obtained from Theorem 13. ▶ Corollary 14. Unless the ETH fails, there is no algorithm deciding whether a given rooted digraph D = (V + r, A) has two edge-disjoint spanning (r, k)-safe spanning trees that runs in 1) time for some ε > 0 and c > 0.

2 c•k 1 2 -ε • n O(
Our techniques. In order to obtain the FPT algorithms for the three considered problems, we follow a common strategy. In a nutshell, the main ideas used in the XP algorithms of [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], and how we manage to improve them to FPT algorithms, can be summarized as follows. The algorithms of Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] are all based on proving the following general property for each of the considered problems, where all the substructures are rooted:

A given (di)graph contains the required substructure X (i.e., a pair of disjoint k-safe spanning arborescences, flow branchings, or spanning trees) if and only if it contains another type of substructure X ′ (i.e., a pair of appropriately defined disjoint objects) of size bounded by a function of k and that can be extended to the substructure X in polynomial time.

We would like to stress that the above property is deliberately abstract in order to capture the essential common property that can be used for all the considered problems. More informally, it states that, instead of finding the required substructure X , which may have arbitrary size (in particular, not depending only on k), we can safely focus on finding another substructure X ′ , with the guarantee that it can always be extended to X in polynomial time, and with the following crucial property that is exploited in the corresponding algorithms, as discussed below: the size of X ′ is bounded by a function depending only on the parameter k.

Once the above property is proved, an XP algorithm follows naturally: generate all candidate substructures X ′ in time n f (k) and, for each of them, try to extend it to a substructure X in polynomial time. Our main contribution is to prove that the above general property is still true if we replace X ′ with another type of substructure X ′′ having the crucial property that the candidate substructures X ′′ can be enumerated in time f (k) • n O (1) , hence yielding an FPT algorithm. In order to achieve this, we prove that we can restrict ourselves to objects X ′′ whose "non-sink" vertices (i.e., those with positive (out-)degree in X ′′ ) have (out-)degree, in the original (di)graph, bounded by some function of k, namely O(k) or O(k 2 ). This is possible because, given a pair X ′ = {X 1 , X 2 } containing a vertex v of large (out-)degree (as a function of k) in, say, X 1 , we can safely prune the "branch" of X 1 hanging from v, with the guarantee that it will always be possible to extend the pruned substructure to another substructure of the original type. Note that since the substructures X ′′ have size and maximum (out-)degree bounded by a function of k, we can indeed generate all candidate substructures in time f (k) • n O (1) , as required. We now make this informal explanation more concrete. For all technical definitions used in the next paragraphs, see Section 2.

Let us first focus on the problem of finding two arc-disjoint k-safe spanning r-arborescences. In this case, the substructure X ′ is an extendable pair of arc-disjoint classic (r, k)-kernels 1 . In Lemma 20, we restate a result from [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] that shows that the existence of this substructure is sufficient for the existence of two arc-disjoint k-safe spanning r-arborescences. We then introduce compact (r, k)-kernels. An extendable pair of arc-disjoint compact (r, k)-kernels corresponds to the substructure X ′′ . In Lemma 28, we show that the existence of an extendable pair of arc-disjoint compact (r, k)-kernels is also sufficient for the existence of two arc-disjoint k-safe spanning r-arborescences. The proof of Lemma 28 is our main technical contribution. Having Lemma 28 at hand, the proof of Theorem 5 is easy.

As for packing (r, k)-flow branchings, the substructure X ′ defined in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] is an extendable pair of arc-disjoint classic (r, k)-cores. In Lemma 24, we restate a result from [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] that shows that the existence of this substructure is sufficient for the existence of two arc-disjoint (r, k)flow branchings. We then introduce compact (r, k)-cores. An extendable pair of arc-disjoint compact (r, k)-cores corresponds to the substructure X ′′ . In Lemma 30, we show that the existence of an extendable pair of arc-disjoint compact (r, k)-cores is also sufficient for the existence of two arc-disjoint (r, k)-flow branchings. Again, the proof of Lemma 30 is our main technical contribution and is similar to the one of Lemma 28. Again, having Lemma 30 at hand, the proof of Theorem 9 is easy.

Finally, for packing (r, k)-safe spanning trees, the substructure X ′ defined in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] is a completable pair of edge-disjoint classic (r, k)-certificates. In Lemma 26, we restate a result from [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] that shows that the existence of this substructure is sufficient for the existence of two edge-disjoint (r, k)-safe spanning trees. We then introduce compact (r, k)-certificates. A completable pair of edge-disjoint compact (r, k)-certificates corresponds to the substructure X ′′ . In Lemma 32, we show that the existence of a completable pair of edge-disjoint compact (r, k)-certificates is also sufficient for the existence of two edge-disjoint (r, k)-safe spanning trees. Again, the proof of Lemma 32 is our main technical contribution and is similar to the ones of Lemma 28 and Lemma 30. However, while the proofs of Lemma 28 and Lemma 30 use a property on extendable structures proven in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], the proof of Lemma 32 relies on a spanning tree reconfiguration argument. Again, having Lemma 32 at hand, the proof of Theorem 12 is easy.

Organization. In Section 2 we review some more technical results we need from [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], prove several preliminary results, and provide the basic definitions about parameterized complexity. In Section 3, Section 4, Section 5, and Section 6 we give the proof of Theorem 5, Theorem 9, Theorem 12, and Theorem 13, respectively. Finally, we conclude our work in Section 7.

Preliminaries

In this section we collect some more technical previous results and prove several preliminary statements. We first give some general results on graphs and digraphs and then some which are more specific to each of the particular applications. We also provide some basic definitions about parameterized complexity.

General preliminaries

The following is a well-known submodularity property of digraphs that can be found, for instance, in [8, Proposition 1.2.1].

▶ Proposition 15. Let D = (V, A) be a digraph and S 1 , S 2 ⊆ V . Then d - D (S 1 ) + d - D (S 2 ) ≥ d - D (S 1 ∪ S 2 ) + d - D (S 1 ∩ S 2 ). A rooted digraph D = (V + r, A) is called ℓ-root-connected if d - D (X)
≥ ℓ for every X ⊆ V . We use root-connected for 1-root-connected. In a root-connected rooted digraph D = (V + r, A), an arc a ∈ A is called critical if D -a is not root-connected anymore. We now use Proposition 15 to obtain a result that will be useful when dealing with both k-safe spanning r-arborescences and spanning (r, k)-flow branchings.

▶ Lemma 16. Let D = (V +r, A) be a 2-root-connected rooted digraph and let D ′ = (V +r, A ′ ) be a root-connected rooted digraph that is obtained from D by deleting α arcs of A. Then for any v ∈ V + r, there are at most α arcs which are critical in D ′ and whose tail is v.

Proof. We proceed by induction on α. The statement is trivial for α = 0. We suppose that it holds for all integers up to some α and show that it also holds for α + 1. Let v ∈ V + r and let {a 1 , . . . , a α+1 } be a set of arcs in A such that D 2 = D -{a 1 , . . . , a α+1 } is root-connected. By the inductive hypothesis, v is the tail of at most α critical arcs in D 1 = D -{a 1 , . . . , a α }. Suppose, for the sake of a contradiction, that there are two arcs vw 1 , vw 2 which are critical in

D 2 , but not in D 1 . It follows that there are sets X 1 , X 2 ⊆ V such that d - D2 (X 1 ), d - D2 (X 2 ) = 1, d - D1 (X 1 ), d - D1 (X 2 ) = 2, and vw i enters X i . Since D 2 = D 1 -a α+1 , it follows that a α+1 enters X 1 ∩ X 2 , so X 1 ∩ X 2 ̸ = ∅. As D 2 is root-connected, we have d - D2 (X 1 ∩ X 2 ) ≥ 1. As vw i enters X i , we have v ∈ V + r -(X 1 ∪ X 2 ) and so both vw 1 and vw 2 enter X 1 ∪ X 2 . This yields d - D2 (X 1 ) + d - D2 (X 2 ) = 1 + 1 < 1 + 2 ≤ d - D2 (X 1 ∩ X 2 ) + d - D2 (X 1 ∪ X 2 ), a contradiction to Proposition 15. ◀ Given a 2-root-connected rooted digraph D = (V + r, A), a pair of subdigraphs (X 1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 )) of D is called extendable if both D -A 1 and D -A 2 are root-connected.
The following is an immediate consequence of the fact that checking whether a digraph is root-connected can clearly be done in polynomial time using a breadth-first search algorithm.

▶ Lemma 17. Given a rooted digraph D = (V + r, A) and a pair of two subdigraphs

(X 1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 )), we can decide in polynomial time whether (X 1 , X 2 ) is extendable.
We now switch to undirected graphs. The following is an easy known result, whose proof is provided for the sake of completeness.

▶ Lemma 18. Let G = (V, E) be a graph and let T be a spanning tree of G. Let e = uv ∈ E -E(T ). Then there is some f ∈ E(T ) that is incident to u such that T + e -f is a spanning tree of G.

Proof. The graph T + e contains a unique cycle C such that uv ∈ E(C) and the deletion of an arbitrary edge of E(C) yields a spanning tree of G. As C is is a cycle, E(C) contains an edge f different from e that is incident to u. This edge satisfies the condition. ◀

Given two spanning trees T 1 , T 2 of a graph G, we say that a function σ : E(T 1 ) → E(T 2 ) is a tree-mapping function if for every e ∈ E(T 1 ), both T 1 -e + σ(e) and T 2 -σ(e) + e are spanning trees of G. It is well-known that a tree-mapping function exists for any two spanning trees T 1 , T 2 of a graph G, see for example [START_REF] Frank | Connections in Combinatorial Optimization[END_REF]Theorem 5.3.3].

▶ Lemma 19. Let G = (V, E) be a graph, let T 1 , T 2 spanning trees of G, σ : E(T 1 ) → E(T 2 ) a tree-mapping function from T 1 to T 2 and F ⊆ δ T1 (v) for some v ∈ V . Then {σ(e) : e ∈ F } contains at least ⌈ |F |
2 ⌉ distinct elements. Proof. It suffices to prove that there are no three distinct edges e 1 , e 2 , e 3 ∈ F with σ(e 1 ) = σ(e 2 ) = σ(e 3 ). Let e 1 , e 2 , e 3 ∈ F . As T 1 is a spanning tree, T 1 -{e 1 , e 2 , e 3 } contains three components C 1 , C 2 , C 3 none of which contains v such that e i is incident to a vertex in V (C i ) for i = 1, 2, 3. As T 1 -e i + σ(e i ) is a spanning tree, we obtain that σ(e i ) is incident to a vertex in V (C i ) for i = 1, 2, 3. As V (C 1 ), V (C 2 ) and V (C 3 ) are pairwise disjoint, the statement follows.

◀

Preliminaries on k-safe spanning r-arborescences

Given a rooted digraph D = (V + r, A) and a positive integer k,

a classic (r, k)-kernel is an r-subarborescence X = (V ′ + r, A ′ ) of D such that X is k-safe and |V ′ | = 2k -2.
The XP algorithm of Theorem 4 is based on the following result, which we reformulate here using our terminology.

▶ Lemma 20 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Let k be a positive integer and D = (V +r, A)

a rooted digraph with |V | ≥ 2k -2.
Then D contains two arc-disjoint k-safe spanning rarborescences if and only if D contains an extendable pair of arc-disjoint classic (r, k)-kernels.

Further, the two arc-disjoint k-safe spanning r-arborescences can be constructed from the extendable pair of classic (r, k)-kernels in polynomial time.

Preliminaries on spanning (r, k)-flow branchings

We first need the following result that allows to recognize (r, k)-flow branchings.

▶ Lemma 21 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Given a rooted digraph D = (V + r, A) and a positive integer k, we can decide in polynomial time whether D is an (r, k)-flow branching.

Given a digraph D = (V, A) and two vertices u, v ∈ V , a uv-path flow is a flow z such that z(a) = 1 for all arcs a ∈ A(P ) and z(a) = 0 for every a ∈ A -A(P ) for some uv-path P . Similarly, a cycle flow is a flow z such that z(a) = 1 of all a ∈ A(C) and z(a) = 0 for every a ∈ A -A(C) for some cycle C. We need the following result on flows which is proven in a more general form in [START_REF] Bang | Digraphs: Theory, Algorithms and Applications[END_REF].

▶ Lemma 22. Let X = (V + r, A) be a flow branching and z : A → Z ≥0 be a branching flow in X. Then there is an rv-path flow z v for every v ∈ V and a set of cycle flows {z C : C ∈ C} for some set of cycles C such that z = v∈V z v + C∈C z C .

We now use Lemma 22 to prove an important property of arc-minimal (r, k)-flow branchings. A rooted digraph X = (V + r, A) is called triple-free if it does not contain more than two arcs in the same direction between the same two vertices.

▶ Lemma 23. Let k be a positive integer and X = (V + r, A) an arc-minimal (r, k)-flow branching with |V | ≥ 2k -1. Then X is triple-free.

Proof. Suppose that X contains three arcs a 1 , a 2 , a 3 whose tail is u and whose head is v for some u, v ∈ V + r. Further, let z : A → Z ≥0 be an (r, k)-branching flow. By Lemma 22, we obtain that z = v∈V z v + C∈C z C where z v is an rv-path flow for every v ∈ V and z C is a cycle flow for every C ∈ C for some set of cycles C. Let z ′ = v∈V z v . Observe that z ′ is an (r, k)-branching flow. As all of the z v are path flows, we obtain

z ′ (a 1 ) + z ′ (a 2 ) + z ′ (a 3 ) ≤ |V | < 2(n -k). It follows that we can define a flow z ′′ : A → Z ≥0 such that z ′′ (a 1 ) + z ′′ (a 2 ) = z ′ (a 1 ) + z ′ (a 2 ) + z ′ (a 3 ), z ′′ (a 3 ) = 0, min{z ′′ (a 1 ), z ′′ (a 2 )} ≤ n -k and z ′′ (a) = z ′ (a) for every a ∈ A -{a 1 , a 2 , a 3 }. It is easy to see that z ′′ is an (r, k)-branching flow, so X -a 3 is an (r, k)-flow branching, a contradiction to the minimality of X. ◀ Given a positive integer k and a rooted digraph D = (V + r, A) with |V + r| ≥ 2k, a classic (r, k)-core is an (r, k)-flow branching X = (V ′ + r, A ′ ) that is a subdigraph of D with |V ′ | = 2k -1.
The XP algorithm of Theorem 8 is based on the following result, again reformulated using our terminology.

▶ Lemma 24 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Let k be a positive integer and D = (V +r, A) be a rooted digraph with |V | ≥ 2k -1. Then D contains two arc-disjoint spanning (r, k)-flow branchings if and only if D contains an extendable pair of arc-disjoint classic (r, k)-cores. Further, the two arc-disjoint spanning (r, k)-flow branchings can be constructed in polynomial time from the extendable pair of arc-disjoint classic (r, k)-cores.

Preliminaries on (r, k)-safe spanning trees

We first define an equivalent for extendability in undirected graphs. Given a rooted graph

G = (V + r, E), a pair of subtrees (X 1 , X 2 ) is called completable 2 if there are edge-disjoint spanning trees T 1 , T 2 of G such that E(X i ) ⊆ E(T i ).
The following result that allows to test completabality can be established using matroid theory as mentioned in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF].

▶ Lemma 25 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Given a graph G = (V + r, E) and a pair of subtrees (X 1 , X 2 ), we can decide in polynomial time whether (X 1 , X 2 ) is completable.

Given a positive integer k and a rooted graph

G = (V + r, E) with |V + r| ≥ 2k -1, a classic (r, k)-certificate is an (r, k)-safe subtree X = (V ′ + r, E ′ ) of G with |V ′ | = 2k -2.
The XP algorithm of Theorem 11 is based on the following result, again restated using our terminology.

▶ Lemma 26 (Bang-Jensen, Havet, and Yeo [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF]). Let G = (V + r, E) be a rooted graph and k a positive integer. Then G contains two edge-disjoint (r, k)-safe spanning trees if and only if G contains a completable pair of classic (r, k)-certificates. Further, given a completable pair of classic (r, k)-certificates, we can compute two edge-disjoint (r, k)-safe spanning trees in polynomial time.

Preliminaries on parameterized complexity

We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions used in this article. A parameterized problem is a decision problem whose instances are pairs (x, k) ∈ Σ * × N, where k is called the parameter. A parameterized problem L is fixed-parameter tractable (FPT) if there an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| c . A parameterized problem L is slice-wise polynomial (XP) if there exists an algorithm A and two computable functions f, g such that given an instance I = (x, k), A (called an XP algorithm) correctly decides whether I is a positive instance of L in time bounded by f (k) • |I| g (k) .

A kernelization algorithm, or just kernel, for a parameterized problem L is an algorithm A that, in polynomial time, generates from an instance I = (x, k) of L an equivalent instance

I ′ = (x ′ , k ′ ) of L such that |x ′ | + k ′ ≤ f (k), for some computable function f : N → N. If f (k)
is bounded from above by a polynomial of the parameter k, we say that L admits a polynomial kernel. It is well-known [START_REF] Cygan | Parameterized Algorithms[END_REF] that a parameterized problem is FPT if and only if it admits a (not necessarily polynomial) kernel.

An FPT algorithm for packing k-safe spanning arborescences

This section is concerned with proving Theorem 5. Given a rooted digraph D = (V + r, A) and a positive integer k, we say that a vertex v ∈ V + r is large if |N + D (v)| ≥ 6k -5, and small otherwise. We let L D (resp. S D ) be the set of vertices in V + r which are large (resp. small) in D.

We are now ready to introduce a new notion of (r, k)-kernels for k-safe spanning r-

arborescences. A compact (r, k)-kernel is a subdigraph X = (V ′ +r, A ′ ) of D with |V ′ | ≤ 2k-2 satisfying the following:
X is an r-arborescence, all vertices in (V ′ + r) ∩ L D are sinks of X, and a k-safe r-arborescence Y can be obtained from X by adding a set V * of 2k -2 -|V ′ | new vertices and adding an arc from a vertex in (

V ′ + r) ∩ L D to v for every v ∈ V * .
Observe that Y is not necessarily a subdigraph of D. We now give the following algorithmic result.

▶ Proposition 27. Let D = (V + r, A) be a rooted digraph, k a positive integer, and

X = (V ′ + r, A ′ ) a subdigraph of D with |V ′ | ≤ 2k -2. We can test in time 2 O(k log k) whether X is a compact (r, k)-kernel.
Further, if this is the case, we can find a k-safe r-arborescence Y with the properties mentioned in the definition of compact (r, k)-kernels in the same running time.

Proof. We first verify whether X is an r-arborescence such that all the vertices in (V ′ +r)∩L D are sinks in X. If this is the case, we add a set V * of 2k -2 -|V ′ | new vertices to X. We then test all possibilities to add one arc from (V + r) ∩ L D to v for every v ∈ V * . As |V ′ + r| ≤ 2k and |V * | ≤ 2k, there are at most (2k) 2k = 2 O(k•log k) possibilities to check. For each of these possibilities, we can then check in polynomial time whether the obtained graph is a k-safe arborescence.

◀

The following result shows that compact (r, k)-kernels can be used in a similar way as classic (r, k)-kernels. ▶ Lemma 28. Let k be a positive integer and D = (V + r, A) be a 2-root-connected rooted digraph with |V | ≥ 2k-2. Then D contains two arc-disjoint k-safe spanning r-arborescences if and only if D contains an extendable pair of arc-disjoint compact (r, k)-kernels. Further, given an extendable pair of arc-disjoint compact (r, k)-kernels, we can find a pair of arc-disjoint k-safe spanning r-arborescences in time 2 O(k log k) • n O (1) .

Proof. By Lemma 20, for the first part it suffices to prove that D contains a pair of arcdisjoint extendable compact (r, k)-kernels if and only if D contains a pair of arc-disjoint extendable classic (r, k)-kernels.

First let (X

1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 )) be an extendable pair of arc-disjoint classic (r, k)-kernels. Let X ′ i = (V ′ i + r, A ′ i ) be obtained from X i by deleting B v Xi -v for every v ∈ (V i + r) ∩ L D . By construction, the X ′ i are r-arborescences and all vertices in (V ′ i + r) ∩ L D are sinks in X ′ i . Let Y i be obtained from X ′ i by adding the vertices in V i -V ′ i and adding an arc from a vertex v ∈ (V ′ i + r) ∩ L D to a vertex w ∈ V i -V ′ i whenever w ∈ V (B v Xi ) -v. Observe that Y i is an arborescence with |V (Y i )| = 2k -1. Further, note that |V i + r -V (B v Yi )| = |V i + r -V (B v Xi )| ≥ k for every v ∈ V ′ i and |V (B v Yi )| = 0 for every v ∈ V i -V ′ i . This yields that |V i + r -V (B v Yi )| ≥ |V i + r -V (B v Xi )| ≥ k for every v ∈ V i
and so Y i is a k-safe arborescence. By definition, we obtain that (X ′ 1 , X ′ 2 ) is a pair of arc-disjoint compact (r, k)-kernels. Further, D -A i is a subdigraph of D -A ′ i that is root-connected, so D -A ′ i is root-connected as well. This yields that (X ′ 1 , X ′ 2 ) is extendable. Now let (X 1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 )) be an extendable pair of arc-disjoint compact (r, k)-kernels. By definition, there are k-safe arborescences Y 1 , Y 2 such that Y i is obtained from X i by adding a set V * i of 2k -2 -|V i | new vertices and an arc from a vertex in (

V i + r) ∩ L D to v for every v ∈ V * i . Let (X ′ 1 = (V ′ 1 + r, A ′ 1 ), X ′ 2 = (V ′ 2 + r, A ′ 2
)) be a pair of subdigraphs of D that are vertex-maximal with the following properties: (i) X ′ i is obtained from X i by repeatedly adding another vertex v ∈ V -V i and an arc of A that goes from a vertex in (

V i + r) ∩ L D to v, (ii) d + X ′ i (v) ≤ d + Yi (v) for every v ∈ (V i + r) ∩ L D , (iii) A ′ 1 and A ′ 2 are disjoint, and (iv) (X ′ 1 , X ′ 2 ) is extendable. Note that (X 1 , X 2 ) satisfies conditions (i)-(iv), so (X ′ 1 , X ′ 2 ) is well-defined. Also observe that if condition (ii) is satisfied with equality for every v ∈ (V i + r) ∩ L D , then X ′ i is isomorphic to Y i , so X ′
i is a k-safe arborescence and by definition also a classic (r, k)-kernel. If this is the case for both X ′ 1 and X ′ 2 , we are done by conditions (iii) and (iv). We may therefore suppose by symmetry that there is a vertex

v ∈ (V 1 + r) ∩ L D with d + X ′ 1 (v) < d + Y1 (v). For any a = vz a with z a ∈ N + D (v) -V ′ 1 , let X a 1 = (V ′ 1 + r + z a , A ′ 1 ∪ a)
. By the maximality of X ′ 1 , we obtain that X a 1 violates one of conditions (i)-(iv) for every

a ∈ δ + D (v) with z a ∈ N + D (v) -V ′ 1 .
By construction and the choice of v, X a 1 satisfies conditions (i) and (ii) for every a

∈ δ + D (v) with z a ∈ N + D (v) -V ′ 1 . If X a 1 violates (iii), then z a ∈ V ′ 2 . By (ii), we have |V ′ 2 | ≤ |V 2 ∪ V * 2 | = 2k -2 and so this is the case for at most 2k -2 vertices z a ∈ N + D (v) -V ′ 1 . If X a 1 does not satisfy (iv), then a is critical in D -A ′ 1 . As D is 2-root-connected and X ′
1 is an arborescence by construction, Lemma 16 implies that this is the case for at most

|A ′ 1 | = |V ′ 1 | ≤ |V 1 ∪ V * 1 | = 2k -2 vertices z a ∈ N + D (v) -V ′ 1 . As v ∈ L D and |V ′ 1 | ≤ |V 1 ∪ V * 1 | = 2k -2, we have |N + D (v) -V ′ 1 | ≥ (6k -5) -(2k -2) > (2k -2)+ (2k -2), so there is at least one vertex in z ∈ N + D (v) -V ′
1 and an arc a = vz such that X a 1 does not violate any of conditions (i)-(iv), a contradiction.

Observe that the second part of the proof yields an algorithm for computing a pair of arc-disjoint extendable classic (r, k)-kernels from a pair of arc-disjoint extendable compact (r, k)-kernels. First observe that by the second part of Proposition 27, we can find Y 1 , Y 2 in 2 O(k log k) time. Now, defining X a 2 similarly to X a 1 , every time we try to add an arc a = vz to X ′ i for i = 1 or 2, we test, if (X a i , X ′ 3-i ) satisfies conditions (i)-(iv). Conditions (i)-(iii) can clearly be checked in polynomial time and, by Lemma 17, condition (iv) can also be checked in polynomial time. Never testing an arc that is parallel to one that we have tested already, after at most 4k -4 failed attempts, we manage to add a new vertex to V ′ i . We repeat this procedure |V * i | ≤ 2k -2 times. It follows that a pair of arc-disjoint extendable classic (r, k)-kernels can be computed in time k 2 • n O (1) = n O (1) . By the second part of Lemma 20, we can then find the arc-disjoint k-safe spanning arborescences in D in n O (1) time. Therefore, the overall running time of the algorithm is 2 O(k log k) • n O (1) , as claimed.

◀

We are now ready to proceed to the proof of Theorem 5.

Proof of Theorem 5. We may suppose that there are at most two parallel arcs from u to v for any u, v ∈ V + r. If |V | < 2k -2, the problem can be solved by a brute force algorithm in time 2 O(k 2 ) , by generating all pairs of subdigraphs of D and checking whether any of these pairs satisfies the required conditions. We may hence also suppose that |V | ≥ 2k -2. By Theorem 1 and the remark after, we can first decide in time n O (1) if D is 2-rootconnected. If it is not, the answer is negative by Theorem 1, so we may suppose it is.

We first explain how to test whether a candidate for the extendable pair of arc-disjoint compact (r, k)-kernels is indeed an extendable pair of arc-disjoint compact (r, k)-kernels. After, we show that the number of candidates is bounded. Let

X 1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 ) be two subdigraphs of D with |V 1 |, |V 2 | ≤ 2k -2.
By the first part of Proposition 27, we can check in time 2 O(k•log k) whether both X 1 and X 2 are compact (r, k)-kernels. By Lemma 17, we can therefore decide in time 2 O(k•log k) + n O (1) if (X 1 , X 2 ) is an extendable pair of arc-disjoint compact (r, k)-kernels in D. By Lemma 28, it therefore suffices to prove that there are at most 2 O(k 2 •log k) possible candidates for the extendable pair of arc-disjoint compact (r, k)-kernels, and that these can be generated within this running time.

Let X = (V ′ + r, A ′ ) be a compact (r, k)-kernel in D. Observe that by definition of compact (r, k)-kernels, all vertices in L D ∩ (V ′ + r) are sinks in X. Further, as X can be extended to a k-safe arboresecence on 2k -2 vertices, B X v contains at most k -1 vertices for every v ∈ V ′ . In particular, every vertex in V ′ can be reached from r by a directed path all of whose interior vertices are in S D and whose length is at most k -1. As every vertex in S D has at most 6k -6 out-neighbors, we obtain that the number of vertices in V that can be reached by such a path is at most (6k -6) + (6k -6) 2 + . . . + (6k -6) k-1 ≤ (6k) k . As V ′ contains at most 2k -2 vertices, there are at most (6k) k 2k-2 ≤ (6k) 2k 2 possibilities to choose V ′ . Now suppose that we have chosen V ′ of size 2k -2. As there are at most two arcs in the same direction between any two vertices, there are at most 4 |V ′ +r| 2 ≤ 16k 2 arcs that have their head and tail in V ′ + r. As |A ′ | = 2k -2, there are at most 16k 2 2k-2 ≤ (16k 2 ) 2k possibilities to choose A ′ . It follows that there are at most (6k) 2k 2 • (16k 2 ) 2k possibilities to choose a compact (r, k)-kernel X. As these can be computed by a brute force method, the algorithm can finish after checking less than

f (k) = (6k) 2k 2 •(16k 2 ) 2k 2 = 2 O(k 2 •log k) candidates
for the extendable pair of arc-disjoint compact (r, k)-kernels.

If no extendable pair of arc-disjoint compact (r, k)-kernels exists, by Lemma 28, D does not contain two arc-disjoint k-safe spanning arborescences. On the other hand, once we have found an extendable pair of arc-disjoint compact (r, k)-kernels, we can compute the two arc-disjoint k-safe spanning r-arborescences in polynomial time by the second part of Lemma 28. The overall running time of the obtained algorithm is 2 (1) . ◀

O(k 2 •log k) • n O

An FPT algorithm for packing spanning (r, k)-flow branchings

This section is concerned with proving Theorem 9. Slightly modifying the terminology introduced in Section 3, given a 2-root-connected digraph D = (V + r, A) and a positive integer k, we say that a vertex v is large if |N + D (v)| ≥ 20k 2 + 1, and small otherwise. Again, we let L D (resp. S D ) be the set of vertices in V + r which are large (resp. small) in D.

We are now ready to introduce a new notion of (r, k)-cores for spanning (r, k)-flow branchings

. A compact (r, k)-core is a subdigraph X = (V ′ + r, A ′ ) of D with |V ′ | ≤ 2k -1 satisfying the following:
all vertices in (V ′ + r) ∩ L D are sinks in X and an (r, k)-flow branching Y can be obtained from X by adding a set V * of 2k -1 -|V ′ | new vertices and adding an arc from a vertex in (

V ′ + r) ∩ L D to v for every v ∈ V * .
Observe that Y is not necessarily a subdigraph of D. We now give the following algorithmic result which plays the analogous role of Proposition 27 for flow branchings.

▶ Proposition 29. Let D = (V + r, A) be a rooted digraph, k a positive integer, and X = (V ′ + r, A ′ ) a subdigraph of D with |V ′ | ≤ 2k -1. We can test in time 2 O(k log k) whether X is a compact (r, k)-core. Further, if this is the case, we can find an (r, k)-flow branching Y with the properties mentioned in the definition of compact (r, k)-cores in the same running time.

Proof. We first test if all vertices in (V ′ + r) ∩ L D are sinks in X. We then add a set V * of 2k -1 -|V ′ | new vertices to X. We then test all possibilities to add one arc from

(V ′ + r) ∩ L D to v for every v ∈ V * i . As |V ′ |, |V * | ≤ 2k
, there are at most 2k 2k = 2 O(k•log k) possibilities to check. By Lemma 21, we can check in time polynomial in k whether each of the resulting graphs is an (r, k)-flow branching. ◀

The following result, which is similar to Lemma 28, shows that compact (r, k)-cores can be used in a similar way as classic (r, k)-cores. (1) .

▶ Lemma 30. Let k be a positive integer and D = (V + r, A) be a 2-root-connected rooted digraph with |V | ≥ 2k -1. Then D has two arc-disjoint spanning (r, k)-flow branchings if and only if D contains an extendable pair of arc-disjoint compact (r, k)-cores. Further, given an extendable pair of triple-free arc-disjoint compact (r, k)-cores, we can find a pair of arc-disjoint spanning (r, k)-flow branchings in time

2 O(k•log k) • n O
Proof. By Lemma 24, for the first part it suffices to prove that D contains an extendable pair of arc-disjoint compact (r, k)-cores if and only if D contains an extendable pair of arc-disjoint classic (r, k)-cores.

First let (X

1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 )) be an extendable pair of arc-disjoint classic (r, k)-cores. Let X ′ i = (V ′ i + r, A ′ i )
be obtained from X i by first deleting all arcs in A i whose tail is a large vertex and then restricting to the subdigraph that is root-connected from r. As

A ′ i ⊆ A i , (X ′ 1 , X ′ 2 ) is extendable. It remains to show that X ′ 1 and X ′ 2 are compact (r, k)-cores. By construction, all vertices in (V ′ i + r) ∩ L D are sinks in X ′ i . If X ′ i = (r, ∅)
, let Y i be obtained by attaching 2k -1 outgoing arcs to r. Clearly, Y i is an (r, k)-flow branching and so X ′ i is a compact (r, k)-core. We may hence suppose that X ′ i ̸ = (r, ∅). As X i is an (r, k)-flow branching, there is an (r, k)-branching flow z :

A i → Z ≥0 in X i . Create Y i from X ′ i by attaching z(δ - X ′ i (v)) -1 arcs directed away from v to every vertex v ∈ V ′ i ∩ L D .
Assigning z ′ (a) = 1 for all arcs leaving a large vertex in Y i and z ′ (a) = z(a) for all remaining arcs, we obtain that z ′ is an (r, k)-branching flow in Y i , so Y i is an (r, k)-flow branching. Furthermore, we have

|V (Y i ) -r| = z ′ (δ + Yi (r)) = z(δ + Xi (r)) = |V i | = 2k -1. It follows by definition that X ′ i is a compact (r, k)-core. Now let (X 1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 )
) be an extendable pair of arc-disjoint compact (r, k)-cores. Possibly deleting arcs, we may suppose by Lemma 23 and as |V | ≥ 2k -1 that X 1 and X 2 are triple-free. By definition, there are (r, k

)-flow branchings Y 1 , Y 2 such that Y i is obtained from X i by adding a set V * i of 2k -1 -|V i | new vertices and adding an arc from a vertex in (V i + r) ∩ L D to v for every v ∈ V * i . Let X ′ 1 = (V ′ 1 + r, A ′ 1 ) and X ′ 2 = (V ′ 2 + r, A ′
2 ) be subdigraphs of D that are vertex-maximal with the following properties:

(i) X ′ i is obtained from X i by repeatedly adding another vertex in v ∈ V -V i and an arc of A that goes from a vertex in (V i + r) ∩ L D to v, (ii) d + X ′ i (v) ≤ d + Yi (v) for every v ∈ (V i + r) ∩ L D , (iii) A ′ 1 and A ′ 2 are disjoint, and (iv) (X ′ 1 , X ′ 2 ) is extendable.
Note that (X 1 , X 2 ) satisfies conditions (i)-(iv), so (X ′ 1 , X ′ 2 ) is well-defined. Further, observe that if condition (ii) is satisfied with equality for every v ∈ (

V i + r) ∩ L D , then X ′ i is isomorphic to Y i , so X ′
i is an (r, k)-flow branching, thus by definition also a classic (r, k)-core. If this is the case for both X ′ 1 and X ′ 2 , we are done by conditions (iii) and (iv). We may therefore suppose by symmetry that there is some v

∈ (V 1 + r) ∩ L D with d + X ′ 1 (v) < d + Y1 (v). For any a = vz a with z a ∈ N + D (v) -V ′ 1 , let X a 1 = (V ′ 1 + r + z a , A ′ 1 ∪ a). By the maximality of X ′ 1 , X a 1 violates one of conditions (i)-(iv) for every a ∈ δ + D (v) with z a ∈ N + D (v) -V ′ 1 .
By construction and the choice of v, X a 1 satisfies conditions (i) and (ii)

for every a ∈ δ + D (v) with z a ∈ N + D (v) -V ′ 1 . If X a 1 violates condition (iii), then z a ∈ V ′ 2 . As |V ′ 2 | ≤ |V (Y 2 )| = 2k, this is the case for at most 2k vertices in N + D (v) -V ′ 1 . If X a 1 does not satisfy (iv), then a is critical in D -A ′ 1 . As X 1 is triple-free, |V ′ 1 | ≤ 2k and by construction, we obtain that |A ′ 1 | ≤ 4 |V ′ 1 | 2 ≤ 16k 2 . Now Lemma 16 implies that this is the case for at most 16k 2 vertices in N + D (v) -V ′ 1 . As v ∈ L D and |V ′ 1 | ≤ |V 1 ∪ V * 1 | = 2k -1, we have |N + D (v) -V ′ 1 | ≥ (20k 2 + 1) -(2k -1) > 2k + 16k 2 , so there is at least one vertex z ∈ N + D (v) -V ′
1 and an arc a = vz such that X a 1 does not violate any of conditions (i)-(iv), a contradiction.

Observe that the second part of the proof yields an algorithm for computing a pair of arc-disjoint extendable classic (r, k)-cores from a pair of triple-free arc-disjoint extendable compact (r, k)-cores. First observe that by the second part of Proposition 29, we can find Y 1 , Y 2 in time 2 O(k log k) . Now, defining X a 2 similarly to X a 1 , every time we try to add an arc a = vz to X ′ i for i = 1 or 2, we test if (X a i , X ′ 3-i ) satisfies conditions (i)-(iv). Conditions (i)-(iii) can clearly be checked in polynomial time and, by Lemma 17, condition (iv) can also be checked in polynomial time. Never checking an arc a which is parallel to an arc we have already checked, after at most 20k 2 failed attempts, we manage to add a new vertex to V ′ i . We repeat this procedure at most |V * i | ≤ 2k times. It follows that a pair of arc-disjoint extendable classic (r, k)-cores can be computed in time 40k 3 • n O (1) = n O (1) . By the second part of Lemma 24, we can then find the arc-disjoint spanning (r, k)-flow branchings in D in polynomial time. The overall running time of the algorithm is 2 O(k•log k) • n O (1) , as claimed.

◀

We are now ready to proceed to the proof of Theorem 9. = O(k 2 ) pairs of vertices, the total number of choices for these distributions is γ µ = 2 O(k 2 •log k) . The problem can therefore be solved by a brute force algorithm in time 2 O(k 2 •log k) , by generating all 2 O(k 2 •log k) pairs of candidate subdigraphs of D and checking whether any of these pairs satisfies the required conditions. We may hence suppose that |V | ≥ 2k -1.

Proof of

By Lemma 23, we may also suppose that there are at most four parallel arcs between any two vertices in D. By Theorem 1 and the remark after, we can first decide in polynomial time if D is 2-root-connected. If it is not, the answer is negative by Theorem 1 and the fact that every (r, k)-flow branching contains an r-arborescence, so we may suppose it is.

We first explain how to test whether a candidate for the extendable pair of arc-disjoint compact (r, k)-cores is indeed an extendable pair of arc-disjoint compact (r, k)-cores. After, we show that the number of candidates is bounded. Let

X 1 = (V 1 + r, A 1 ), X 2 = (V 2 + r, A 2 ) be two subdigraphs of D with |V 1 |, |V 2 | ≤ 2k -1.
By the first part of Proposition 29, we can check in time 2 O(k•log k) whether both X 1 and X 2 are compact (r, k)-cores. By Lemma 17, we can therefore decide in time 2 O(k•log k) + n O (1) if (X 1 , X 2 ) is an extendable pair of arc-disjoint compact (r, k)-cores in D. By Lemma 30, it therefore suffices to prove that there are at most 2 O(k 2 •log k) possible candidates for the extendable pair of arc-disjoint compact (r, k)-cores, and that these can be generated within the same running time.

Let X = (V ′ + r, A ′ ) be a compact (r, k)-core in D. Observe that every vertex in V ′ can be reached from r by a directed path all of whose internal vertices are in S D and whose length is at most 2k -1. As every vertex in S D has at most 20k 2 out-neighbors, we obtain that the number of vertices in V that can be reached by such a path is at most 20k 2 + (20k 2 ) 2 + . . . + (20k 2 ) 2k-1 ≤ (20k 2 ) 2k . As V ′ contains at most 2k -1 vertices, there are at most (20k 2 ) 2k (2k-1) ≤ (20k 2 ) 4k 2 possibilities to choose V ′ . Now suppose that we have chosen V ′ of size at most 2k -1. As there are at most four arcs in the same direction between any two vertices, there are at most 8 |V ′ | 2 ≤ 32k 2 arcs that have their head and tail in V ′ + r. As all arcs of A ′ have both ends in V ′ + r, there are at most 2 32k 2 possibilities to choose A ′ . It follows that there are at most (20k 2 ) 4k 2 • 2 32k 2 possibilities to choose a compact (r, k)-core X. As these can be computed by a brute force method, the algorithm can finish after checking less than

f (k) = (20k 2 ) 4k 2 •2 32k 2 2 = 2 O(k 2 •log k) candidates for the extendable pair of compact (r, k)-cores.
If no such extendable pair of arc-disjoint compact (r, k)-cores exists, by Lemma 30, D does not contain two arc-disjoint spanning (r, k)-flow branchings. On the other hand, if we find an extendable pair of arc-disjoint compact extendable (r, k)-cores, we also find such a pair (X 1 , X 2 ) where X 1 and X 2 are arc-minimal, so by Lemma 23 triple-free. By the second part of Lemma 30, we can compute the two arc-disjoint spanning (r, k)-flow branchings in polynomial time. The overall running time of the obtained algorithm is 2 O(k 2 •log k) • n O (1) . ◀

5

An FPT algorithm for packing (r, k)-safe spanning trees

This section is concerned with proving Theorem 12. Again, slightly modifying the terminology introduced in Section 3 and reused in Section 4, given a rooted graph G = (V + r, E) and a positive integer k, we say that a vertex v ∈ V + r is large if |N G (v)| ≥ 8k -7, and small otherwise. And again, we let L G (resp. (S G )) be the set of vertices in V + r which are large (resp. small) in G.

We are now ready to introduce a new notion of certificates for (r, k)-safe spanning trees.

A compact (r, k)-certificate is a subgraph X = (V ′ + r, E ′ ) of G with |V ′ | ≤ 2k -2 satisfying the following:
X is a tree, all vertices in (V ′ + r) ∩ L G are terminals of X, and an (r, k)-safe tree Y can be obtained from X by adding a set V * of 2k -2 -|V ′ | new vertices and adding an edge from a vertex in (

V ′ + r) ∩ L G to v for every v ∈ V * .
Observe that Y is not necessarily a subgraph of G. We now give the following algorithmic result which plays the analogous role of Proposition 27 and Proposition 29 for k-safe spanning trees.

▶ Proposition 31. Let G = (V + r, E) be a rooted graph, k a positive integer, and

X = (V ′ + r, E ′ ) a subgraph of G with |V ′ | ≤ 2k -2. We can test in time 2 O(k log k) whether X is a compact (r, k)-certificate.
Further, if this is the case, we can construct an (r, k)-safe spanning tree Y with the properties mentioned in the definition of compact (r, k)-certificate in the same running time.

Proof. We first check whether X is a tree such that all the vertices in (V ′ + r) ∩ L G are terminals of X. If this is the case, we add a set V * of 2k -2 -|V ′ | new vertices to X. We then test all possibilities to add one edge from (V ′ + r) ∩ L G to v for every v ∈ V * . As |V ′ + r| ≤ 2k and |V * | ≤ 2k, there are at most (2k) (2k) = 2 O(k•log k) possibilities to check. For each of them, we can check in time polynomial in k if the obtained graph is an (r, k)-safe spanning tree. ◀

The following result, which is similar to Lemma 28 and Lemma 30, shows that compact certificates can be used in a similar way as classic certificates.

▶ Lemma 32. Let k be a positive integer and G = (V + r, E) be a rooted graph with |V | ≥ 2k -2. Then G has two edge-disjoint (r, k)-safe spanning trees if and only if G contains a completable pair of compact (r, k)-certificates. Further, given a completable pair of compact (r, k)-certificates, we can find a pair of edge-disjoint (r, k)-safe spanning trees in time 2 O(k•log k) • n O (1) . Proof. By Lemma 26, for the first part it suffices to prove that G contains a completable pair of compact (r, k)-certificates if and only if G contains a completable pair of classic (r, k)-certificates.

First let (X

1 = (V 1 + r, E 1 ), X 2 = (V 2 + r, E 2 )) be a completable pair of classic (r, k)- certificates. Let X ′ i = (V ′ i + r, E ′ i ) be obtained from X i by deleting C v Xi for every v ∈ (V i + r) ∩ L G .
By construction, the X ′ i are trees and all vertices in (V ′ i + r) ∩ L G are terminals in X ′ i . Let Y i be obtained from X ′ i by adding the vertices in V i -V ′ i and adding an edge from

As v ∈ L G and |V ′ 1 | ≤ |V 1 ∪ V * 1 | = 2k -2, we have |N G (v) -V ′ 1 | ≥ (8k -7) -(2k -2) > 6k -6.
It now follows from Claim 33 and Claim 34 that there is at least one vertex in z ∈ N G (v) -V ′ 1 and an edge e = vz such that X e 1 does not violate any of conditions (i)-(iii), a contradiction. Observe that the second part of the proof yields an algorithm for computing a completable pair of classic (r, k)-certificates from a pair of completable compact (r, k)-certificates. First observe that by the second part of Proposition 29, we can find Y 1 , Y 2 in time 2 O(k log k) . Now, defining X a 2 similarly to X a 1 , every time we try to add an edge e to X ′ i , for i = 1 or 2, we test if (X e i , X ′ 3-i ) satisfies conditions (i)-(iii). Conditions (i)-(ii) can clearly be checked in polynomial time and, by Lemma 25, condition (iii) can also be checked in polynomial time. Never checking an edge that is parallel to one we have already checked, after at most 6k -6 failed attempts, we manage to add a new vertex to V ′ i . We repeat this procedure (1) . By the second part of Lemma 26, we can then find two edge-disjoint (r, k)-safe spanning trees in G in polynomial time. The overall running time of the algorithm is 2 O(k log k) • n O (1) , as claimed. ◀

|V * i | ≤ 2k -2 times. It follows that a completable pair of classic (r, k)-certificates can be computed in time k 2 • n O(1) = n O
We are now ready to proceed to the proof of Theorem 12.

Proof of Theorem 12. We may suppose that there are at most two parallel edges from u to v for any u, v ∈ V + r. If |V | < 2k -2, the problem can be solved by a brute force algorithm in time 2 O(k 2 ) , by generating all pairs of subgraphs of G and checking whether any of these pairs satisfies the required conditions. We may hence also suppose that |V | ≥ 2k -2. We first explain how to test whether a candidate for the completable pair of compact (r, k)-certificates is indeed a completable pair of compact (r, k)-certificates. After, we show that the number of candidates is bounded.

Let X 1 = (V 1 + r, E 1 ), X 2 = (V 2 + r, E 2 ) be two subgraphs of G. By the first part of Proposition 31, we can check in time 2 O(k•log k) whether both X 1 and X 2 are compact (r, k)-certificates. By Lemma 25, we can therefore decide in time 2 O(k•log k) + n O (1) if (X 1 , X 2 ) is a completable pair of compact (r, k)-certificates in G. By Lemma 32, it therefore suffices to prove that there are at most 2 O(k 2 •log k) possible candidates for the completable pair of compact (r, k)-certificates, and that they can be generated within the same running time.

Let X = (V ′ + r, E ′ ) be a compact (r, k)-certificate in G. Observe that every vertex in V ′ can be reached from r by a path all of whose interior vertices are in S G and whose length is at most k -1. As every vertex in S G has at most 8k -8 neighbors, we obtain that the number of vertices in V that can be reached by such a path is at most (8k -8) + (8k -8) 2 + . . . + (8k -8) k-1 ≤ (8k) k . As V ′ contains at most 2k -2 vertices, there are at most

(8k) k 2k-2 ≤ (8k) 2k 2 possibilities to choose V ′ .
Now suppose that we have chosen V ′ of size 2k -2. Observe that there are at most 2 |V ′ +r| 2 ≤ 8k 2 edges that have both ends in V ′ + r. As |E ′ | = 2k -2, there are at most 8k 2 2k-2 ≤ (8k 2 ) 2k possibilities to choose A ′ . It follows that there are at most (8k) 2k 2 • (8k 2 ) 2k possibilities to choose a compact (r, k)-certificate X. As these can be computed by a brute force method, the algorithm can finish after checking less than f

(k) = (8k) 2k 2 •(8k 2 ) 2k 2 = 2 O(k 2 •log k) candidates for the pair of compact (r, k)-certificates.
If no completable pair of compact (r, k)-certificates exists, by Lemma 26, G does not contain two edge-disjoint (r, k)-safe spanning trees. On the other hand, once we have found a pair of completable compact (r, k)-certificates, we can compute in polynomial time the two edge-disjoint (r, k)-safe spanning trees by the second part of Lemma 26. The overall running time of the obtained algorithm is 2 O(k 2 •log k) • n O (1) . ◀

A hardness result for packing (r, k)-safe spanning trees

In this section we prove Theorem 13. It is well-known that the 3-Sat problem is NPcomplete. Further, we will need the following lemma derived from the ETH using the so-called Sparsification Lemma [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF].

▶ Lemma 35 (Impagliazzo et al. [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF]). Assuming the ETH, there is an ε > 0 such that there is no algorithm for solving a 3-Sat formula with ℓ variables and m clauses in time 1) .

2 εm • (ℓ + m) O(
The proof of Theorem 13 given below is strongly inspired from the reduction given in [3, Theorem 5.2], but we provide it here entirely for the sake of completeness.

Proof of Theorem 13. Observe that, given a rooted graph G = (V + r, E) and two positive integers p and k, G contains an (r, k)-safe spanning tree if and only if the graph that is obtained from G by replacing each of its edges by p parallel copies of itself contains p edgedisjoint (r, k)-safe spanning trees. Hence, it suffices to prove the statement for p = 1. Let ϕ be an instance of 3-Sat, with variables x 1 , x 2 , . . . , x ℓ and clauses C 1 , C 2 , . . . , C m . Adding a variable that is not contained in any clause if necessary, we can assume that ℓ is even. We construct a simple rooted graph G = (V + r, E) as follows; see Figure 1 for an illustration. For i = 1, . . . , ℓ, let V i be an independent set containing two vertices v i and vi , and let r and t be two extra vertices. Add all possible edges between r and V 1 , between V i and V i+1 for i = 1, . . . , ℓ -1, and between V ℓ and t. Next, add m vertices c 1 , . . . , c m and link c i to v j (resp. vj ) with a path containing ℓ/2 interior vertices if x i (resp. xi ) is a literal of C i . Finally, let k := 1 + ℓ + 3ℓm/2 + m and add to G an independent set Q on q vertices all linked to t, where q > k -ℓ -1 will be specified later. Notice that we have n We now prove that ϕ is satisfiable if and only if G admits an (r, k)-safe spanning tree. First assume that G contains an (r, k)-safe spanning tree T . Observe that, by construction and the definition of (r, k)-safe spanning trees, T -r has exactly two components whose vertex sets we denote by T 1 and T 2 . We may assume that T 1 contains t. Then G[T 1 ] contains a path P from V 1 to t and T 1 contains Q. As a shortest path from V 1 to t contains ℓ + 1 vertices, we have |T 1 | ≥ q + ℓ + 1 and n -|T 1 | ≤ k. As T is (r, k)-safe, we obtain that |T 1 | = q + ℓ + 1 and T 1 consists exactly of the vertex set of the path P , which contains exactly ℓ + 1 vertices, and the whole set Q. In particular, P intersects each V i in exactly one vertex. Now for i = 1, . . . , ℓ , we set x i to true if P contains vi and to false if P contains v i . For each clause C j , there must be a path from the corresponding vertex c j to V 1 in T 2 . Then one of the vertices corresponding to a literal of C j must not be contained in P and so, this literal is set to true and C j is satisfied by it. It follows that the constructed assignment satisfies ϕ.

= |V | = q + k + ℓ + 1. V 1 V 2 V 3 V 4 V ℓ-1 V ℓ r t Q c 4 c m ℓ / 2 v e r t ic e s v 1 v1 v 2 v2 v 3 v3 v 4 v4 vℓ-1 vℓ v ℓ-1 v ℓ c 1 c 2 c 3
Conversely, assume that ϕ admits a truth assignment. Let P be the path defined so that, for every i = 1, . . . , ℓ, it contains v i if x i is set to false and vi if x i is set to true. Further, let T 1 = V (P ) ∪ t ∪ Q. As ϕ is satisfied, for every 1 ≤ j ≤ m, there exists a path from c j to

V 1 ∪ • • • ∪ V ℓ in G -(T 1 ∪ r).
It follows that G -(T 1 ∪ r) is connected and we select a spanning tree of it. The union of this spanning tree with G[T 1 ], r, and the edges incident to r is a spanning tree of G. In order to see that this spanning tree is (r, k)-safe, it suffices to observe that, as q > k -ℓ -1, we have |T 1 | = q + ℓ + 1 > k and |V -T 1 | = q + k + 1 + ℓ -(q + ℓ + 1) = k.

If we fix q = k, then the size of G is bounded by a polynomial in ℓ and m. Thus, the above reduction implies that, as 3-Sat is NP-complete, given a rooted graph G and an integer k, deciding whether G admits an (r, k)-safe spanning tree is NP-complete.

Let now ε be a positive constant and assume that k is an integer function satisfying (log(n)) 2+ε ≤ k(n) ≤ n 2 for every n > 0. Furthermore, suppose that there exists a constant C * such that for every integer c ≥ C * there exists an n such that k(n) = c. Finally, for the sake of a contradiction assume that there exists a polynomial-time algorithm A, running in time O(n c0 ) for some c 0 > 0, for deciding if a given rooted graph G = (V + r, E) on n vertices contains an (r, k(n))-safe spanning tree. Then let ϕ be a 3-Sat formula with ℓ variables and m clauses. We may assume that ℓ and m are large enough so that 1 + ℓ + 3ℓm/2 + m ≥ C * . Adding trivial clauses if necessary, we may also assume that ℓ ≤ m. By assumption, there exists n such that k(n) = 1 + ℓ + 3ℓm/2 + m. So, in the above reduction, we choose q to be n -(k(n) + ℓ + 1), in order to have n = q + k(n) + ℓ + 1. Then, using algorithm A, one could decide if ϕ is satisfiable in time

O(n c0 ) = O(2 c0•log n ) = O(2 c0•k(n) 1/(2+ε)
), where we have used the assumption that k(n) ≥ (log(n)) 2+ε . Moreover, in the previous construction, we have k(n) = 1 + ℓ + 3ℓm/2 + m ≤ 3m + 3m 2 /2 ≤ 3m 2 . So we could decide whether ϕ is satisfiable in time O(2 c0•(3m 2 ) 1/(2+ε) ) = O(2 c ′ 0 •m ε ′ ) with ε ′ = 2/(2 + ε) < 1, a contradiction to Lemma 35 assuming the ETH. ◀

Conclusion

We considered three problems on finding certain disjoint substructures in graphs and digraphs. While in our proofs we restrict to finding two of these substructures for the sake of simplicity, our results can be generalized to allow for finding an arbitrary number of them using the same proof techniques. More concretely, the following results can be established using the techniques of this article. As in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], we omit the proofs of these generalized statements. Further, if they exist, the p edge-disjoint (r, k)-safe spanning trees can be computed within the same running time.

It is natural to ask whether the dependency on k of our FPT algorithms can be improved.

There is still a significant gap between the lower bounds in Corollaries 3,7 and 14, which are 2 O(k 1-ε ) or 2 O(k 1/2-ε ) , and the function 2 O(k 2 •log k) in our FPT algorithms.

We did not focus on optimizing the polynomial factors in n of our algorithms, and we leave it for further research. Further, we leave as an open question whether any of the considered problems admit a polynomial kernel parameterized by k. Finally, it would be interesting to find a theorem on packing k-safe mixed arborescences in mixed graphs, hence generalizing both Theorem 36 and Theorem 38.

Theorem 9 .

 9 First consider the case where |V | < 2k -1. Observe that any arcminimal spanning (r, k)-flow branching has at most |V | parallel arcs between any two vertices. It follows that, for any two vertices u, v, at most γ := 4k 2 different distributions of the arcs between u and v among the two candidates for the spanning (r, k)-flow branchings have to be considered, including taking none of these arcs. Since there are µ := |V | 2

Figure 1

 1 Figure 1 The rooted graph G in the proof of Theorem 13 with C1 = x1 ∨ x2 ∨ x4.

▶ Theorem 36 .▶

 36 Given a rooted digraph D = (V + r, A) and an integer p ≥ 2, deciding whether D contains p arc-disjoint k-safe spanning r-arborescences is FPT with parameter k. More precisely, the problem can be solved in time2 O(p•k 2 •log k) • n c, where c is a constant depending on p. Further, if they exist, the p arc-disjoint k-safe spanning r-arborescences can be computed within the same running time. Theorem 37. Given a rooted digraph D = (V + r, A) and an integer p ≥ 2, deciding whether D contains p arc-disjoint (r, k)-flow branchings is FPT with parameter k. More precisely, the problem can be solved in time2 O(p•k 2 •log k) • n c, where c is a constant depending on p. Further, if they exist, the p arc-disjoint (r, k)-flow branchings can be computed within the same running time.▶ Theorem 38. Given a rooted graph G = (V + r, E) and an integer p ≥ 2, deciding whether G contains p arc-disjoint (r, k)-safe spanning trees is FPT with parameter k. More precisely, the problem can be solved in time 2 O(p•k 2 •log k) • n c , where c is a constant depending on p.

This notion should not be confused with the standard term 'kernel' from parameterized complexity, as defined in Subsection

2.5.

Note that we require a completable pair of trees to be edge-disjoint. This is in contrast with the fact that, in Subsection 2.2 and Subsection 2.3, we do not require the elements in an extendable pair to be arc-disjoint. We adopt this asymmetric choice for technical reasons arising from the proofs.

FUNCAP Pronem 4543945/2016 and CAPES/STIC-AmSud 88881.197438/2018-01. Ignasi Sau: DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), ELIT (ANR-20-CE48-0008-01), and French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).

)) be a completable pair of compact (r, k)certificates. By definition, there are (r, k)-safe trees Y 1 , Y 2 such that Y i is obtained from X i by adding a set V * i of 2k -2 -|V i | new vertices and an edge from a vertex in (

)) be a pair of subgraphs of G that are vertex-maximal with the following properties:

i is an (r, k)-safe tree and by definition also a classic (r, k)-certificate. If this is the case for both X ′ 1 and X ′ 2 , we are done by condition (iii). We may therefore suppose by symmetry that there is a vertex

∪e). By the maximality of X ′ 1 , we obtain that X e 1 violates one of conditions (i)-(iii) for every

By construction and the choice of v, X e 1 satisfies conditions (i) and (ii) for every e = vz e ∈ δ G (v) with

Proof. Suppose otherwise. By Lemma 18, there is an edge

). As T ′ 1 and T 2 are edge-disjoint, we obtain that (X e 1 , X ′ 2 ) is completable, a contradiction. ◀ ▶ Claim 34. There are at most 6k - ) and E(X ′ 2 ) ⊆ E(T ′ 2 ), we obtain that (X e 1 , X ′ 2 ) is completable, a contradiction. ◀


Marc Rabaud

Frederic Moisy

Kelvin Or Mach Angle?

Frédéric Moisy

Ship wakes

Keywords: Kelvin or Mach Angle? PACS numbers: 47.35.Bb, 42.15.Dp, 92.10.Hm

come

The V-shaped wakes behind objects moving on calm water is a fascinating wave phenomenon with important practical implications for the drag force on ships [START_REF] Garrett | The symmetry of sailing[END_REF] and for bank erosion along navigable waterways [START_REF] Osborne | [END_REF]. The wake pattern was first explained by Lord Kelvin, who by recognizing the dependence of the phase speed c ϕ of surface gravity waves on their wavelength (dispersion) predicted that the wake half-angle α K = arcsin(1/3) ≈ 19.47 o should be independent of the object's velocity U [START_REF] Lighthill | Waves in fluids[END_REF][START_REF] Darrigol | Worlds of Flow: A History of Hydrodynamics from the Bernoullis to Prandtl[END_REF]. However, Kelvin's analysis is called into question by numerous observations of wakes significantly narrower than he predicted [START_REF] Reed | [END_REF][6][7][8][START_REF] Mei | Proc. R. Soc. Lond. A[END_REF][START_REF] Munk | Proc. R. Soc. Lond. A[END_REF], which have been rationalized by invoking finite-depth effects [6], nonlinear resonances or solitons [7,8], unsteady forcing [START_REF] Mei | Proc. R. Soc. Lond. A[END_REF], and visualisation biases [START_REF] Munk | Proc. R. Soc. Lond. A[END_REF]. Analysing a set of airborne images taken from the Google Earth database [START_REF]Google Earth[END_REF], we show here that ship wakes undergo a transition from the classical Kelvin regime at low speeds to a previously unnoticed highspeed regime α ∼ U -1 that resembles the Mach cone prediction α = arcsin(c ϕ /U ) for supersonic airplanes [START_REF] Lighthill | Waves in fluids[END_REF].

Since the pioneering work of Froude and Kelvin, waves generated by ships have received considerable interest in naval hydrodynamics, because an important part of the resistance to motion of a ship is due to the energy radiated by these waves [START_REF] Garrett | The symmetry of sailing[END_REF][START_REF] Darrigol | Worlds of Flow: A History of Hydrodynamics from the Bernoullis to Prandtl[END_REF][START_REF] Raphaël | [END_REF]. A key parameter governing the wave drag is the hull Froude number, F r = U/ √ gL, where L is the hull length and g the gravitational acceleration. This non-dimensional number can be conveniently rewritten as F r = λ g /2πL, where λ g = 2πU 2 /g is the wavelength of the gravity wave propagating in the ship direction with a phase speed equal to U . We propose here a model that takes into account the finite length of the ship, and which successfully predicts the Kelvin-Mach transition at a critical Froude number F r = U/ √ gL 0.5.

We have systematically measured the angle of ship wakes from a series of airborne images taken from the Google Earth database [START_REF]Google Earth[END_REF] (data available as Supplemental Material [13]). These images, which are corrected for parallax distortion, are chosen close to active harbors, where a high resolution of order of 1 m is available. Only images where the ship wake forms straight arms, ensuring a constant ship direction, are selected. For each image, the ship length L is measured and its velocity U is deduced from the wavelength λ measured in the wake arms [see Eq. ( 1) below and Ref. [14]], from which the Froude number is determined. From these images, wake angles close to the Kelvin prediction α K = 19.47 o are system- For each image, the wake angle α is defined from the slope of the line going through the brightest points resulting from sun glitter or whitecaps (yellow dotted line), which trace the maximum amplitude of the wake. Using the highest available magnification, the ship length L can be accurately determined with the calibration provided by Google Earth.

atically found at low F r, i.e. for L λ g (Fig. 1a). In this case, a double wedge pattern, generated by the bow and the stern, can be observed. At larger F r, λ g reaches the ship length L, resulting in interacting bow and stern waves. At this point it is known that the trim of the boat is affected and the wave drag strongly increases: this is the so-called hull limit velocity [START_REF] Garrett | The symmetry of sailing[END_REF][START_REF] Darrigol | Worlds of Flow: A History of Hydrodynamics from the Bernoullis to Prandtl[END_REF] -even if powerful speed boats or sailing boats nowadays overcome this limit. At even larger F r (L λ g ), the hull partly rises out of the water, entering in the so-called planing regime [START_REF] Garrett | The symmetry of sailing[END_REF]. It is in this large-F r regime that we find examples of narrow wakes, with angles of 10 o or less, as illustrated in Fig. 1b.

The wake angles measured from the airborne images are plotted as a function of the Froude number in Fig. 2. In spite of a significant scatter, which can be mainly ascribed to the uncertainty in measuring the wavelength λ, the data clearly shows a plateau at α 18.6 o ± 1.8 o up to F r 0.5 ± 0.1, in good agreement with the Kelvin theory. For larger F r, this Kelvin regime is followed by a decrease of the angle down to values of order of 7 o for the fastest boats of our dataset [13]. Interestingly, like in the Mach cone problem, this decrease approximately follows a law α ∼ 1/F r.

In order to explain the transition in the wake angle, the starting assumption is to relate each wavenumber k emitted by the ship hull to a specific angle α(k). This k-dependent angle can be inferred from the linear dispersion relation for gravity waves in deep water [START_REF] Lighthill | Waves in fluids[END_REF], ω 2 = gk, from which it follows that the group velocity c g = dω/dk of each wavenumber k is half its phase speed c ϕ = ω/k = g/k. Since the wake is stationary in the reference frame of the ship, the phase speed of each k must be given by the ship velocity projected in the di- rection of the wave propagation,

U cos θ(k) = c ϕ (k) = g/k.
(

Accordingly, only wavenumbers k ≥ k g = 2π/λ g = g/U 2 can form a stationary pattern. Following the geometrical construction of Ref. [15] (see Fig. 3), we consider a wave of given wavenumber k emitted at time -t in the direction θ(k) given by Eq. ( 1) when the boat was in M, with MO= U t. Since its group velocity is half its phase speed, the distance MH= c g t traveled by this wave is half the distance MI= c ϕ t. It follows that the wedge angle formed by this particular wavenumber k is

α(k) = tan -1 k/k g -1 2k/k g -1 , (2)
which is plotted in Fig. 4. This angle vanishes at the lower bound k = k g allowed by the ship velocity (corresponding to the transverse wave λ g shown in Fig. 3) and at k → ∞, and reaches the maximum

α K = tan -1 (1/ √ 8) 19.47 o at k = 3k g /2.
No energy can be found outside this wedge of angle α K , so if all wavenumbers are excited (flat disturbance spectrum), the classical Kelvin angle α K is found.

An important point is that the departure from the Kelvin angle α K in Fig. 2 is observed at large velocities, for which both viscosity and surface tension effects can be neglected, so a model for the Kelvin-Mach transition must rely only on gravity waves. The key assumption here is that a ship of size L cannot excite waves of size much larger than L, suggesting to model the finite size of the ship by a disturbance spectrum E d (k) truncated at low wavenumber. The simplest choice is a Heaviside step spectrum, E d (k) ∝ H(k -k L ), with a cutoff wavenumber k L = 2π/L. The resulting wake angle is therefore simply given by the maximum of (2) taken over the range of excited wavenumbers,

[k L , ∞[. When k L ≤ 3k g /2, i.e. for M O k I α θ λ Ut c g t c ϕ t λ g H FIG.
3. Wake angle α(k) of a given Fourier component k. The wave of wavenumber k emitted in the direction θ(k) at time -t when the ship was in M reaches at time 0 the point H at the middle of MI because the group velocity is half the phase speed. The wave crests illustrate the transverse waves λg at α = 0 and the divergent waves λ at α = 0 (with λ = 2λg/3 for the classical Kelvin wake).

F r ≤ F r c = 3/4π 0.49, the maximum of α(k) belongs to the excited range and the classical Kelvin angle is found; on the other hand, when k L > 3k g /2, a lower angle given by Eq. ( 2) at k = k L is selected, resulting in a piecewise wake angle

α = tan -1 (1/ √ 8) 19.47 o , F r ≤ F r c (3a) α = tan -1 √ 2πF r 2 -1 4πF r 2 -1 , F r ≥ F r c , (3b)
This model provides a good comparison with the angles measured from the wake images, as shown in Fig. 2. Values slightly below Eq. (3b) probably originate from a systematic underestimation of the Froude number for the fastest boats: at such large F r boats are in the planing regime, resulting in a waterline length smaller than their actual length L seen from above. It is worth noting that the details of the high wave-number part of the disturbance spectrum, which must be affected by complex flow phenomena around the ship hull (flow separation, capillary effects, splashing), is not critical in this model. All disturbance spectrum with no energy below k L = 2π/L would produce essentially the same transition at F r = F r c , and would differ only in the limit of low Froude number. Interestingly, for large Froude numbers, Eq. (3b) simply reduces to

α ≈ 1 2 √ 2πF r , (4)
which is analogous to the Mach cone angle for (nondispersive) acoustic waves, α c g /U , where the constant group velocity c g = 1 2 g/k L selected by the ship length L plays here the role of the sound velocity. We can therefore call the regimes described by Eq. ( 3a) and (3b) the 'Kelvin' and 'Mach' regimes, respectively. The asymptotic law (4) matches the model (3b) to within 1% for F r > 1, and describes equally well the data in Fig. 2. Note that Eq. ( 4) is similar to what would be obtained in the case of a (non-dispersive) shallow water wake [6], namely α ≈ 1/F r H , where F r H = U/ √ gH is now the depth Froude number based on the sea depth H. But despite this resemblance, Eq. ( 4) remains essentially a dispersive result, as confirmed by the the characteristic feathered wave pattern seen in Fig. 1(b). Indeed, a non-dispersive shallow-water wake would be made of two straight crests comparable to a supersonic shock wave, which we have never observed in our set of images. The finite size rather than finite depth origin of the narrow wakes analysed here is further confirmed by the depth Froude number determined for each location [START_REF]Local depths are available from the marine charts pro[END_REF], which does not correlate to the measured angles [13].

In order to confirm the influence of the finite size of the disturbance on the wake angle, we have performed a pseudo-spectral simulation of the wave pattern generated by a disturbance moving at constant velocity with infinite water depth. The simulation is carried out in a square domain r = (x, y) ∈ [-D/2, D/2] 2 , discretized on a grid of size N = 2048. At each time step δt = δx/U , where δx = D/N is the mesh unit, a disturbance δζ located at r s = (D/4, 0) is added to the surface deformation ζ(r, t) initially set to 0. The disturbance is a localized deformation of the interface δζ = w d (r -r s )δt, mimicking the effect of a pressure disturbance applied during δt. Since the simulation is performed in the reference frame of the disturbance, the actual deformation field ζ(r, t) is translated by one mesh unit δx, Fourier-transformed, and each wave component is phase-shifted according to the dis-

persion relation, ζ(k, t + δt) = ζ(k, t) exp[iω(k) δt].
The resulting spectrum is then Fourier-transformed back in the physical domain, yielding ζ(r, t + δt), and an absorbing boundary condition is applied in order to avoid the wake pattern re-entering the periodic domain. The procedure is repeated until a stationary pattern is achieved, i.e. when the transient waves generated at t = 0 leave the domain. Note that the resulting deformation ζ(r) is complex, with the real part being the actual surface deformation (related to the potential energy), and the imaginary part coding for the phase of the wave (related to the kinetic energy, which is in phase quadrature with the potential energy for each Fourier component).

The deformation disturbance w d (r) is the response of the free surface to an applied moving pressure distribution P (r -U te x ), given by -U ∂P/∂x in the frame of the disturbance. Introducing a highly simplified hull disturbance in the form of an axisymmetric Gaussian pressure distribution P (r), the resulting disturbance deformation has a dipolar shape, which we write as w d (r) ∝ -∂[exp(-2π 2 (r/L) 2 )]/∂x, with a bump before and a hole behind it. The corresponding disturbance spectrum is

E d (k) = | ŵd (k)| 2 ∝ k 2 x | P (k)| 2 ∝ k 2 x exp[-(kL) 2 /4π 2 ],
which is maximum at k x = 2π/L. This model spectrum (plotted in Fig. 4 for four values of the Froude number) has therefore an effective low-wavenumber cutoff, which is the fundamental ingredient of the Heaviside step spectrum leading to the wake angle [START_REF] Lighthill | Waves in fluids[END_REF]. Its decrease at large k (which is required for numerical convergence) should not affect the wake angle selection, provided that the Froude number is not too small.

The simulated wake patterns shown in Fig. 5 for four Froude numbers reproduce successfully the key features of the ship wake observations. Interestingly, at F r = 0.5, the transverse wave of wavelength λ g is clearly present in the field, in addition to the divergent wave of wavelength 2λ g /3 along the cusp line at α 19 o , as commonly observed behind boats at moderate Froude numbers. Froude numbers below 0.3 produce no wake, because the range of wavenumbers k ∈ [k g , ∞[ is not significantly fed by the disturbance spectrum (see the curve at F r = 0.25 in Fig. 4); this is a limitation of the smooth pressure distribution chosen here, which does not possess the high-wavenumber energy content of the Heaviside spectrum used in the model. At larger Fr, only the divergent wave is present, since the transverse component at k g falls outside the disturbance spectrum E d (k). We can note the broad wake arms at F r = 1, for which E d (k) covers a range where α(k) varies significantly. At larger F r, E d (k) picks only a narrow range of α(k), and the wake angle becomes more precisely selected. The wake angles have been measured from a linear fit through the of the modulus of the complex deformation |ζ(x, y)| (shown in Fig. 5), which conveniently displays the square root of the total energy in the physical space. The resulting wake angles, also plotted in Fig. 2 (yellow squares), are in good agreement with the two branches (3a) and (3b), confirming that the Kelvin-Mach transition at F r 0.5 is correctly captured by the finite size effect of the disturbance.

Our results suggest that the departure from conventional Kelvin wakes reported in the literature can be attributed at least in part to the effect of the finite size of the disturbance. The Mach-like ship wakes described here provide an intriguing example of a seemingly nondispersive wake pattern, similar to a supersonic shock wave, although keeping its specific feathered shape characteristic of a dispersive medium. We are now extending this approach to smaller scales, e.g. for ducks or insects [START_REF] Benzaquen | [END_REF]18], for which richer wake patterns are expected from the interplay between the capillary cutoff and the finite size of the moving body.

FIG. 1 .

 1 FIG. 1. (color online) Airborne images of ship wakes taken from the Google Earth database [13]. (a), Cargo ship near Antwerpen, with α 20 o and Froude number F r 0.15. (b), Speed boat near Toronto, with α 9 o and F r 1.03.For each image, the wake angle α is defined from the slope of the line going through the brightest points resulting from sun glitter or whitecaps (yellow dotted line), which trace the maximum amplitude of the wake. Using the highest available magnification, the ship length L can be accurately determined with the calibration provided by Google Earth.

FIG. 2 .

 2 FIG. 2. (color online) Log-log plot of the wake angle α as a function of the hull Froude number F r = U/ √ gL. Red circles: angles measured from the 37 airborne images of the dataset [13]. Blue line: model (3). Blue dotted line: asymptotic law (4). Yellow squares: numerical simulations.

FIG. 4 .

 4 FIG.4. Selection of the wake angle by the disturbance spectrum. Thick line: wake angle α(k) [Eq. (2)] as a function of the normalized wavenumber k/kg, with kg = g/U 2 = 2π/λg. Thin dashed lines: disturbance spectrum E d (k) used in the numerical simulation, plotted for various Froude numbers. The resulting wake angle α is given by the maximum of α(k) taken over the range of significant E d (k).

  (a) Fr = 0.5, α = 18.9°(b) Fr = 1, α = 15.9°( c) Fr = 2, α = 5.8°(d) Fr = 4, α = 2.9°F IG. 5. (color online) Wake pattern obtained from numerical simulation, for Froude numbers F r = 0.5, 1, 2 and 4. The disturbance size is L = 4 m, and the imaged domain is 140 m. The upper panel of each image shows the physical amplitude R{ζ(x, y)}, and the lower panel shows the modulus |ζ(x, y)|. Wake angles (shown as yellow squares in Fig. 2) are measured from best linear fit of the maximum of |ζ(x, y)|. Black dotted lines indicate the Kelvin angle αK = 19.47 o .

We acknowledge N. Pavloff, E. Raphaël and G. Rousseaux for fruitful discussions, and J.P. Hulin and N. Ribe for their comments to the manuscript.