Pierre Aboulker

Nathann Cohen

Frédéric Havet

Phablo William Lochet

F S Moura

Stéphan Thomassé

Phablo F S Moura

Subdivisions in digraphs of large out-degree or large dichromatic number *

come   L'archive ouverte pluridisciplinaire

Introduction

Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF] established the following.

Theorem 1 (Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF]). There exists an integer g(k) such that every graph with minimum degree at least g(k) contains a subdivision of K k .

For k ≤ 4, we have g(k) = k -1 as first proved by Dirac [START_REF] Andrew | In abstrakten graphen vorhandene vollständige 4-graphen und ihre unterteilungen[END_REF]; for k = 5, we have the estimate 6 ≤ g(5) ≤ 7 by Thomassen [START_REF] Thomassen | Some homeomorphism properties of graphs[END_REF][START_REF] Thomassen | K5-subdivisions in graphs[END_REF]. In general, the order of growth of g(k) is k 2 as shown in [START_REF] Bollobás | Proof of a conjecture of Mader, Erdös and Hajnal on topological complete subgraphs[END_REF] and [START_REF] Komlós | Topological cliques in graphs ii[END_REF].

Similarly, it would be interesting to find analogous results for digraphs. However, the obvious analogue that a digraph with sufficiently large minimum in-and out-degree contains a subdivision of the complete digraph of order n is false as shown by Mader [START_REF] Mader | Degree and local connectivity in digraphs[END_REF].

Let γ be a digraph parameter. A digraph F is γ-maderian if there exists a least integer mader γ (F ) such that every digraph D with γ(D) ≥ mader γ (F ) contains a subdivision of F .

For a digraph D, δ + (D) (resp. δ -(D)) denote the minimum out-degree (resp. in-degree) and δ 0 (D) = min{δ + (D), δ -(D)}. A natural question is to ask which digraphs F are δ + -maderian (resp. δ 0 -maderian).

Observe that every δ + -maderian digraph is also δ 0 -maderian and that mader δ + ≥ mader δ 0 .

For each positive integer k, we denote by [k] the subset of the natural numbers {1, . . . , k}.

On the positive side, Mader conjectured that every acyclic digraphs is δ + -maderian. Since every acyclic digraph is the subdigraph of the transitive tournament on the same order, it is enough to prove that transitive tournaments are δ + -maderian.

Conjecture 2 (Mader [START_REF] Mader | Degree and local connectivity in digraphs[END_REF]). There exists a least integer mader δ + (T T k ) such that every digraph D with δ + (D) ≥ mader δ + (T T k ) contains a subdivision of T T k .

Mader proved that mader δ + (T T 4 ) = 3, but even the existence of mader δ + (T T 5 ) is still open. This conjecture implies directly that transitive tournaments (and thus all acyclic digraphs) are δ 0maderian.

Conjecture 3. There exists a least integer mader δ 0 (T T k ) such that every digraph D with δ 0 (D) ≥ mader δ 0 (T T k ) contains a subdivision of T T k .

In fact, Conjecture 3 is equivalent to Conjecture 2 because if transitive tournaments are δ 0 -maderian, then mader δ + (T T k ) ≤ mader δ 0 (T T 2k ) for all k. Indeed, let D be a digraph with minimum out-degree mader δ 0 (T T 2k ), and let D be the digraph obtained from disjoint copies of D and its converse (the digraph obtained by reversing all arcs) D by adding all arcs from D to D. Clearly, δ 0 (D ) ≥ mader δ 0 (T T 2k ). Therefore D contains a subdivision of T T 2k . Hence, either D or D (and so D) contains a subdivision of T T k .

Both conjectures are equivalent, but the above reasoning does not prove that a δ 0 -maderian digraph is also δ + -maderian. The case of oriented trees (i.e. orientations of undirected trees) is typical. Using a simple greedy procedure, one can easily find every oriented tree of order k in every digraph with minimum in-and out-degree k (so mader δ 0 (T ) = |T | -1 for any oriented tree T ). On the other hand, it is still open whether oriented trees are δ + -maderian and a natural important step towards Conjecture 2 would be to prove the following weaker one. Conjecture 4. Every oriented tree is δ + -maderian.

We give evidences to this conjecture. First, in Subsection 2.1, we prove that every oriented path (i.e. orientation of an undirected path) P is δ + -maderian and that mader δ + (P ) = |V (P )| -1. Next, in Subsection 2.2, we consider arborescences. An out-arborescence (resp. in-arborescence) is an oriented tree in which all arcs are directed away from (resp. towards) a vertex called the root. Trivially, the simple greedy procedure shows that mader δ + (T ) = |T | -1 for every out-arborescence. In contrast, the fact that in-arborecences are δ + -maderian is not obvious since we have no control on the in-degree of each vertex in a digraph of out-degree at least k. We show in Theorem 23 that the in-arborescences are δ + -maderian.

In [START_REF] Mader | Existence of vertices of local connectivity k in digraphs of large outdegree[END_REF], Mader gave another partial result towards Conjecture 2. He proved the existence of a function f 1 (k) such that every digraph D with δ + (D) ≥ f 1 (k) contains a pair of vertices u and v with k disjoint directed paths between u and v. It is however not known if we can insist on these paths to be arbitrarily long. In Theorem 24, we do the first step toward this question by proving it in the case k = 2.

Conjecture 2 states that the acyclic digraphs are δ + -maderian. However, they are not the only ones. For example, it is folklore that every digraph with minimum out-degree at least 1 contains a directed cycle, which is a subdivision of C 2 , the directed 2-cycle. More generally, one can easily show, by considering a directed path of maximum length, that every digraph with minimum out-degree at least k -1 contains a directed cycle of length at least k. In other words, mader δ + ( C k ) = k -1, where C k denotes the directed k-cycle. Furthermore Alon [START_REF] Alon | Disjoint directed cycles[END_REF] showed that every digraph with minimum out-degree at least 64k contains k disjoint directed cycles, which forms a subdivision of the disjoint union of k copies of C 2 . A celebrated conjecture of Bermond and Thomassen [START_REF] Bermond | Cycles in digraph -a survey[END_REF] states that the bound 64k can be decreased to 2k -1.

Conjecture 5 (Bermond and Thomassen [4]). For every positive integer k, every digraph with minimum out-degree at least 2k -1 contains k disjoint directed cycles.

In [START_REF] Alon | Disjoint directed cycles[END_REF], Alon also conjectured the following.

Conjecture 6 (Alon [START_REF] Alon | Disjoint directed cycles[END_REF]). There exists a function h such that every digraph with minimum out-degree

h(k) has a partition (V 1 , V 2 ) such that, for i = 1, 2, D V i has minimum out-degree k.
The difficulty of this question is remarkable, as the existence of h( 2) still remains open. If true, this conjecture implies the following one.

Conjecture 7.

If F 1 and F 2 are δ + -maderian, then the disjoint union of F 1 and F 2 is also δ + -maderian.

Partial positive answers to this conjecture can be obtained via the Erdős-Posá Property. For a digraph F and an integer k, we denote by k × F the disjoint union of k copies of F . A digraph F is said to have the Erdős-Posá Property if for every positive integer k, there exists φ(k), such that every digraph D either contains a subdivision of k × F , or has a set S of size (at most) φ(k) such that D -S contains no subdivision of F . Theorem 8. If F is δ + -maderian and has the Erdős-Posá Property, then k × F is also δ + -maderian for all positive integer k.

Proof. Let F be a maderian digraph having the Erdős-Posá Property for some function φ. Let D be a digraph with δ + (D) ≥ φ(k)+mader δ + (F ). For every set S of size at most φ(k), δ + (D-S) ≥ mader δ + (F ), so D-S contains a subdivision of F . Thus, since F has the Erdős-Posá Property, D contains a subdivision of k × F .

Reed et al. [START_REF] Reed | Packing directed circuits[END_REF] proved that C 2 has the Erdös-Posá Property, and using the Directed Grid Theorem [START_REF] Kawarabayashi | The directed grid theorem[END_REF], Akhoondian et al. [START_REF] Amiri | The Erdos-Posa Property for Directed Graphs[END_REF] showed that many digraphs have the Erdös-Posá Property, in particular all disjoint unions of directed cycles. Hence, Theorem 8 implies that disjoint unions of directed cycles are δ + -maderian.

On the negative side, Thomassen [START_REF] Thomassen | Sign-nonsingular matrices and even cycles in directed graphs[END_REF] showed a construction of digraphs with arbitrarily large inand out-degree and no directed cycles of even length (see also [START_REF] Devos | Immersing complete digraphs[END_REF]). This gives a large class of digraphs that are not δ 0 -maderian, namely: digraphs such that all its subdivisions have a directed cycle of even length. In particular, K 3 , the complete digraph on three vertices, belongs to this class. All digraphs in this class have been characterized by Seymour and Thomassen [START_REF] Seymour | Characterization of even directed graphs[END_REF]. Morever, Devos et al. [START_REF] Devos | Immersing complete digraphs[END_REF] showed the existence of digraphs with large minimum out-degree and in-degree such that there exists no pair of vertices u and v with four internally disjoint directed paths between them, two from u to v and two from v to u. In Theorem 28, we show that if the minimum out-degree is large enough then we can find two vertices u and v with three internally disjoint directed paths between them, one from u to v and two from v to u.

Note that every graph with chromatic number at least p has a subgraph with minimum degree at least p -1. This implies, by Theorem 1, that every graph with chromatic number at least g(k) + 1 contains a subdivision of K k . In the context of digraphs, there exist two natural analogues of the chromatic number. Given a digraph D, the chromatic number of D, denoted by χ(D), is simply the chromatic number of its underlying graph. The dichromatic number of D, denoted by χ(D), is the smallest integer k such that D admits a k-dicolouring. A k-dicolouring is a k-partition {V 1 , . . . , V k } of V (D) such that D V i is acyclic for every i ∈ [k]. Hence, it is natural to ask which digraphs are χ-maderian and which ones are χ-maderian.

Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF] proved that every (k -1) 2 -chromatic digraph contains every oriented forest of order k. Later on, Addario-Berry et al. [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF] slightly improved this value to k 2 /2 -k/2 + 1. This implies that every oriented forest is χ-maderian. Cohen et al. [START_REF] Cohen | Subdivisions of oriented cycles in digraphs with large chromatic number[END_REF] showed that for any positive integer b, there are digraphs of arbitrarily high chromatic number that contain no oriented cycles with less than b blocks. This directly implies that if a digraph is not an oriented forest, then it is not χ-maderian because it contains an oriented cycle, all subdivisions of which have the same number of blocks. Theorem 9. A digraph is χ-maderian if and only if it is an oriented forest.

The χ-maderian digraphs are known but determining mader χ for such digraphs is still open. Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF] made the following conjecture.

Conjecture 10 (Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF]). Every digraph with chromatic number 2k -2 contains every oriented tree of order k as a subdigraph.

An interesting step towards Burr's conjecture is to prove the following consequence of it.

Conjecture 11. If T is an oriented tree of order k, then mader χ (T ) ≤ 2k -2.

In Section 3, we prove that every digraph is χ-maderian. Again determining mader χ for every digraph is still open. Since every digraph D of order n is a subdigraph of K n , the complete digraph of order n, and so mader χ (D) ≤ mader χ ( K n ), it is natural to focus on K n . Problem 12. What is mader χ ( K n ) ?

In Subsection 3.1, we show mader χ ( K n ) ≤ 4 n 2 -2n+1 (n -1) + 1 and more generally that if F is a digraph with n vertices, m arcs and c connected components, then mader χ (F ) ≤ 4 m-n+c (n -1) + 1 (Corollary 36). We also give better upper bounds on mader χ for some particular digraphs.

To prove Theorem 1, Mader showed a stronger result about the average degree. Recall that the average degree of a graph G is d(G) = 2|E(G)|/|V (G)|. He proved that there exists a function g (k) such that every graph G with at least d(G) ≥ g (k) contains a subdivision of K k . The average out-degree of a digraph D is d+ (D) = |A(D)|/|V (D)|. (Note that this is equal to the average in-degree and half the average degree.) A digraph is -→ P 3 -free if it does not contain -→ P 3 as a subdigraph, where -→ P 3 is the dipath on three vertices. There are bipartite graphs with arbitrarily large degree and arbitrarily large girth (recall that the girth of a graph is the length of a smallest cycle or +∞ if it is a forest). Orienting edges of such graphs from one part to the other result in -→ P 3 -free digraphs with arbitrarily large average out-degree and arbitrarily large girth (the girth of a digraph is the girth of its underlying graph). Consequently, a digraph is d+ -maderian only if it is an antidirected forest, that is, an oriented forest containing no -→ P 3 as a subdigraph. This simple necessary condition is also sufficient. Burr [START_REF] Burr | Antidirected subtrees of directed graphs[END_REF] showed that all antidirected forests are d+ -maderian: for every antidirected forest F , mader d+ (F ) ≤ 4|V (F )| -4.

Theorem 13. A digraph is d+ -maderian if and only if it is an antidirected forest.

Addario-Berry et al. [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF] conjectured that the bound 4|V (F )| -4 in Burr's result is not tight. The value k -2 in this conjecture would be best possible, since the oriented star S + k , consisting of a vertex dominating k -1 others, is not contained in any digraph in which every vertex has out-degree k -2. It is also tight because the complete digraph K k-1 has (k -2)(k -1) arcs but trivially does not contain any oriented tree of order k.

As observed in [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF], Conjecture 14 for oriented graphs implies Burr's conjecture (Conjecture 10) for antidirected trees and Conjecture 14 for symmetric digraphs is equivalent to the well-known Erdős-Sós conjecture.

Conjecture 15 (Erdős and Sós [START_REF] Erdős | Some problems in graph theory[END_REF]). Let G be a graph.

If |E(G)| > 1 2 (k -2)|V (G)|, then G contains every tree of order k .
Their conjecture has attracted a fair amount of attention over the last decades. Partial solutions are given in [START_REF] Brandt | The Erdös-Sós conjecture for graphs of girth 5[END_REF][START_REF] Haxell | Tree embeddings[END_REF][START_REF] Saclé | The Erdös-Sós conjecture for graphs without c 4[END_REF]. In the early 1990's, Ajtai, Komlós, Simonovits and Szemerédi announced a proof of this result for sufficiently large m.

Since k-connected and k-edge-connected graphs have minimum degree at least k, Theorem 1 implies that every graph G with connectivity (resp. edge-connectivity) at least g(k) contains a subdivision of K k . Let κ(D), κ (D), be respectively the strong connectivity and the strong arc-connectivity of D.

Problem 16. Are all digraphs κ-maderian? κ -maderian ?

The following conjecture due to Thomassen [START_REF] Thomassen | Configurations in graphs of large minimum degree, connectivity, or chromatic number[END_REF] implies that all digraphs are κ-maderian.

Conjecture 17 (Thomassen [START_REF] Thomassen | Configurations in graphs of large minimum degree, connectivity, or chromatic number[END_REF]). There exists f 1 (k) such that if κ(D) ≥ f 1 (k), and x 1 , . . . , x k and y 1 , . . . , y k are distinct vertices of D, then D contains k disjoint dipaths P 1 , . . . , P k such that P i goes from

x i to y i for all i ∈ [k].
This conjecture would also imply the following one due to Lovász [START_REF] Lovász | Problem 2[END_REF].

Conjecture 18. There exists a integer p such that every p-strongly connected digraph has an even directed cycle.

2 Subdivision in digraphs with large minimum out-degree

Subdivisions of oriented paths

Let P = (x 1 , x 2 , • • • , x n ) be an oriented path. We say that P is an (x 1 , x n )-path. The vertex x 1 is the initial vertex of P and x n its terminal vertex. P is a directed path or simply a dipath, if

x i → x i+1 for all i ∈ [n -1].
Let k 1 be nonnegative integer and k 2 , . . . , k be positive integers. We denote by P (k 1 , k 2 , . . . , k ) the path obtained from an undirected path (v 1 v 2 . . . v +1 ) by replacing, for every

i ∈ [ ], the edge (v i , v i+1 ) by a directed path of length k i from v i to v i+1 if i is odd, and from v i+1 to v i if i is even. (If k 1 = 0, then v 1 = v 2 .)
Theorem 19. Let P (k 1 , k 2 , . . . , k ) be a path, and let D be a digraph with

δ + (D) ≥ i=1 k i . For every v ∈ V (D), D contains a path P (k 1 , k 2 , . . . , k ) with initial vertex v such that k i ≥ k i if i is odd, and k i = k i otherwise.
Proof. By induction on . If = 1, then the result holds trivially. Assume now ≥ 2, and suppose that, for every path P (x 1 , x 2 , . . . , x t ) with t < and every digraph G with δ + (G) ≥ t i=1 x i , G contains a path P (x 1 , x 2 , . . . , x t ) starting at any vertex of G such that x i ≥ x i if i is odd, and

x i = x i otherwise.
Let v be a vertex of D. Since δ + (D) ≥ i=1 k i , there exists a (v, u)-dipath P v,u in D of length exactly k 1 , for some vertex u ∈ V (D). Let D = D -(P v,u -u), let C be the connected component of D containing u, and let H be a sink strong component of C (i.e. a strong component without arcs leaving it) that is reachable by a directed path in C starting at u. We denote by

P u,x a (u, x)-dipath in C such that V (P u,x ) ∩ V (H) = {x}.
Note that no vertex of H dominates a vertex in

V (P u,x ) \ {x} since H is a sink strong component. Thus, δ + (H) ≥ δ + (D) -k 1 ≥ k 2 . As a consequence, H contains a directed cycle of length at least k 2 .
Using this and the fact that H is strongly connected, we conclude that there exists a dipath

P y,x in H from a vertex y ∈ V (H) \ {x} to x of length exactly k 2 . Let G = H -(P y,x -y). One may easily verify that δ + (G) is at least δ + (D) -k 1 -k 2 ≥ i=3 k i . Let Q v,y = P v,u P u,x P y,x . Note that Q v,y is a path P (k 1 , k 2 ) starting at v with k 1 ≥ k 1 .
Therefore, the result follows immediately if = 2. Suppose now that ≥ 3. By the induction hypothesis, G contains a path W y := P (k 3 , . . . , k ) with initial vertex y such that k i ≥ k i if i is odd, and k i = k i otherwise. Therefore, Q v,y W y is the desired path P (k 1 , k 2 , . . . , k ) with initial vertex v.

Since

i=1 k i = |V (P (k 1 , k 2 , . . . , k ))| -1, and that the complete digraph K k on k vertices has minimum out-degree k -1 and contains no path on more than k vertices, we obtain the following corollary.

Corollary 20. mader δ + (P ) = |V (P )| -1 for every oriented path P .

Subdivision of in-arborescences

The aim of this subsection is to prove that the in-arborescences are δ + -maderian. We need some preliminary results. The first one is the vertex and directed version of the celebrated Menger's theorem [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]. (See also [START_REF] Göring | Short proof of Menger's theorem[END_REF] for a short proof.) Theorem 21 (Menger's theorem). Let D be a digraph, and let S, T ⊆ V (D). The maximum number of vertex-disjoint (S, T )-dipaths is equal to the minimum size of an (S, T )-vertex-cut. Lemma 22. Let D be a digraph, let S ⊆ V (D) be a nonempty subset of vertices of in-degree 0 in D, and let

T ⊆ V (D) such that T ∩ S = ∅. If d + (v) ≥ ∆ -(D) for all v ∈ V (D) \ T , then there exist |S| vertex-disjoint (S, T )-dipaths in D.
Proof. Suppose to the contrary that there do not exist |S| vertex-disjoint (S, T )-dipaths in D. By Menger's theorem, there exists a set of vertices X ⊆ V (D) with cardinality |X| < |S| which is an (S, T )vertex-cut. Let C be the set of vertices in D -X that are reachable in D by a dipath with initial vertex in S \ X. Set k = |X ∩ S|. Observe that k < |S|.

Let us count the number a(C, X) of arcs with tail in C and head in X. Since the vertices in S have in-degree 0 and every vertex in C has out-degree at least ∆ -(D),

a(C, X) ≥ |C| • ∆ -(D) -[|C| -(|S| -k)] • ∆ -(D) = (|S| -k) • ∆ -(D).
Moreover, a(C, X) is at most the number of arcs with head in X which is at most

(|X| -k) • ∆ -(D), because the vertices in S ∩ X have in-degree 0. Hence (|S| -k) • ∆ -(D) ≤ a(C, X) ≤ (|X| -k) • ∆ -(D). This is a contradiction to |X| < |S|.
Let k and be positive integers. The -branching in-arborescence of depth k, denoted by B(k, ), is defined by induction as follows.

• B(0, ) is the in-arborescence with a single vertex, which is the root and the leaf of B(0, ).

• B(k, ) is obtained from B(k -1, )
k i=0 i = 1-k+1 1-
. Observe that every in-arborescence T is a subdigraph of B(k, ) with k = ∆ -(T ) and the maximum length of a dipath in T . Therefore to prove that in-arboresences are δ + -maderian, it suffices to show that B(k, ) is δ + -maderian for all k and .

We define a recursive function f : N → N as follows. For all positive integers k and such that ≥ 2, f (1, ) = and, for k ≥ 2, we define

f (k, ) = t(k, ) • ( -1) • k + t(k, ), where t(k, ) := f (k -1, b(k -1, ) • ( -1) + 1) • b(k -1, ).
If D is a family of digraphs, a packing of elements of D is the disjoint union of copies of elements of D. Let F be a packing of -branching in-arborescences subdigraphs of any non-zero depth in D that covers the maximum number of vertices. We denote by U ⊆ V (D) the set of vertices not covered by F, that is, U = V (D) \ A∈F V (A). Let r A denote the root of the in-arborescence A, for each A ∈ F, and let R = {r A ∈ V (D) : A ∈ F} be the set of the roots of the arborescences in F.

We now construct the digraph H with vertex set R such that there exists an arc (r A , r B ) in H if and only if r A dominates some vertex of V (B) in D.

Claim 23.1. If δ + (H) ≥ t(k, )/b(k -1, ), then D contains a subdivision of B(k, ). Subproof. Let p = b(k -1, ) • ( -1) + 1. By the induction hypothesis, H contains a subdivision T of B(k -1, p). Let R be the set of branching vertices of T , that is, R = {r ∈ T : d - T (r) = p}.
We assume that each in-arborescence of F has at most b(k -1, ) vertices, as any larger arborescence would yield the theorem. Thus, for each r ∈ R , there exists a vertex h r in the in-arborescence rooted at r such that h r is dominated in D by vertices of V (T ). Similarly, for each r ∈ V (T ) with in-degree 1, there exists a vertex h r in the in-arborescence rooted at r such that h r is dominated in D by a vertex of V (T ). Using these remarks, we next define a procedure to obtain a subdigraph of T that is a subdivision of B(k -1, ).

For each r ∈ R , we remove from T all arcs with head r but exactly arcs from vertices in V (T ) that dominate h r in D. We denote by T the component of the subdigraph of T obtained by applying the above-described procedure and that contains the root of T . One may easily verify that T is a subdivision of B(k -1, ). Let P r be the path from h r to r in the in-arborescence corresponding to r, for every r ∈ V (T ) such that either r ∈ R or r has in-degree 1.

Let Q be the in-arborescence obtained from T in the following way. For each r ∈ V (T ) such that either r ∈ R or r has in-degree 1, we add h r to T , and we add an arc from every in-neighbour of r in T to h r . Additionally, we remove all arcs with head r in T , and link h r to r by using the dipath P r . Finally, for each r ∈ V (T ) that is a leaf, we replace r by its corresponding in-arborescence belonging to F.

By this construction, we have that Q is a subdigraph of D such that every internal vertex has either in-degree or 1. Furthermore, it has depth at least k. Therefore, by possibly pruning some levels of Q, we obtain a subdivision of B(k, ).

♦

Suppose now δ + (H) < t(k, )/b(k-1, ). Observe that, for every v ∈ R such that d + H (v) < t(k, )/b(k- 1, ), we have, in the digraph D, that d + U (v) ≥ t(k, ) • ( -1) • k since δ + (D) ≥ t(k, ) • ( -1) • k + t(k, ). We define X = {v ∈ R : d + U (v) ≥ t(k, ) • ( -1) • k}. Let D be the digraph obtained from D[U ∪ X]
by removing all arcs with head in X. From D , we construct a digraph G by replacing every vertex v ∈ X by t(k, ) new vertices v 1 , . . . , v t(k, ) , and adding, for each i ∈ [t(k, )], at least ( -1)

• k arcs from v i to N + D (v) in such a way that d - D (u) = d - G (u), for all u ∈ N + D (v).
In other words, we "redistribute" the out-neighbours of v in D among its t(k, ) copies in G so that every copy has out-degree at least ( -1) • k, and the in-degrees of vertices belonging to U are not changed. Let S ⊆ V (G) be the set of vertices that replaced those of X, that is, S = v∈X {v 1 , . . . , v t(k, ) }. Let T be the set of vertices in U that have large out-degree outside U in the digraph D, more formally, T = {v ∈ U :

d + V (D)\U (v) ≥ t(k, ) + 1}. For every i ∈ [k -1], let F i = {A ∈ F : A has depth exactly i}. Note that {F i } i∈[k-1]
forms a partition of the packing F. Additionally, observe that, due to the maximality of F, every vertex in U is dominated by at most -1 vertices belonging to U , and by at most -1 roots of in-arborescences in F i , for each i ∈ [k-1]. Thus, the in-degree in G of every vertex belonging to U is at most ( -1)+( -1)

•(k-1) = ( -1) • k. Therefore, we have ∆ -(G) ≤ ( -1) • k. Moreover, since δ + (D) ≥ t(k, ) • ( -1) • k + t(k, ), we have d + G (v) ≥ t(k, ) • ( -1) • k for every v ∈ U \ T . Hence, d + G (v) ≥ ( -1)
• k, for every v ∈ V (G) \ T . By Lemma 22, there exists a set P of |S| vertex-disjoint paths from S to T in G.

Note that, in D, every vertex belonging to T has at least t(k, ) + 1 out-neighbours in V (D) \ U . Therefore one can greedily extend each path of P with an out-neighbour of its terminal vertex in V (D)\U in order to obtain a set P of |S| vertex-disjoint paths from S to V (D) \ U such that for any v ∈ X all the paths in P with initial vertex v have distinct terminal vertices (and different from v).

We now construct the digraph M on the vertex set R where there exists an arc from v = r A to r B in M whenever either r A dominates some vertex of V (B) in D, or there is a dipath from some v i to V (B) in P .

Since, for each v ∈ X, all vertices in {v i } i∈[t(k, )] are the initial vertices of vertex-disjoint dipaths in P , we obtain δ + (M ) ≥ t(k, )/b(k -1, ). Therefore, the result follows by Claim 23.1 with M playing the role of H.

Cycles with two blocks

We denote by C(k 1 , k 2 ) the digraph which is the union of two internally disjoint dipaths, one of length k 1 and one of length k 2 with the same initial vertex and same terminal vertex. C(k 1 , k 2 ) may also be seen as an oriented cycles with two blocks, one of length k 1 and one of length k 2 . Recall that the blocks of an oriented cycle are its maximal directed subpaths.

Theorem 24. Let D be a digraph with δ + (D) ≥ 2(k 1 + k 2 ) -1. Then D contains a subdivision of C(k 1 , k 2 ).
Proof. Let us assume, without loss of generality, that k 1 ≥ k 2 . Let be a positive integer. An ( , k 1 , k 2 )-fork is a digraph obtained from the union of three disjoint dipaths A = (a 0 , a 1 ,

• • • , a ), B 1 = (b 1 1 , • • • , b 1 k1-1 ) and B 2 = (b 2 1 , • • • , b 2 k2-1
) by adding the arcs (a , b 1 1 ) and (a , b 2 1 ).

Since a (1, k 1 , k 2 )-fork has k 1 + k 2 + 1 vertices and δ + (D) ≥ k 1 + k 2 + 1, then D contains a (1, k 1 , k 2 )fork as a subdigraph. Let ≥ 1 be the largest integer such that D contains an ( , k 1 , k 2 )-fork as a subdigraph. Let F be such a fork. For convenience, we denote its subpaths and vertices by their labels in the above definition.

If there exist i, j ∈ [ ] ∪ {0}, where i ≤ j (resp. j ≤ i), such that a i ∈ N + (b 1 k1-1 ) and a j ∈ N + (b 2 k2-1 ), then the union of the dipaths (a , B 1 , a i , • • • , a j ) and (a , B 2 , a j ) (resp. (a , B 1 , a i ) and

(a , B 2 , a j , • • • , a i )) is a subdivision of C(k 1 , k 2 ). Suppose now that b 1 k1-1 has no out-neighbour in {a 0 , • • • , a -1 }, that is, N + (b 1 k1-1 ) ∩ (A \ {a }) = ∅ (the case N + (b 2 k2-1 ) ∩ (A \ {a }) = ∅ is similar). Since |B 1 ∪ B 2 ∪ {a }| = k 1 + k 2 -1 and δ + (D) ≥ 2(k 1 + k 2 -1) + 1, b 1
k1-1 has two distinct out-neighbours, say c 1 1 and c 2 1 , not in F . Let i 1 ≥ 1 be the largest integer such that there exist two disjoint dipaths C 1 and C 2 in D -F with initial vertex c 1 1 and c 2 1 , respectively, and length i 1 and

i 2 = min{k 2 , i 1 }. Set C 1 = (c 1 1 , • • • , c 1 i1 ) and C 2 = (c 2 1 , • • • , c 2 i2 ). By maximality of , if i 1 ≥ k 2 , then i 1 < k 1 -1. Otherwise, the union of A ∪ B 1 , C 1 , C 2 , (b 1 k1-1 , c 1 1 ) and (b 1 k1-1 , c 2 1 ) would contain an ( + k 1 -1, k 1 , k 2 )-fork, contradicting the maximality of .
Suppose to the contrary that both c 1 i1 and c 2 i2 have no out-neighbour in A \ {a }.

Since |V (B 1 ) ∪ V (B 2 ) ∪ {a } ∪ V (C 1 ) ∪ V (C 2 )| = k 1 + k 2 + i 1 + i 2 -1 < 2(k 1 + k 2 ) -2 (since i 1 + i 2 < k 1 + k 2 -1) and δ + (D) ≥ 2(k 1 + k 2 -1) + 1, then there exist c 1 i1+1 , c 2 i2+1 ∈ V (D -(F ∪ C 1 ∪ C 2 )) such that (c 1 i1 , c 1 i1+1 ), (c 2 i2 , c 2 i2+1 ) ∈ A(D) and c 1 i1+1 = c 2 i2+1
. This contradicts the maximality of i 1 . Henceforth, we assume that c 1 i1 has an out-neighbour a j ∈ A \ {a } for some 0 ≤ j < . The case in which c 2 i2 has an out-neighbour in A \ {a } is similar.

If b 2 k2-1 has also an out-neighbour a m ∈ A\{a }, then the union of the dipaths (a , B 1 , C 1 , a j , . . . , a m ) and (a , B 2 , a m ) (if m ≥ j) or of the dipaths (a , B 1 , C 1 , a j ) and (a , B 2 , a m , . . . ,

a j ) (if m < j) is a subdivision of C(k 1 , k 2 ). If b 2 k2-1 has an out-neighbour z ∈ V (C 1 ∪ C 2 ), say z = c 1 h for some h ≤ i 1 (the case in which z ∈ V (C 2 ) is similar), then the union of the dipaths (a , B 2 , c 1 h ) and (a , B, c 1 1 , • • • , c 1 h ) is a subdivision of C(k 1 , k 2 ).
So, we may assume that b 2 k2-1 has no out-neighbour in For sake of contradiction, assume that both c 3 i3 and c 4 i4 have no out-neighbour in

A \ {a } ∪ C 1 ∪ C 2 . Hence, b 2 k2-1 has two distinct out-neighbours, say c 3 1 and c 4 1 , not in F ∪ C 1 ∪ C 2 . Let i 3 ≥
(A \ {a }) ∪ C 1 ∪ C 2 . Because |V (B 1 ) ∪ V (B 2 ) ∪ V (C 3 ) ∪ V (C 4 ) ∪ {a }| = k 1 + k 2 + i 3 + i 4 -1 < 2(k 1 + k 2 ) -2 (since i 3 + i 4 < k 1 + k 2 -1) and δ + (D) ≥ 2(k 1 + k 2 -1) + 1, then there exist distinct vertices c 3 i3+1 , c 4 i4+1 ∈ V (D -(F ∪C 1 ∪C 2 ∪C 3 ∪C 4 )) (if i 3 ≥ k 2 , we only define c i3+1 ) such that (c 3 i3 , c 3 i3+1 ), (c 4 i4 , c 4 i4+1 ) ∈ A(D)
. This contradicts the maximality of i 3 .

So one of c 3 i3 , c 4 i4 has an out-neighbour in (A \ {a }) ∪ C 1 ∪ C 2 . We assume that it is c 3 i3 ; the case when it is c 4 i4 is similar. If c 3 i3 has an out-neighbour a q ∈ A \ {a } (for some q < ), then the union of either the dipaths (a , B 1 , C 1 , a j , . . . , a q ) and (a , B 2 , C 3 , a q ) (if q ≥ j), or the dipaths (a

, B 1 , C 1 , a j ) and (a , B 2 , C 3 , a q , • • • , a j ) (if q < j), is a subdivision of C(k 1 , k 2 ). If c 3 i3 has an out-neighbour c 1 h ∈ V (C 1 ) for some 1 ≤ h ≤ i 1 , then the union of the dipaths (a , B 1 , c 1 1 , • • • , c 1 h ) and (a , B 2 , C 3 , c 1 h ) is a subdivision of C(k 1 , k 2 ). Similarly, we find a subdivision of C(k 1 , k 2 ) if c 3 i3 has an out-neighbour in C 2 .
Theorem 24 shows that an oriented cycle with two blocks C is maderian and mader δ + (C) ≤ 2|V (C)| -1. A natural question is to ask whether this upper bound is tight or not. Proof. The complete digraph on k vertices has minimum in-and out-degree k -1, and it trivially contains no subdivision of C(k, 1) because it has less vertices than C(k, 1). Hence mader δ + (C(k, 1)) ≥ mader δ 0 (C(k, 1)) ≥ k.

Consider now a digraph D with δ + (D) ≥ k. Let P be a longest dipath in D and let u be its terminal vertex. Necessarily N + (u) ⊆ V (P ). Let v (resp. w) be the first (resp. last) vertex of N + (u) along P . The path P [v, w] contains all vertices of N + (u), so it has length at least k -1. Hence the union of (u, v) ∪ P [v, w] and (u, w) is a subdivision of C(k, 1).

A step further towards Conjecture 2 would be to prove that every oriented cycle is δ + -maderian. We even conjecture that for every oriented cycle

C mader δ + (C) ≤ 2|V (C)| -1.
Conjecture 27. Let D be a digraph with δ + (D) ≥ 2k -1. Then D contains a subdivision of any oriented cycle of order k

Three dipaths between two vertices

A slight adaptation of the proof of Theorem 24 leads to a stronger result. Let k 1 , k 2 , k 3 be positive integers. Let P (k 1 , k 2 ; k 3 ) be the digraph formed by three internally disjoint paths between two vertices x, y, two (x, y)-dipaths, one of size at least k 1 , the other of size at least k 2 , and one (y, x)-dipath of size at least k 3 . When we want to insist on the vertices x and y, we denote it by P xy (k 1 , k 2 ; k 3 ).

Theorem 28. Let k 1 , k 2 , k 3 be positive integers with k 1 ≥ k 2 . Let D be a digraph with δ + (D) ≥ 3k 1 + 2k 2 + k 3 -5. Then D contains P (k 1 , k 2 ; k 3 ).
Proof. Let be an integer. An ( , k 3 ; k 1 , k 2 )-fork is a digraph obtained from the union of four disjoint directed paths P = (p 1 , . . . , p

), A = (a 1 , • • • , a k3-1 ), B 1 = (b 1 1 , • • • , b 1 k1-1 ) and B 2 = (b 2 1 , • • • , b 2 k2-1 ) by adding the arcs (p , a 1 ), (a k3-1 , b 1 1 ) and (a k3-1 , b 2 1 ). Since a (1, k 3 ; k 1 , k 2 )-fork has k 1 + k 2 + k 3 -2 vertices and δ + (D) ≥ k 1 + k 2 + k 3 -2, then D contains a (1, k 3 ; k 1 , k 2 )
-fork as a subdigraph. So, let ≥ 1 be the largest integer such that D contains an ( , k 3 ; k 1 , k 2 )-fork as a subdigraph. Let F be such a fork. For convenience, we denote its subpaths and vertices by their labels in the above definition.

If there exist i, j ∈ [ ], with i ≤ j, such that

p i ∈ N + (b 1 k1-1 ) and p j ∈ N + (b 2 k2-1 ) or p i ∈ N + (b 2 k2-1 ) and p j ∈ N + (b 1 k1-1 ), then F contains a P a k 3 -1 pj (k 1 , k 2 ; k 3 ). So, let us assume that b 1
k1-1 has no out-neighbour in P (the case where b 2 k2-1 has no out-neighbour in P is similar).

Since |A ∪ B 1 ∪ B 2 | = k 1 + k 2 + k 3 -3 and δ + (D) ≥ k 1 + k 2 + k 3 -1, b 1
k1-1 has two distinct out-neighbours, say c 1 1 and c 2 1 , not in F . Let i 1 ≥ 1 be the largest integer such that there exist two disjoint directed paths C 1 and C 2 in D -F with initial vertex c 1 1 and c 2 1 respectively and length i 1 and i 2 = min{k 2 -1, i 1 }. If i 1 ≥ k 1 -1, then i 2 ≥ k 2 -1, and thus P ∪ A ∪ B 1 ∪ C 1 ∪ C 2 would contain a fork that contradicts the maximality of . Hence we may assume that i 1 ≤ k 1 -2 (and in particular

|V (C 1 ) ∪ V (C 2 )| ≤ k 1 + k 2 -3).
For sake of contradiction, assume that both c 1 i1 and c 2 i2 have no out-neighbour in P . Since

|V (A) ∪ V (B 1 ) ∪ V (B 2 ) ∪ V (C 1 ) ∪ V (C 2 )| ≤ 2k 1 + 2k 2 + k 3 -6 < δ + (D) -2, then there exist c 1 i1+1 , c 2 i2+1 ∈ V (D -(F ∪ C 1 ∪ C 2 )) such that (c 1 i1 , c 1 i1+1 ), (c 2 i2 , c 2 i2+1 ) ∈ A(D) and c 1 i1+1 = c 2 i2+1
. This contradicts the maximality of i 1 . Henceforth, we assume that c 1 i1 has an out-neighbour p i ∈ P (the case in which c 2 i2 has an out-neighbour in P is similar).

If b 2 k2-1 has also an out-neighbour p j ∈ P , then F ∪ C 1 contains a P a k 3 pj (k 1 , k 2 ; k 3 ) if i ≤ j, and a

P a k 3 pi (k 1 , k 2 ; k 3 ) if j ≤ i.
So, we may assume that b 2 k2-1 has no out-neighbour in P . Hence, b 2 k2-1 has two distinct outneighbours, say c 3 1 and c 4 1 , not in F ∪ C 1 . Let i 3 ≥ 1 be the largest integer such that there exist two disjoint dipaths C 3 and C 4 in D -(F ∪ C 1 ) with initial vertex c 3 1 and c 4 1 respectively and length i 3 and

i 4 = min{k 2 -1, i 3 }. If i 3 ≥ k 1 , then i 4 ≥ k 2 -1 and thus P ∪ A ∪ B 2 ∪ C 3 ∪ C 4 contains
a fork that contradicts the maximality of F . Thus, we may assume that i 3 ≤ k 1 -2. In particular

|V (C 3 ) ∪ V (C 4 )| ≤ k 1 + k 2 -3.
Suppose to the contrary that both c 3 i3 and c 4 i4 have no out-neighbour in P , where c 3 i3 and c 4 i4 are the last vertices of C 3 and C 4 . Note that

|V (A)∪V (B 1 )∪V (B 2 )∪V (C 1 )∪V (C 3 )∪V (C 4 )| ≤ 3k 1 +2k 2 +k 3 -7 ≤ δ + (D) -2. Hence, there exist distinct vertices c 3 i3+1 , c 4 i4+1 ∈ V (D -(F ∪ C 1 ∪ C 3 ∪ C 4 )) such that (c 3 i3 , c 3 i3+1 ), (c 4 i4 , c 4 i4+1 ) ∈ A(D)
. This contradicts the maximality of i 3 . Therefore, one of c 3 i3 , c 4 i4 has an out-neighbour in p j in P . We assume that it is c 3 i3 ; the case when it is c 4 i4 is similar. We conclude that F ∪ C 1 ∪ C 3 contains a P a k 3 pj (k 1 , k 2 ; k 3 ) if i < j, and a P a k 3 pi (k 1 , k 2 ; k 3 ) if j < i.

Subdivisions in digraphs with large dichromatic number

Recall that a k-dicolouring is a k-partition {V 1 , . . . , V k } of V (D) such that D V i is acyclic for every i ∈ [k], and that the dichromatic number of D is the minimum k such that D admits a k-dicolouring. In this section, we first prove that every digraph is χ-maderian. We need some preliminaries. The first one is an easy lemma, whose proof is left to the reader. Lemma 29. The dichromatic number of a digraph is the maximum of the dichromatic numbers of its strong components.

Our proof is based on levelling. Forthwith, we introduce the necessary definitions. Given a digraph D, the distance from a vertex x to another y, denoted by dist D (x, y) or simply dist(x, y) when D is clear from the context, is the minimum length of an (x, y)-dipath or +∞ if no such dipath exists. An out-generator in D is a vertex u such that, for every x ∈ V (D), there exists an (u, x)-dipath in D. Analogously, an in-generator in D is a vertex u such that, for every x ∈ V (D), there exists an (x, u)-dipath in D. For simplicity, we call a vertex generator if it is an in-or out-generator. Observe that every vertex in a strong digraph is an in-and out-generator.

Let D be a digraph. Let w, u be in-and out-generators of D, respectively. We remark that w and u are not necessarily different. For every nonnegative integer i, the ith out-level from u in D is the set

L u,+ i = {v ∈ V (D) | dist D (u, v) = i}, and the ith in-level from w in D is the set L w,- i = {v ∈ V (D) | dist D (v, w) = i}. Note that i L u,+ i = i L w,- i = V (D).
An out-Breadth-First-Search Tree or out-BFS-tree T + with root u, is a subdigraph of D spanning V (D) such that T + is an oriented tree and, for every

v ∈ V (D), dist T + (u, v) = dist D (u, v). Similarly, an in-Breadth-First-Search Tree or in-BFS-tree T -with root w, is a subdigraph of D spanning V (D) such that T -is an oriented tree and, for every v ∈ V (D), dist T -(v, w) = dist D (v, w).
It is well-known that if D has an out-generator, then there exists an out-BFS-tree rooted at this vertex. Likewise, if D has an in-generator, then there exists an in-BFS-tree rooted at this generator.

Let T denote an in-or out-BFS-tree rooted at u. For any vertex x of D, there is a single (u, x)-dipath in T if T is an out-BFS-tree, and a single (x, u)-dipath in T if T is an in-BFS-tree. The ancestors or successors of x in T are naturally defined. If y is an ancestor of x, we denote by T [y, x] the (y, x)-dipath in T . If y is a successor of x, we denote by T [x, y] the (x, y)-dipath in T .

Lemma 30. Let D be a strong digraph and let T be an in-or out-BFS-tree in D. There is a level L such that χ(D L ) ≥ χ(D)/2.

Proof. First, let us suppose, without loss of generality, that T is an out-BFS-tree in D. The proof when T is an in-BFS-tree is analogous.

Let D 1 and D 2 be the subdigraphs of D induced by the vertices of odd and even levels, respectively. Since there is no arc from L i to L j for every j ≥ i + 2, the strong components of D 1 and D 2 are contained in the levels. Hence, by Lemma 29,χ

(D 1 ) = max{ χ(D L i ) | i is odd} and χ(D 2 ) = max{ χ(D L i ) | i is even}. Moreover, note that V (D 1 ) ∪ V (D 2 ) = V (D) because D is strong. Therefore, χ(D) ≤ χ(D 1 ) + χ(D 2 ) ≤ 2 • max{ χ(D L i ) | i ∈ N}.
Lemma 31. Let F be a digraph and let a = xy be an arc in A(F ). If F -a is χ-maderian, then F is χ-maderian, and mader χ (F ) ≤ 4 • mader χ (F -a) -3

Proof. Let c = mader χ (F -a) and let D be a digraph with χ(D) ≥ 4c -3. We shall prove that D contains a subdivision of F .

By Lemma 29, we may assume that D is strong. Let u be a vertex in D and T u an out-BFS-tree with root u. By Lemma 30, there is a level Proof. We prove the result by induction on m. If m = 0, then F is an empty digraph which is trivially χ-maderian and mader χ (F ) = n. If m > 0, then consider an arc a ∈ A(F ). By Lemma 31, we obtain mader χ (F ) ≤ 4 • mader χ (F -a) -3. By the induction hypothesis, mader χ (F -a) ≤ 4 m-1 (n -1) + 1. Therefore, mader χ (F ) ≤ 4 m (n -1) + 1.

L u such that χ(D L u ) ≥ 2c -1. By Lemma 29, there is a strong component C of D L u such that χ(C) = χ(D L u ) ≥ 2c -1. Since D is strong, there is a shortest (v, u)-dipath P in D such that V (P ) ∩ V (C) = {v}. Let T v be an in-BFS-tree in C rooted at v. By Lemma 30, there is a level L v of T v such that χ(D L v ) ≥ c. Now since mader χ (F -a) = c, D L v contains a subdivision S of F -a.
Observe that Theorem 32 generalizes the consequence of Theorem 1, stating that every graph with sufficiently large chromatic number contains a subdivision of K k . In fact this statement corresponds to the case of symmetric digraphs of Theorem 32.

Better bounds on mader χ

The bound on mader χ given in Theorem 32 is not optimal. The aim of this subsection is to find better upper bounds.

A Proof. The proof is identical to the one of Theorem 32, but instead of starting the induction with empty digraphs, we start it with a forest that is the union of spanning trees of the connected components.

Corollary 36 implies that mader χ ( K n ) ≤ 4 n(n-2)+1 (n -1) + 1. On the other hand, we have mader χ ( K n ) ≥ Ω( n 2 log n ). Indeed, consider a tournament T on p vertices with a subdivision S of K n . For every two distinct vertices u, v of K n , at least one of the arcs (u, v), (v, u) is subdivided in S. Hence, S has at least n + n 2 = n+1 2 vertices, so p ≥ n+1 2 . Erdős and Moser [START_REF] Erdős | On the representation of directed graphs as unions of orderings[END_REF] proved that for every integer p, there exists a tournament T p on p vertices with no transitive tournament of order 2 log p + 1. Thus χ(T p ) ≥ p 2 log p . Now set p = n+1 2 -1. The tournament T p contains no subdivision of K n and χ(T p ) ≥ p 2 log p . Hence mader χ ( K n ) ≥ p 2 log p + 1 ≥ Ω( n 2 log n ). A k-source in a digraph is a vertex x with in-degree 0 and out-degree at most k; a k-sink in a digraph is a vertex x with out-degree 0 and in-degree at most k. A digraph is k-reducible if it can be reduced to the empty digraph by repeated deletion of k-sources or k-sinks. For instance, the 1-reducible digraphs are the oriented forests.

Lemma 37. Let F be a digraph having a 2-source x. Then mader χ (F ) ≤ 2 mader χ (F -x) -1.

Proof. Suppose that F -x is ( χ ≥ c)-maderian. We shall prove that F is ( χ ≥ 2c -1)-maderian.

Let D be a digraph with χ(D) ≥ 2c -1. By Lemma 29, we may assume that D is strong. Let u be a vertex in D, and let T be a BFS-tree with root u. By Lemma 30, there is a level such that χ(D L ) ≥ c. Consequently, D L contains a subdivision S of F -x. Let y 1 and y 2 be the vertices in S corresponding to the two out-neighours of x in F . Let v be the least common ancestor of y 1 and y 2 and, for i ∈ {1, 2}, let P i be the (v, y i )-dipath in T . Therefore, we conclude that the digraph S ∪ P 1 ∪ P 2 is a subdivision of F in D.

Conjecture 14 (

 14 Addario-Berry et al. [1]). Let D be a digraph. If |A(D)| > (k -2)|V (D)|, then D contains every antidirected tree of order k as a subdigraph.

  by taking each leaf of B(k -1, ) in turn and adding new vertices dominating this leaf. The root of B(k, ) is the one of B(k -1, ), and the leaves of B(k, ) are the newly added vertices, that is, those not in V (B(k -1, )). The number of vertices of B(k, ) is denoted by b(k, ); so b(k, ) =

Theorem 23 .

 23 Let k and ≥ 2 be positive integers, and let D be a digraph with δ + (D) ≥ f (k, ). Then D contains a subdivision of B(k, ).Proof. We prove the result by induction on k and .If k = 1, then δ + (D) ≥ . Thus, ∆ -(D) • |V (D)| ≥ v∈V (D) d -(v) = v∈V (D) d + (v) ≥ •|V (D)|.Hence there is a vertex with in-degree at least in D and, consequently, the result follows when k = 1. Assume now k ≥ 2, and suppose that, for every positive integers k < k and , and every digraph H with δ + (H) ≥ f (k , ), H contains a subdivision of the -branching in-arborescence of depth k .

  1 be the largest integer such that there exist two disjoint dipaths C 3 and C 4 in D -(F ∪C 1 ∪C 2 ) with initial vertex c 3 1 and c 4 1 , respectively, and length i 3 and i 4 = min{k 2 , i 3 }. By the maximality of , if i 4 ≥ k 2 then i 3 < k 1 -1 since otherwise the union of A∪B 2 , C 3 , C 3 , (b 2 k2-1 , c 3 1 ) and (b 2 k2-1 , c 4 1 ) would contain an ( +k 1 -1, k 1 , k 2 )-fork, contradicting the maximality of .

Problem 25 .

 25 What it the value of mader δ + (C(k 1 , k 2 )) ? Proposition 26. For any positive integer k, mader δ + (C(k, 1)) = mader δ 0 (C(k, 1)) = k.

  With a slight abuse of notation, let us call x and y the vertices in S corresponding to the vertices x and y of F . Now T v [x, v] ∪ P ∪ T u [u, y] is a directed (x, y)-walk with no internal vertex in L v . Hence it contains an (x, y)-dipath Q whose internal vertices are not in S. Therefore, S ∪ Q is a subdivision of F in D. Theorem 32. Every digraph F is χ-maderian. More precisely, mader χ (F ) ≤ 4 m (n -1) + 1, where m = |A(F )| and n = |V (F )|.

  digraph is k-χ-critical if χ(D) = k and χ(D ) < k for every proper subdigraph D of D. Proposition 33. If D is k-χ-critical, then δ 0 (D) ≥ k -1. Proof. Let v be a vertex of D. Since D is k-χ-critical, χ(D -v) ≤ k -1, so D -v admits a (k -1)dicolouring {V 1 , . . . , V k-1 }. Thus, for each i ∈ [k -1], D V i ∪ {v} has a directed cycle that contains v.Therefore, v has an in-neighbour and an out-neighbour in each V i .Corollary 34. mader χ (F ) ≤ mader δ 0 (F ) + 1 for all digraph F . Corollary 35. mader χ (F ) = |V (F )| for all oriented forest F . Let us denote by cc(F ) the number of connected components of F , that are the connected components of the underlying graph. Corollary 36. For every digraph F , we have mader χ (F ) ≤ 4 m-n+cc(F ) (n -1) + 1, where m = |A(F )| and n = |V (F )|.

Corollary 38 .

 38 The following statements hold. (a) mader χ (F ) ≤ 2 |V (F )|-2 + 1 for every 2-reducible digraph F or order at least 2. (b) mader χ (C) ≤ 2 • |V (C)| -3 for every oriented cycle C of order at least 3. Proof. Statement (a) follows by induction on |V (F )|. Observe that the result trivially holds when |V (F )| = 2. To prove statement (b), consider the following two complementary cases. If C is directed, say C = C k , then mader χ (C) ≤ mader δ 0 (C) + 1 ≤ mader δ + (C) ≤ k ≤ 2k -3. If C is not directed, then it contains a 2-source x. Hence C -x is an oriented path, and, by Corollary 35, it follows that mader χ (C -x) = |C -x| = |C| -1. Conjecture 39. mader χ (C) ≤ |C| for every oriented cycle C.

* This work was supported by ANR under contract STINT ANR-13-BS02-0007 † Supported by FAPESP Proc. 2013/19179-0, 2015/11930-4


Andrea Tomassilli

Nicolas Huin

Frédéric Giroire

Brigitte Jaumard

Energy-Efficient Service Chains with Network Function Virtualization

Keywords: Network Function Virtualization, Service Function Chains, Software Defined Networks, Energy Efficiency, Optimization Virtualisation des fonctions réseaux, Chaînes de fonctions de service, Réseaux logiciels, Efficacité énergétique, Optimisation

Service Function Chains (SFCs) are an ordered sequence of network functions, such as firewall. Using the new approaches of Software Defined Networks and of Network Function Virtualization (NFV), the network functions can be virtualized and executed on generic hardware. To optimize network management, it is thus crucial to place dynamically the network functions at the right positions in the network according to the network traffic. In this paper, we consider the problem of SFC placement with the goal of minimizing network energy consumption. We model the problem as an Integer Linear Program, which can be used to solve small instances. To solve larger instances, we propose GreenChains, a heuristic algorithm. We exhibit the benefit of dynamic routing and of NFV on the energy savings. We show that between 30 to 55% of energy can be saved for typical ISP networks, while respecting the SFC constraints.

Introduction

With the large yearly increase of Internet traffic, future networks will have to be more energy efficient [START_REF] Matsubara | Toward future networks: a viewpoint from itu-t[END_REF]. One of the classic methods to reduce the energy consumption of networks is to try to aggregate network traffic on a small number of network equipments in order to put to sleep the unused hardware. However, a difficulty is that today's traffic has to pass through a number of network functions, such as deep packet inspection (DPI), firewall, load balancing, WAN optimization. The network functions often need to be applied in a specific order, e.g. in a security scenario, the firewall has to be applied before carrying out a DPI as the last one is more CPU intensive. In this context, a Service Function Chain (SFC) is a list of network functions, that need to be applied to a flow in a particular order. These functions are carried out by specific hardware, which are installed at specific locations of the network. The paths followed by demands are thus very constrained, reducing the opportunities to aggregate traffic.

With the emergence of technics of Network Function Virtualization (NFV), the functions can now be executed by generic routers instead of dedicated equipments. Coupled with the Software Defined Network (SDN) paradigm, NFV brings a great flexibility to manage network flows. Indeed, with the centralized control allowed by SDN, the flow can be managed dynamically from end-to-end and the service functions can be installed only along paths for which and when they are necessary. These new paradigms thus bear the opportunity for energy savings in networks.

In this work, we explore the potential energy savings of using NFV for Service Function Chains. We consider the problem of reducing network energy consumption while placing service functions using generic hardware along the paths followed by flows. A specific difficulty is that the network functions can be repeated several time in the same chain and have to be executed in a specific order. In summary, the contributions of this work are -We show how virtualization can be used to improve the energy efficiency of networks, when demands have to go through a chain of services. To the best of our knowledge, we are the first to propose such a method.

-We propose a new way of modeling this problem based on Integer Linear Programming (ILP). The ILP can solve optimally instances of small sizes. We thus propose and validate a heuristic algorithm, GreenChains, to handle instances of larger sizes.

-This allows us to carry out extensive simulations on networks of different sizes. We study three different scenarios: a legacy scenario which serves as baseline for comparison, a hardware scenario in which the routing can be changed dynamically by a centralized SDN controller, but in which network functions are executed by specific hardware, and finally, an NFV scenario in which the network functions are virtualized and can be placed dynamically.

We show that between 30 to 55% of energy can be saved while respecting the constraints of the service chains.

-We additionally study the impact of the number of occurences of Virtual Network Functions (VNF) on bandwdith usage, path delay, and energy savings. We show that with only a small number of replicates near optimal results can be obtained.

The remainder of the paper is organized as follow. Related work is discussed in Section 1.1. The optimization problem and the ILP model are explained in Section 2, while the heuristic algorithm is described in Section 3. Numerical results are given in Section 4.

Related Work

Service Chains. Several works consider the problem of service function chain placement, but considering other metrics or other scenarios. [START_REF] Savi | Impact of processing costs on service chain placement in network functions virtualization[END_REF] proposes a different ILP model to solve problem studies the impact of the positions of chains on the processing costs. The authors of [START_REF] Gupta | Joint virtual network function placement and routing of traffic in operator networks[END_REF] explores the joint placement and routing of traffic in order to minimize the newtork bandwidth consumption. In [START_REF] Martini | Latency-aware composition of virtual functions in 5g[END_REF] is proposed a layered ILP close to the one we propose in the paper, but they optimize the latency. [START_REF] Mohammadkhan | Virtual function placement and traffic steering in flexible and dynamic software defined networks[END_REF] explores a problem of joint optimization of maximum link, CPU core and maximum delay in the network while placing the NVFs. Last, [START_REF] Riggio | Virtual network functions orchestration in wireless networks[END_REF] considers a cloud environment in which the load has to be load-balanced in order to minimize the computation and the communication overheads . However, these works do not consider the problem minimizing network energy consumption with a dynamic traffic.

Energy-Aware Routing. Several works have proposed algorithms to obtain energy aware routing, see e.g. [START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF][START_REF] Rouzic | Trend towards more energy-efficient optical networks[END_REF]. However, these works are hard to be put in practice as operators of legacy networks are reluctant to change their network configurations.

SDN and Network Energy Efficiency. Recently, researchers have started to explore how the introduction of the SDN paradigm with a centralized control and a live report of metrology data may allow to carry out dynamic routing. In particular, it would allow to implement energy-aware routing algorithms, as discussed in [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF]. However, these papers did not consider the constraints of network functions. Some particular works considered some specific class of network functions, like compression [START_REF] Giroire | Minimization of network power consumption with redundancy elimination[END_REF], but not the general problem of ensuring that flows are treated by the network functions.

Network Virtualization and Network Energy Efficiency. Only two papers explore the potential of network virtualization for energy efficiency In [START_REF] Bolla | Dropv2: energy efficiency through network function virtualization[END_REF], the author present an extension of an open source software framework, the Distributed Router Open Platform (DROP), to enable a novel distributed paradigm for NFV. DROP includes sophisticated power management mechanisms, which are exposed by means of the Green Abstraction Layer. In [START_REF] Mijumbi | On the energy efficiency prospects of network function virtualization[END_REF], authors estimate the energy savings that could result from the three main NFV use cases-Virtualized Evolved Packet Core, Virtualized Customer Premises Equipment and Virtualized Radio Access Network. However, both papers do not consider the constraints of service chains.

Model

Problem

We model our network as a bidirectional graph G = (V, A). A router is represented by a node. Each node u ∈ U has a capacity C u to handle network functions and which can represent its CPU, memory or storage (for simplicity, we consider here that the capacity of u is given by its number of cores). A link between two routers u and v consists in two directed arcs uv and vu in opposite directions. An arc uv has a capacity C uv .

The network operator has a set of demands D which need to be routed. A demand is a 4-tuple (s, t, D st , γ st ), where s is the source of the demand, t its destination, and D st the amount of flow which has to be routed from s to t. The demand has to pass through a chain of network functions among F, the set of the network NFVs. We note the chain γ st = f st 1 ...f st L st , with L st the chain length. A function f i can be more or less demanding for a node (e.g. it is more resource intensive to compress traffic, than to simply load balance it). To model it, we note ∆ f the fraction of cores used by function f per bandwidth unit. For different reasons (e.g. resiliency, privacy), two Inria different functions f i and f j may not be allowed to be installed in the same node. To model this, we define θ i , the set of anti-affinity functions that cannot be installed at the same location as f i .

The Energy Efficient Service Function Chain Placement Problem (EE-SFCP) problem consists in routing the set of demands D to minimize the network energy consumption, while respecting link and node capacities and constraints given by the set of chains γ st .

Power Model. Campaigns of measures of power consumption (see e.g. [START_REF] Chabarek | Power awareness in network design and routing[END_REF]) show that a network device consumes a large amount of its power as soon as it is switched on and that the energy consumption does not depend much of the load. Following this observation, On/Off power models have been proposed and studied. Later, researchers and hardware constructors have proposed more energy proportional hardware [START_REF] Niccolini | Building a power-proportional software router[END_REF]. To cover the different models for different hardware, we use a hybrid power model. Power of an active link:

pow uv + flow uv C uv pow uv
In our model, we considered that links can be put into sleep mode (by putting to sleep both corresponding interfaces). Note that the two links (uv and vu) between a pair of nodes are in the same state (active or in sleep mode) as there are sharing the same interface. But the routers themselves may not be put into sleep mode, as there are the sources or destinations of network traffic. However, cores may be put into sleep mode and the power used by nodes is given by

pow u × #cores
In the experiments, we consider that pow uv = pow uv = pow u .

A layered Model

We model the problem as an Integer Linear Program (ILP) using a layered model to express the orders between functions of the service chains. The model has L st + 1 layers. We note u(i) the copy of Node u in Layer i. The paths for the demand D st starts from node s(0) of layer 0 and ends in node t(L st ) of layer L st . Passing from layer i to layer i + 1 means that the i th function of the chain has been applied.

Notations

G = (V, A) F set of functions D set of Demands C uv capacity of link (u, v) γ st = f st 1 ...f

Formulation

Variables:

• x uv ∈ {0, 1} where x uv = 1 if link uv is active, 0 otherwise

• x fiu ∈ {0, 1} where x fiu = 1 of function f i is installed on node u, 0 otherwise • g st u(i)v(i) ∈ {0, 1} where g st u(i)v(i) = 1
if the flow for the demand st uses the link u(i)v(i), i.e., the link uv in layer i. We consider here unsplittable routing.

• k u ∈ N, #cores used in node u.

• f uv ∈ R, flow passing through link uv. This variable is linked and is added to the ILP for clarity of the presentation.

Objective

min (u,v)∈A (pow uv x uv + pow uv f uv C uv ) + u∈V pow u k u (1)
Flow Conservation

v∈N + (u) g st u(i)v(i) - v∈N -(u) g st v(i)u(i) + g st u(i)u(i+1) -g st u(i-1)u(i) =      1 if u(i) = s(0), -1 if u(i) = t(L st ), (s, t) ∈ D, u ∈ V, 0 else 0 ≤ i ≤ L st , f i ∈ F (2)
Link Capacity

f uv = (s,t)∈D L st i=0 D st g st u(i)v(i) (u, v) ∈ A f uv ≤ x uv C uv (u, v) ∈ A (3)
Function Activation

x f st i u ≥ g st u(i-1)u(i) , u ∈ V, (s, t) ∈ D, 1 ≤ i ≤ L st (4)
Anti-affinity rules

x fiu ≤ 1 -x fj u f i ∈ F, f j ∈ θ i , u ∈ V (5)
Number of cores used

(s,t)∈D l st i=1 ∆ f st i D st g st u(i-1)u(i) ≤ k u u ∈ V (6) Node Capacity k u ≤ C u u ∈ V (7)
For Equations (2), we set g st u(-1)u(0) = 0 and g st u(l st )u(l st +1) = 0. It allows to write the same set of equations for all the layers of the model. Note the link capacity constraints (3). If the link uv is into sleep mode, the sum of the flows forwarded through it must be null.

Inria 3 Solving large Instances with GreenChains

As the ILP proposed in the previous section cannot provide solutions for large networks, we propose here a heuristic algorithm called GreenChains to solve the EE-SFCP problem. The problem can be decomposed into three-subproblems.

-First, the routing problem is to compute a path for each demand, respecting the link capacity constraints.

-Second, the goal of the service chain placement problem is to find a placement of the NVF respecting the capacities of the nodes and the order defined by the service chains.

-Last, the energy saving problem tries to put into sleep mode as many links and cores as possible to decrease the energy consumption of the network.

Routing Module. The routing module is simple. The demands are considered one by one.

For each demand, we compute a weighted shortest path on a residual graph. The weight of a link is equal to the inverse of its residual capacity. This favors the link with lower load. The idea is to spread as much as possible the demands to find a feasible routing. To compute the residual graph, when the path is computed, we reduce the link capacities by the value of the demand. Furthermore, when considering a new demand to be routed, we remove links with a residual capacity smaller than the demand.

Service Chain Placement Module. When the paths for all demands are set, we place the service chains. We consider the different service chains separately. For a given chain, we consider the paths of all the demands with this chain. We then sort the nodes of the networks in the decreasing order of the number of such paths they are involved in. We then try to place all the functions of the chains on the nodes following this order. If it is possible in a node u, we place the functions. We then assign some of the paths to the cores of node u, till its capacity is full.

We then actualize the ordered list of nodes considering only the paths not yet assigned.

Energy Saving Module. The module tries to greedly put links into sleep mode. It starts with the graph G = (V, E). It first launches the routing module and then the service chain placement module. If they both succeed, it creates a list U of all links according to their usage (volume of traffic). It then chooses the less loaded link e min as a candidate to be put in sleep mode. It now considers the graph G = (V, E \ e min ). It launches again the routing and placement modules. If they succeed, e min is definitely put in sleep mode. The list U is actualized with the new routing, as well as the less loaded link. If at least one of the two modules fails, GreenChains considers that e min cannot be into sleep mode and the link is definitely kept active for the final solution.

The second element of U is then considered. The algorithm goes on till all links have been tried and set either as definitely in sleep mode or definitely active.

Results

In this section, we study the EE-SFCP for three networks with different sizes of the SNDLib [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF] library:

pdh with 11 nodes and 64 directed links, 440 demands.

atlanta with 15 nodes and 44 directed links, 840 demands.

germany with 50 nodes and 176 directed links, 9800 demands. We first validate the heuristic algorithm, GreenChains, by comparing its results to the optimal one found by the ILP proposed in Section 2. The ILP model can only solve small instances, we thus use GreenChains to solve larger instances. We then study the energy saved during the day for the three networks. The core of the experiments is to compare three scenarios presented below: a legacy scenario, a hardware scenario and an NFV scenario. We show that GreenChains succeeds in savings between 35% and 55% of the energy used in the legacy scenario.

Network Traffic Model. We used the traffic matrices provided by SNDLib for the different networks. For each demand, following [START_REF] Savi | Impact of processing costs on service chain placement in network functions virtualization[END_REF], we then divide it into four different categories of flows: video streaming, web services, voice over IP, and online gaming. As shown in Table 1, each category has a different rate of traffic and corresponds to a different proportion of the total traffic given by [START_REF] Index | Cisco visual networking index: Forecast and methodology 2015-2020[END_REF]. Furthermore, each category has to pass through a different chain of network functions given in the table. As an example, the video traffic has a rate of 4Mbps, represents 69.9% of the total traffic and has to go through, first, a Network Address Translator, then, a Firewall, a Traffic Monitor, a Video Optimizer Controller and, last, an Intrusion Detection Prevention System. For evolution of the traffic during time, we consider a typical daily traffic of France Telecom ISP link given in Figure 1. Traffic at night is about three times lower than during the day. It can be well approximated by considering only a small number of traffic levels. Indeed, an operator can achieve most of the possible energy savings by doing a small number of changes of its routing configurations during the day [START_REF] Araujo | Energy efficient content distribution[END_REF]. This is a great practical use as operators prefer to carry out as few as possible changes in order to minimize the chance of introducing errors or network instabilities. We thus consider 5 levels of traffic in the following.

Validation of the Heuristic Algorithm. We compare the results obtained by the heuristic algorithm, GreenChains, with the optimal results given by the integer linear program on a small network, pdh, with 11 nodes and 64 links. We consider instances with an increasing complexity: the number of demands varies from 4 to 40. Note that we consider multiple of 4 demands, as the traffic between a pair of nodes is divided into four differents demands corresponds to different categories of traffic. We compare the execution times of the ILP model and of the algorithm in Figure 2a. The experiments are made on a Intel(R) Xeon(R) CPU E5620 @2.40GHz 16 cores with 24GB of RAM. We see that the ILP model can be used to solve the problem with a reasonable time for a maximum number of 16 demands. In this case, it takes around 23 minutes to return the optimal solution. The increase is exponential: for 20 demands, the execution time is almost 3 hours. GreenChains, on the contrary, is a lot faster. It returns a solution in less than 1 second (0.7 s) for 20 demands. The increase is linear. It solves an instance with 40 demands in 1.35 s and the all-to-all instance (with 440 demands) considered in the following in less than 8 s. We see that it is impractable to use the ILP for large numbers of demands, and thus we use the GreenChains for the experiments on larger networks in the following. The results in terms of energy are given in Figure 2b. GreenChains finds results within a precision between 0.2% to 22% for the different number of demands. We consider this as good results given the difficulty of the EE-SFCP problem. Moreover, it means that the potential energy savings of using dynamic traffic and virtualization are in fact even greater than the one presented in the following.

Energy Savings during the day. We compare three scenarios in the experiments:

-Legacy scenario. This scenario corresponds to the one of a legacy network, whose operator does not try to reduce the energy consumption of its network. Its goal is to minimize the total bandwidth used while respecting the link capacity and the chain constraints. This scenario is used as a baseline for comparison for the energy-aware algorithms.

-Hardware scenario. The hardware scenario corresponds to the one of an SDN (non virtualized) networks in which an operator tries to reduce its energy consumption by adapting the routing to the demands. In this scenario, the network functions are carried out by some specific hardware placed at given positions in the network.

-NFV scenario. The NFV scenario is the one of a virtualized SDN network in which generic hardware nodes can execute any virtual network functions. This is the scenario solved by the ILP presented in Section 2

Results for the three networks are given in Figure 3. The baseline energy consumption of 100 corresponds to the maximum energy used in the legacy scenario.

First, we observe that, even if the goal in the baseline scenario is not to reduce the energy consumption but to minimize the total bandwidth usage, the energy used varies and is smaller at night for all networks. The explanation is that we used a mixed power model for which energy consumption depends for a part to the level of traffic which goes through the network links. Thus, during the night, even if no equipments (links or cores) is put into sleep mode, the energy used is smaller than during the day in which the traffic is higher. The variation is between 10 to almost 20% for the three networks considered.

We then focus on the energy which can be saved in the hardware scenario by trying to aggregate the traffic towards a small number of links and cores, while respecting the constraints given by the service chains and the capacities. The savings are between 15% and 27%, e.g. 22% at noon for germany. The savings are here limited by the service chains: the flexibility for the choices of paths is limited in this scenario, as the network functions are executed by harware located at fixed positions in the network.

The savings are a lot higher in the nfv scenario: between 30 to 55%. There are, for example, 50% at 6am and 30% at noon for atlanta, and always 50% or more for tt pdh. The explanation is that the possibility to set VNF dynamically provides a larger flexibility to the algorithm to set the paths for the demands, leading to better aggregation, and thus energy savings. We also observe a surprising phenomena in the results, which is best seen in Figure 4, when plotting the data of Figure 4c in terms of savings. The germany network is chosen as an example. The savings (compared to the legacy scenario) are almost constant during the day. They oscillate between 27% at 6 am to 22% at noon. The intuition would be that the savings are a lot larger during the night as the traffic is a lot lower, see Figure 1. Even more surprising, the savings in the nfv scenario for germany are lower during the night than during the day: 33% at 2am and 39% at noon. The explanation of this phenomenon is that, as we discuss it above, the energy consumption of the legacy scenario also decreases at night. The ratio harware/legacy or nfv/legacy scenario stays close to constant.

NFV occurrences. We look at the impact of the number of occurrences of the functions in the network on main metrics. We choose an instance, that we can solve using the ILP, the pdh network with 16 demands. This way, we can easily add constraints on the number of function occurrences in the model. We show in Figure 5 usage (a), (b) path delay, and (c) energy savings. We see that, when number of nodes executing the same function is low, the bandwidth usage and the path delay is very high. As a matter of fact, the paths of the demands have to go through these nodes, which may be far away from a shortest path in the network. These results further explain the better efficiency of the NFV scenario over the hardware scenario. With virtualization, the cost to deploy several occurrences of a network function is low in comparison to the hardware scenario in which some specific hardware has to be installed. However, we see that the bandwdith and the average delay decrease quickly, when the number of occurrences of a function increases. This is an important result, as it shows that the energy savings using NFV can be obtained without installing a large number of NFV. In the case of phd which we take as example, we obtain almost optimal results in terms of bandwidth, delay, and energy savings with a maximum of 4 replicates per function.

Conclusion

In this work, we model the problem of minimizing the energy consumption of a network in which flows have to go through a chain of network functions. We propose an Integer Linear Program to solve the problem on small networks and an efficient heuristic algorithm to solve it on larger instances. We first show the impact of SDN technologies allowing dynamic routing on the energy consumption of the network. We obtain savings of around 20%. We then show that the energy savings may be largely increased by using network function virtualization. Indeed, being able to choose dynamically the position of the virtualized functions leads to further savings between 30 and 55% for different networks.

Inria

Figure 1 :

 1 Figure 1: Multi-period approximation of the trace of the typical daily traffic of a link of France Telecom network.

  Execution time (log scale).

Figure 2 :

 2 Figure 2: Comparison of the performances of the heuristic algorithm, GreenChains, vs. the ILP for the pdh network.

Figure 3 :

 3 Figure 3: Energy used during the day for the legacy, hardware and NFV scenarios (The baseline 100 corresponds to the maximum energy used in the legacy scenario).

  results for this instance about (a) bandwidth

Figure 4 :

 4 Figure 4: Energy savings (compared to the legacy scenario) during the day

Figure 5 :

 5 Figure 5: Impact of the maximum number of network function occurrences (bottom).

RR n°8979

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

* A. Tomassilli, N. Huin, and F. Giroire have been partially supported by ANR program ANR-11-LABX-0031-01 and Mitacs. † B. Jaumard was supported by a Concordia University Research Chair (Tier I) and by an NSERC (Natural Sciences and Engineering Research Council of Canada) grant.


Pierre-François Marteau

Assessing pattern recognition or labeling in streams of temporal data

In the data deluge context, pattern recognition or labeling in streams is becoming quite an essential and pressing task as data flows inside always bigger streams. The assessment of such tasks is not so easy when dealing with temporal data, namely patterns that have a duration (a beginning and an end time-stamp). This paper details an approach based on an editing distance to first align a sequence of labeled temporal segments with a ground truth sequence, and then, by back-tracing an optimal alignment path, to provide a confusion matrix at the label level. From this confusion matrix, standard evaluation measures can easily be derived as well as other measures such as the "latency" that can be quite important in (early) pattern detection applications.

Introduction

In the big data and Internet of things era, data is widely generated through streams at an increasing rate. Such data is provided by sensor applications, measured in network monitoring and traffic management system, available as log records or click-streams in web exploration, sequence of email, blogs data, RSS feeds, social networks, and so many other sources. Applications requiring pattern recognition in such streams is becoming more and more demanding, and, consequently, the question of assessing such applications is particularly essential. Among various type of stream data we are focusing on stream of temporal data, also called timestamped data stream, for which data elements (samples) are associated with a time index. The aim of this paper is, given a ground truth sequence of time-stamped labeled segments, to propose a consolidated and extended assessment framework for pattern labeling or recognition in streams. We consider in this paper that the ground truth sequence is given as a sequence of time-stamped labels, each label being characterized by a begin and an end time-stamp, as depicted in figure 1. It should be stressed that, to ensure as much as possible the independence of the assessment framework to the nature of the stream, such sequence does not keep any reference to the data that are conveyed by the stream except for the time location of the labeled segments.

The output of the pattern recognition or labeling tasks in stream that we intend to assess are expected to provide the same kind of sequences. The proposed algorithm will output -a confusion matrix from which traditional assessment measures such as precision, recall or F-measures can be derived, -an estimation of the recognition latency that can be an issue for real-time application, -an estimation of the average relative duration of the matched labeled segments, that can be of some utility when assessing labeling tasks.

The contribution of this paper is the presentation of a dynamic programming algorithm dedicated to the alignment of such sequences. We insists that it is not one another stream segmentation or labeling method, but a proposal for the assessment of stream segmentation or labeling methods when time occurrence of the labels is a critical issue. The requirement for a ground-truth sequence is a strong constraint that indeed limit the application of the proposed assessment framework, but ensures in general a better acceptance and quality of the assessment since experts are supposedly maintained into the process.

Previous work and problem statement

Stream classification or labeling refers essentially to three distinct tasks [START_REF] Graves | Supervised sequence labelling with recurrent neural networks[END_REF] [START_REF] Graves | Supervised Sequence Labelling with Recurrent Neural Networks[END_REF] -stream classification: the task consists in affecting a class label to a given stream. For instance, categorizing a RSS feed into some pre-defined categories such as sport, economy, society, culture, etc, is typically a stream classification problem. -stream segment classification: here we consider that the streams are segmented (the segments are known), and the task consists in affecting a class label to each segment. Considering a general RSS feed, naturally segmented into time-stamped news items, the task is to affect to each news item a class label (e.g. sport, economy, society, etc.). -pattern spotting and recognition in streams: here again we consider that the stream is also segmented but the segments are only known for training through manual segmentation and labeling. Hence the segments need to be localized along the time axis, with a beginning and an end time-stamps. This is the case for example when addressing human data such as speech data which can be segmented into phonemes, syllables, words, or any other acoustic or linguistic parts. This tasks is also referred to as temporal classification [START_REF] Waleed | Temporal Classification: Extending the Classification Paradigm to Multivariate Time Series[END_REF].

This paper addresses the assessment of approaches that tackle the third task, obviously the most difficult one since it requires to identify segment frontiers and segment classification as a whole. Formally, such approaches will typically output a sequence of labeled time-stamped segments (SLTSS).

Let L be the set of labels, and T a time segment. A labeled-segment s will be defined as a triplet (l, t b , t e ) ∈ L × T × T with the constraint that t b ≤ t e . A sequence of labeled time-stamped segments S will be denoted as

S = s 1 s 2 • • • s n = (l i , t bi , t ei ) i=1•••n . We will note S(i) the ith labeled segment in the sequence S.
Furthermore, we impose an ordering of the segments inside the sequence, such that: ∀i, t bi ≤ t bi+1 and t ei ≤ t ei+1 . From this definition, it should be noted that segments may have different lengths and successive segments can be partially overlapping or disjoint.

The problem of assessing pattern spotting and recognition systems in streams comes down to the alignment of a predicted SLTSS with a ground-truth SLTSS, with the constraint that only time overlapping segment can be matched.

If we were dealing uniquely with sequences of symbolic labels, an edit distance, such as the Levensthein [START_REF] Iosifovich | Binary codes capable of correcting deletions, insertions and reversals[END_REF] or the Smith and Waterman distance [START_REF] Smith | Identification of common molecular subsequences[END_REF] proposed in bioinformatics among others, would be perfectly adapted and has been used for various tasks in bioinformatics, natural language processing, etc, [START_REF] Graves | Supervised Sequence Labelling with Recurrent Neural Networks[END_REF]. However, the time-stamps that delimit the temporal segments introduce a kind of fuzziness in the matching of segments that need to be coped with. It is quite striking that, to our knowledge, no dynamic programming algorithm has been yet proposed to solve this temporal alignment problem at a labeled segment level (straightforwards techniques at frame or sample levels are usually used). Although edit distance based measures have been design to cope with temporal segment sequences such as the time warp edit distance (TWED) [START_REF] Marteau | Time warp edit distance with stiffness adjustment for time series matching[END_REF], these measures does not cope with the label attached to the temporal segments. But more importantly, they are not suited for the alignment of SLTSS we are dealing with, mainly because they enable the alignment of disjoint time segments which has no meaning in our context. The purpose of the temporal alignment algorithm that we detail hereinafter intends to bridge this apparent gap.

Dynamic programming algorithm for the alignment of a pair of SLTSS

Following the mathematical definition of the Levenshtein edit distance designed to align two strings we define δ SLT SS as an edit distance allowing to align two SLTSS S 1 , S 2 (of length

|S 1 | and |S 2 | respectively) is given by δ SLTSS (S 1 (|S 1 |), S 2 (|S 2 |))
where

δ SLTSS (S 1 (i), S 2 (j)) =                C 0 . max(i, j) if min(i, j) = 0, min      δ SLTSS (S 1 (i -1), S 2 (j)) + C 0 δ SLTSS (S 1 (i), S 2 (j -1)) + C 0 δ SLTSS (S 1 (i -1), S 2 (j -1)) + C m (S 1 (i), S 2 (j)) otherwise. ( 1
)
where δ SLTSS (S 1 (i), S 2 (j)) is the distance between the first i segments of S 1 and the first j segments of S 2 , C 0 > 0 is a constant penalty value corresponding to a segment insertion or deletion and C m (S 1 (i), S 2 (j)) ≥ 0 is the local cost associated to the correct matching of segment S 1 (i) with segment S 2 (j) or a substitution of the first segment by the second.

Notice that, similarly to the edit distance, but contrary to the DTW measure [START_REF] Vintsyuk | Speech discrimination by dynamic programming[END_REF], alignment of one segment with several other (multiple matching of one segment) is not possible. The fact that streams can be partially labeled, meaning that labeled segments can be possibly not contiguous (they can be overlapping but also separated by "blank" or "unlabeled" segments), introduces some difficulty. One way to deal with such kind of stream is to introduce a dedicated label NL (for no label) to make the labeling covering the whole time axis. An example of the SLTSS we are working with is given in Figure 2. By convention, a NL segment starts at the end of the previous (disjoint) segment and end at the beginning of the following (disjoint) segment. The main difference with the Levenstein's distance is the local matching cost that is defined for δ SLT SS as: max(te i ,te j )-min(t b i ,t b j ) otherwise (correct match) (2) Basically, the local matching cost is evaluated according to the following cases:

C m (S 1 (i), S 2 (j)) =                          ∞ if
-it is infinite if the segments do not overlap or if the labels are distinct with one being equal to NL (we prohibit the matching of non overlapping segments or NL labeled segments with non NL labeled segments), -it equals C 0 if labels are different and distinct to NL, -otherwise it reduces to 1.0 minus the degree of overlapping of the two segments. Hence, if the two segments are equal (fully overlapping), the cost is null, and if the segments share a single sample, then the cost is 1.0. Figure 3 shows an example of a partial matching with an overlap that will produce a matching cost verifying 0 < C m < 1.0. The ∞ cost penalty prohibits the matching of non overlapping segments or segments that are differently labeled. Hence, the substitution operation (switching a label by another) is only allowed if the segments overlap, with a cost of C 0 .

To favor the matching operation over the substitution, insertion and deletion operations, the local penalty cost C 0 is set up to 2.0, the double of the matching cost with overlap worse case.

In addition, the average latency estimation (LAT) and the average match duration (DUR) can be estimated. When a match is detected, the latency and the duration measures of the matched segments are defined accordingly to Figure 3. The latency is defined as the difference of the matched mid-segment time locations, while the match duration is the length of the overlap between the two matched segments.

The evaluation of the errors is performed by back-tracing the best path provided by the recursive equation 2. This process is a bit tricky in the presence of repetitions or multiple errors. Repetitions as exemplified in figure 4 and possibly multiple errors such as the double errors depicted in figure 5 will produce false positive (FP) and false negative (FN) errors. More precisely one of the repetitions will correspond to a correct match operation while the other occurrences of the repetition will correspond to a deletion (or insertion) operation and will be accounted for FP errors. Similarly, in the presence of multiple errors on a set of overlapping segments, one of the error will be accounted for 1 FN and 1 FP (substitution), while the other errors will be accounted for 1 FP error each. For instance, in figure ??, the first error will account for 1 FN and 1 FP (substitution A -¿ B), the second error will account for 1 FP.

The implementation of δ SLT SS is described in a simplified form in Algorithm 1, which is decomposed in three blocks depicted in Algorithms 2, 3 and 4 1 . Following are the conventions used to described these algorithms:

-the vector or matrix indexes start from 0: basically the first element of a vector V is located at V [0]. The same applies for matrix elements. -If L = {l 1 , l 2 , ..., l |L| } is the set of labels (with N L / ∈ L), l i will correspond to the i th row or column of the confusion matrix (referred to as CM in the algorithms). idx(l) = i > 0 will correspond to the index of label l in the CF matrix (idx(l i ) = i).

-row and column at index 0 in the CM matrix will correspond to N L (no label).

Algorithm 1 returns a confusion matrix (obtained by back-tracing the best alignment provided by the dynamic programming algorithm), the number of repetitions, the average match duration DU R, the average match latency LAT . From this confusion matrix it is easy to evaluate assessment measures such as : Algorithm 1 δ SLT SS : alignment of a ground-truth (S 1 ) and a predicted (S 2 ) labeled segment sequences Integer match count = 0; 5:

for i = 0 to |S1| do D[i][0] = i • C0; ⊲ D initialization 6: for j = 0 to |S2| do D[0][j] = j • C0; 7:
//D Calculation 8:

for i = 1 to |S1| do 9:

for j = 1 to |S2| do 10: while i > 0 and j > 0 do 17: LAT = LAT + latency(S1(i), S2(j); 5: CF [idx(l1(i))][idx(l1(i))] + +; ⊲ idx(l1(i)) is the raw or column index for l1(i)

D[i][j] = min{D[i -1][j] + C0; 11: D[i][j -1] + C0; 12: D[i -1][j -1] + Cm(S1(i), S2 (
m = min(D[i -1][j], D[i][j -1], D[i -1][j -1]); 18: switch(m) 19: case (D[i -1][j - 1
6: i = i -1, j = j -1; Algorithm 3 DELETE1 BLOCK 1: if S1(j) = N L then ⊲ false negative error 2: CF [0][idx(l2(j))] + +; 3: else NL deletion in GT 4: j = j -1; -Micro Average Accuracy (MAA): 1/|L| |L| i=1 (T P i + T N i )/(T P i + F P i + T N i + F N i ), Algorithm 4 DELETE2 BLOCK 1: if S2(j) = N L

Example

Table 1 presents a simple example based on a pair of short sequences. The set of admissible labels is L = {1, 2, 3, 4, 5}. NL is the "no label" extra label. Table 2 present the back-trace process output along a best alignment path. Finally, table 3 gives the confusion matrix provided by the backtracking. Clearly, if we except the NL label, three correct matches have been detected, 1 label of the ground truth has not been predicted (label 3), which results in a false negative error, 1 mismatch (substitution) has been detected between labels 2 (GT) and 4 (PRED) and 1 prediction has led to a false positive error (label 5 has been repeated in the predicted sequence). The "best" alignment provided by the algorithm is given in Figure 6 Table 1 On this example, the mean latency and mean duration have been respectively evaluated to 9.16 and 35 time units.

The choice of the local alignment costs has been made to favor correct label matches and to penalize mismatched labels.

This algorithm provides a confusion matrix from which standard evaluation measures can be easily derived. Furthermore, it evaluates the average latency and the relative average duration of the correct matches, which can be useful to "rank" applications that require pattern spotting and recognition (e.g. speech or gesture recognition applications) as soon as possible, or a precise temporal location of the labels.

This algorithm requires a ground-truth sequence in input, which is indeed a limitation to its use. In the other hand, since experts are generally involved in the construction of the ground-truth, it ensures a human control of the quality of the assessment procedure and possibly a better acceptance.

Fig. 1 .

 1 Fig. 1. Example of a ground truth sequence.

Fig. 2 .

 2 Fig. 2. An SLTSS example with contiguous, overlapping and disjoint segments.

Fig. 3 .

 3 Fig. 3. situation involving a ground truth A labeled segment aligned with a predicted A labeled segment.

Fig. 4 .

 4 Fig. 4. Repetition of a matching label A. NL stands for no label.

Fig. 5 .

 5 Fig. 5. Double errors situation (A v.s. BB). NL stands for no label.

1 :

 1 procedure δSLT SS (S1, S2) 2: Double D[|S1| + 1][|S2| + 1]; ⊲ the distance matrix 3: Integer CF [|L| + 1][|L| + 1] = Zeros(|L| + 1, |L| + 1); ⊲ the confusion matrix 4:

  j))}; 13: //BACK-TRACE 14: i = |S1|, j = |S2|; 15: REP = 0, DU R = 0, LAT = 0; 16:

then ⊲ false positive error 2 :

 2 CF [idx(l1(i))][0] + +; 3: else NL deletion in PRED 4: i = i -1; -the Micro Average Precision (MAP): 1/|L| |L| i=1 T P i /(T P i + F P i ), -the Micro Average Recall (MAR): 1/|L| |L| i=1 T P i /(T P i + F N i ), -Micro Average F1 (MAF1): MAF1 = 2.MAP.MAR/(MAP+MAR). The algorithmic complexity of δ SLT SS is clearly O(|S 1 |.|S 2 |), or simply O(N 2 ) for sequences of length N .

  time intervals [t bi ; t ei ] and [t bj ; t ej ] are disjoint, ∞ if l i = l j and (l i = NL or l j = NL) and [t bi ; t ei ] and [t bj ; t ej ] overlap (false positive or false negative), C 0 if l i = l j and l i = NL and l j = NL and [t bi ; t ei ] and [t bj ; t ej ] overlap (substitution),

	1.0 -

min(te i ,te j )-max(t b i ,t b j )

  . Ground-truth sequence (left) and predicted sequence (right)

		index Label t b te
		0	NL 0 30
	index Label t b te 0 3 0 45 1 NL 46 50 2 5 51 101 3 2 102 152 4 4 153 203 5 1 204 254	1 2 3 4 5 6 7 8	NL 31 50 NL 51 88 5 89 90 NL 91 95 5 96 106 2 107 152 NL 153 174 2 175 195
		9	NL 196 203
		10	1	204 254

The code will be made available for the community at the earliest feasible opportunity

GT stands for ground-truth and PR for predicted GT/PR NL 1 2 3 4 5 NL 1 0 0 1 0 0 1 0 1 0 0 0 0 2 0 0 1 0 1 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 5 1 0 0 0 0 1 Fig. 6. Alignment provided by the algorithm for the pair of SLTSS used in the example.

In red/bold the mismatch, in orange/bold the insertion/deletion, in green the correct matches.

Conclusions

The assessment of temporal pattern labeling or recognition tasks in streams is not trivial. It requires to align sequences of labeled time-stamped segments that either partially overlap or are disjoint. We have proposed to use an editing distance to find first an optimal alignment (basically an alignment with a minimal cost) dedicated to this specific alignment problem. Following backward this optimal alignment allows for the inventory of the various kind of mismatch (substitutions, false positive or false negative) errors as well as the correct matches.