Jean-Christophe Aval

Adrien Boussicault

Sandrine Dasse-Hartaut

Dyck Tableaux

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The starting point of this work is the discovery of a new and direct construction that relies bijectively the permutations of length n to some weighted Dyck paths named subdivided Laguerre histories. These objects correspond to the combinatorial interpretation of the development of the generating function for factorial numbers in terms of a Stieltjes continued 1 The first two authors are supported by the ANR (PSYCO project) 2 The third author is supported by the ANR (IComb project) fraction [START_REF] Xg | Une théorie combinatoire des polynômes orthogonaux[END_REF]. Such a bijection has been given by de Medicis and Viennot [START_REF] De Medicis | Moments de polynômes de q-Laguerre et la bijection de Foata-Zeilberger[END_REF] but their construction is indirect in the sense that it decomposes a permutation in two involutions, then goes through the construction and the fusion of two Hermite histories.

Another interest of our construction is that it gives a link between subdivided Laguerre histories and tree-like tableaux [START_REF] Aval | Tree-like tableaux[END_REF], which are a new presentation of permutation tableaux [START_REF] Postnikov | Total positivity, Grassmannians, and networks[END_REF][START_REF] Steigrímsson | Permutation tableaux and permutation patterns[END_REF] or alternative tableaux [START_REF] Xg | Alternative tableaux, permutations and partially asymmetric exclusion process[END_REF]. The link lies in the insertion algorithm used on both classes of objects and whose key ingredient is the notion of ribbon. For this reason, the central objects of this paper are tableaux called Dyck tableaux whose natural reading in terms of words gives subdivided Laguerre histories. Although the original construction is not recursive, we are able to easily describe relevant statistics (generalized patterns, shape, (RL/LR)-(minima/maxima)) because of the recursive structure given by the insertion procedure.

When talking about relevant statistics, we have in mind the long-term challenging motivation of this work: build new objects in order to give a new, and if possible simpler, interpretation of the statistics introduced by Corteel and Williams [START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials[END_REF] which describe the stationary state of the physical model named PASEP. The Partially Asymmetric Simple Exclusion Process is a model in which N sites on a one-dimensional lattice are either empty or occupied by a single particle. These particles may hop to the left or to the right with fixed probalities, which defines a Markov chain on the 2 N states of the model. The explicit description of the stationary probability of the PASEP was obtained through the Matrix-Ansatz [START_REF] Derrida | Exact solution of a 1D asymmetrix exclusion model using a matrix formulation[END_REF]. Since then, the links between specializations of this model and combinatorics have been the subject of an important research (see for example [START_REF] Duchi | A combinatorial approach to jumping particles[END_REF][START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process[END_REF][START_REF] Corteel | Bijections for permutation tableaux[END_REF][START_REF] Josuat-Vergès | Combinatorics of the three-parameter PASEP partition function[END_REF]). A great achievment is the description of the stationary distribution of the most general PASEP model through statistics defined on combinatorial objects called staircase tableaux [START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials[END_REF]. Although this result gives an explicit solution, it would be valuable to give another, and simpler interpretation.

This paper is divided into eight sections. The first one is devoted to the definition of Dyck tableaux, together with their word reading. In Section 2, we present the insertion algorithm which gives Dyck tableaux their nice recursive structure. Section 3 presents the direct bijection between Dyck tableaux and permutations. Section 4 studies some generalized permutation patterns. The bijection with tree-like tableaux is presented in Section 5. The next two sections deal with relevant parameters of Dyck tableaux: their shape in Section 6, and (RL/LR)-(minima/maxima) in Section 7. To conclude, the last section points out open questions.

Dyck tableaux

We shall call staircase partition of size n the partition E n = (n, n -1, . . . , 1). As usual, a partition is represented by a Ferrers diagram and Figure 1 illustrates the convention that we choose to draw such diagrams. The set of Dyck paths of size n may be defined as

D n = {E n /µ | µ ⊂ E n-1 }
where / denotes the suppression of a partition box by box. Figure 2 shows the set of the 5 Dyck paths of size 3. It is more convenient for our purpose to use diagrams, but of course, the lower border of such a diagram π is an "usual" Dyck paths. Moreover, when reading on the border of π (from left to right) a D letter for a step going down, and an U letter for a step going up, we bijectively get Dyck words. For example, the Dyck word associated to the second Dyck path π on Figure 2 is D D U U D U . In a Dyck path π of size n, the set of n boxes placed at the top is called its first floor. This notion is illustrated by Figure 3. The number of boxes in a given column is called its height; for example, the column 2 on Figure 4 is of height 2. Now we may define the central objects in our work. A Dyck tableau is a Dyck path whose columns contain each exactly one dot (dotted box). The size of a Dyck tableau is its number of dots, which coincides with the size of its underlying Dyck path. Figure 5 is an example of Dyck tableau of size 6 and Figure 6 presents all the Dyck tableaux of size 3. The height of a dot in a Dyck tableau is defined as the number of empty boxes above it in the same column. For example, on Figure 5, the dot in column 2 (resp. 3) is at height 0 (resp. 1). We need to define the basement of size n as the diagram:

S n = E n /E n-1 .
This notion is illustrated on Figure 7. We shall now represent Dyck paths and Dyck tableaux of size n with a basement S n+1 whose boxes are colored in black, as shown on Figure 8.

⊲ for each position i, w(i) ∈ N =⇒ w(i) < ch(i, w)
where ch(i, w) is the column height defined by

ch(i, w) := |{j < i|w(j) = D}| -|{j < i|w(j) = U }| 2 .
The integer entries of a weighted Dyck word are called its weights. The same notion of weighted paths appears in [START_REF] De Medicis | Moments de polynômes de q-Laguerre et la bijection de Foata-Zeilberger[END_REF] under the name subdivided Laguerre histories. It should be clear that Dyck tableaux and weighted Dyck paths are two representations of the same object, as illustrated on Figure 9: to get a word from a Dyck tableau, one has to read the tableau (with its basement) from left to right and to write:

Insertion procedure

The insertion procedure is the way to insert a dotted box inside a Dyck tableau, thus giving to the set of Dyck tableaux a nice recursive structure. In this section we define this insertion procedure and we present a generation tree for Dyck tableaux. The insertion procedure uses two main operations: column addition and ribbon addition. Let us describe these two operations.

Let T be a Dyck tableau and w its reading as a weighted Dyck word. We call column addition in w the substitution -→ DmU where m = ch(i, w) -1 and i is the position of the substituted letter in w. For example, a column addition at the third letter in the word

D0D D1D U 0U U 0D U 0U
gives the following word: Proof. Let w = w 1 w 2 be a weighted Dyck word and w ′ = w 1 DmU w 2 be the result of a column insertion in w. Let i be the position of m in w ′ . Let L be the language ( (U + D)N(U + D)) * . Let us check that w ′ verifies the 3 properties defining weighted Dyck words:

D0D D1D D2U U 0U U 0D U 0U .
D0D D1D U 0U U 0D U 0U split ---→ D0D D1D U 0U U 0D U 0U join ---→ D0D D1D U 0U U 0D U 0U addition of ----------→ a dotted box D0D D1D D2U U 0U U 0D U 0U
⊲ If w 1 w 2 ∈ L, then, by a recursion argument, we get that w 1 ∈ L and that w 2 ∈ L. Hence, w 1 DmU w 2 ∈ L.

⊲ The insertion of DU in a Dyck word does not change its nature. Hence, the subword in U and D letters of w ′ is a Dyck word.

⊲ The insertion of DU does not modify the weight and the height of the existing columns. Moreover, the new weight is such that m < ch(i, w) because m = ch(i, w) -1.

It is clear that the size of a weighted Dyck path is increased by 1 in a column addition.

Let w be a weighted Dyck word. The ribbon addition on the subword U D in w is the operation exchanging the two letters D and U of the subword in w.

For example, the word

D0D D1U U 0D U 0U D0D U 0U D0U
has a subword U D with a U letter in the 8-th position and a D letter in the 26-th position. If we add a ribbon between these two letters, we obtain the word : Hence, the new word verifies all the conditions to be a weighted Dyck word.

D0D D1D U 0D U 0U D0D U 0U U0U .
D0D D1U U 0D U 0U D0D U 0U D0U -→ D0D D1D U 0D U 0U D0D U 0U U0U
Before defining the insertion procedure, we need to define the special box of a Dyck tableau. In a Dyck tableau, an eligible box is a dotted box with no box to its South-West. The special box is the right-most eligible box. Figure 12 gives an example of special box. Proof. A weighted Dyck word of size k ≥ 1 has at least one weight. Its first three letters are always : D0 and the height of the first column is 1. We deduce that the first weight is a eligible. The uniqueness is obvious.

special box

We are now ready to present the insertion procedure. The insertion procedure is an algorithm to insert (in an invertible way) a dotted box (and therefore a column) in a Dyck tableau. This procedure is composed of four steps: Step 1 is correct because there is always a special weight in a weighted Dyck word (Proposition 3). By definition, a weighted Dyck word has at least one letter, whence step 2 is valid, and step 3 can be performed. Thanks to Proposition 1, the result of step 3 is a weighted Dyck word of size n + 1.

From the column addition, we know that the letter following the new weight is a U , and from the definition of the special weight, we know that the letter preceding of s is a D. Now, if the new weight is on the left of s, we get a subword U D on which we can add a ribbon. We deduce that step 4 is well defined.

Because of Proposition 2, we conclude that the output of the algorithm is a weighted Dyck word of size n + 1.

The next proposition is a key ingredient. Proposition 4. At the end of the insertion procedure, the new weight becomes the special weight.

Proof. Let w be a Dyck word. We may write w = w 1 sw 2 , with w 1 and w 2 two words and s the special weight of w. Let w ′ be the result of the insertion procedure applied to w. Step 3 consists in a column addition. When we add a column, we substitute a letter in w by the word DmU where m = ch(i, w) -1 is the new weight. The new weight is maximal and have a D letter to its left. Thus the new weight m is eligible.

We want to prove now that m is the right-most eligible weight. Two cases have to be considered:

1) m is to the right of s: as s is the special weight in w, there is no eligible weight to its right, whence no eligible weight to the right of m;

2) m is to the left of s: a ribbon is added between m and s at step 4. Columns between m and s have their height increased by 1 and their weight unchanged. Hence, all the weights between m and s are not maximal. As s is the special weight in w, the weights placed to its right are not eligible. We deduce that there is no eligible weight to the right of m.

We conclude that m is the special weight.

This insertion would be of no use if it could not be inversed. We shall now describe the inverse insertion procedure, which consists in three steps: Inverse insertion procedure validity. Let w be a weighted Dyck word of size k ≥ 1. We will now justify the three steps of the algorithm:

1)
Step 1 is correct because there is always a special weight in w (Proposition 3).

2) We may suppose that the the letter following s is D, since the other case is trivial. We check successively: that we can perform step 2 and that it gives a weighted Dyck word of size k.

i) To perform step 2, we need to find the first maximal weight m placed to the right of s. This weight exists since the rightmost weight of a weighted Dyck word is always maximal and can not be special (the letter just to its right is a U ). The letter preceding m is a U : otherwise m would be an eligible weight placed to the right of s. Thus we can apply step 2. ii) By performing step 2, we permute the letters D and U to obtain a new word w ′ . Let i and j be the position of s and m in w. We know that m is the leftmost maximal weight placed to the right of s. We deduce that

∀k ∈]i, j[, w(k) ∈ N ⇒ w(k) ≤ ch(k, w) -2.
When we permute the letters D and U , we decrease by 1 the height of all the columns placed between s and m. Thus, the new word w ′ has the following properties: ⊲ the weights between s and m are strictly smaller than the height of their columns; ⊲ the subword in U and D of w ′ is a Dyck word. We deduce that the result of step 2 is a weighted Dyck word w ′ of size k.

3) By definition of the special weight, the letter preceding s in w (thus in w ′ ) is a D. In the two cases of step 2, the letter following s in w ′ is a U . We deduce that DsU is a factor of w ′ . We can perform step 3 and substitute the factor DsU by a letter to get a word w ′′ . This substitution does not modify the height or the weight of the columns. Moreover, deleting a factor DU in a Dyck word gives another Dyck word. We can conclude that w ′′ is a weighted Dyck word of size k -1.

Proposition 5. The inverse insertion procedure is the inverse of the insertion procedure.

Proof. Let w be a weighted Dyck word and p a letter of w. We denote by w ′ the result of the insertion procedure applied to letter p in w. We want to check that the inverse insertion procedure appied to w ′ gives back w. Two cases have to be distinguished, according to the place of s, the special weight of w:

Case 1: p is to the left of s.

In this case, we may write w = w 1 pw 2 Dsw 3 , with w 1 , w 2 and w 3 factors of w. Thus w ′ = w 1 DmD w 2 U sw 3 where m is the inserted weight. We now apply the inverse insertion procedure to w ′ . Thanks to Proposition 4, the special weight of w ′ is m.

Since there is a D following m, we have to perform step 2 and remove a ribbon. To do this, we first search for the leftmost maximal weight placed to the right of m. This maximal weight is s: indeed, by permuting U and D during the insertion procedure, we have increased the height of all the columns between m and s and leave their weight unchanged. By removing the ribbon, we get the word w 1 DmU w 2 Dsw 3 . At step 3, we replace the factor DmU by a letter. We finally get w 1 w 2 Dsw 3 which is precisely w.

Case 2: p is to the right of s.

In this case, we may write w = w 1 sw 2 pw 3 , with w 1 , w 2 and w 3 factors of w. We get w ′ = w 1 sw 2 DmU w 3 where m is the inserted weight. We now apply the inverse insertion procedure to w ′ . Using Proposition 4, we select the weight m at step 1. At step 2, there is nothing to do, because the letter following m is a U . At step 3 we replace the factor DmU by a letter . We finally get w 1 sw 2 w 3 which is precisely w.

If we apply the inverse insertion procedure to a weighted Dyck word w of size n, we get a Dyck path w ′ of size n -1 and an integer 0 ≤ k ≤ n -1 (the place of the special weight of w). We prove in a similar way that if we apply the insertion procedure to w ′ at place k, we get back w.

Proposition 6. Every weighted Dyck word w may be constructed from (the word of size 0), recursively using the insertion procedure.

Proof. We shall prove the result by induction on the size of w. It is obvious if the size is 0, and we assume it holds up to size k. Let w be a weighted Dyck word of size k + 1. If we use the inverse insertion procedure on w, we obtain a weighted Dyck word w ′ of size k. By induction, we know that w ′ may be obtained from the word using the insertion procedure. Thanks to Proposition 5, w can be constructed by applying the insertion algorithm to w ′ .

The generation tree for Dyck tableaux of size at most 3 is shown on Figure 15. In this tree, an arrow of label i links a tableau T to a tableau T ′ obtained by inserting a dot in the i-th box of the basement of T . Proof. It follows easily from the fact that the insertion procedure induces a bijection between couples (T, k), where T is a Dyck tableau of size n and k is an integer with 0 ≤ k ≤ n, and Dyck tableau T ′ of size n + 1.

Bijection between Dyck tableaux and permutations

The insertion procedure can be used to construct a template of bijections between permutations and Dyck tableaux. To obtain this template, to each tableau T of size n, we label all the boxes of the basement from left to right by integers from 0 to n. Then, during the insertion procedure, we record in a table the labels of the chosen boxes. We call this table the history table of T . For example, Table 1 is the history table of the Dyck tableau of Figure 16.

N I σ [i] = #{j ′ < j : σ(j ′ ) < σ(j) and σ(j) = i}.
As an example, Table 1 is the non-inversion table of the permutation 24153. It should be clear that the set of history tables of size n coincides with the set of non-inversion tables N I σ where σ runs through permutations of size n.

By interpreting the history table of a Dyck tableau as the non-inversion table of a permutation, we obtain a direct bijection from Dyck tableaux to permutations. Throughout all this article, we will denote by φ this bijection.

We will now describe φ in a more simple and direct way. Let σ be a permutation of size n. We first construct a basement of size n + 1. Then, we label all the columns of the basement from left to right with the entries of σ. The bijection is obtained by iterating n dot-insertions from the basement. The j-th dot-insertion consists in the following two steps:

1) we add one dotted box in the column with entry j;

2) if the new dotted box is to the left of the dotted box added during step j -1, we add a ribbon between these two boxes.

Figure 17 shows bijection φ. It is important to note that applying bijection φ to a Dyck tableau T gives the same result than interpreting the history table of T as a non-inversion table. To prove this fact, we just have to remark that: ⊲ the insertion procedure can be followed from φ by removing at each dot-insertion the empty columns;

⊲ if a(j) denotes the number of non empty columns to the left of the column with entry j after j dot-insertion in bijection φ, then one has:

a(j) = N I φ(T ) [j].
It is clear that bijection φ is simpler than the insertion procedure, and that it gives a direct and elegant solution to the problem studied by de Medicis and Viennot in [START_REF] De Medicis | Moments de polynômes de q-Laguerre et la bijection de Foata-Zeilberger[END_REF], but a drawback of φ is that we have to wait the end of the procedure to obtain a Dyck tableau. It is convenient with the insertion procedure that the current tableau during the construction is always a Dyck tableau.

Generalized patterns

The aim of this section is to study some generalized patterns in permutations through the use of Dyck tableaux. To this end, we choose to label the dots in a Dyck tableaux with respect to the insertion algorithm: a dotted box inserted at time j gets the label j. We shall consider patterns with constraints on their values, and not on their places, which is more usual in the literature. A pattern 2 + 2 of a permutation σ is a sub-word ab of σ such that a = b + 1. A pattern 2 + 12 of a permutation σ is a sub-word abc of σ such that b < c and a = c + 1. A pattern 1 + 21 of a permutation σ is a sub-word abc of σ such that a = c + 1 and b > a. For example, in the permutation 2746153, there are It is more common in the literature (for example in [START_REF] Corteel | Bijections for permutation tableaux[END_REF][START_REF] Josuat-Vergès | Combinatorics of the three-parameter PASEP partition function[END_REF]) to study descents and generalized patterns 31 -2 and 2 -31 instead of the patterns 2 + 2, 2 + 12 and 1 + 21 used in the present work. This presentation is more convenient in our context, and it should be clear that the map σ → σ -1 sends our notions of generalized patterns to the ones in previous works. Proposition 8. The ribbons of a Dyck tableau T are in bijection with the patterns 2 + 2 of φ(T ). Moreover, we get the pattern 2 + 2 itself by reading from left to right the two labels that are linked by the ribbon.

As an example, the Dyck tableau on Figure 18 contains 4 ribbons which correspond to the occurences 21, 43, 65 and 76 of the pattern 2 + 2 in the permutation σ = 2746153. Proof. Let ab be a pattern 2 + 2 in the permutation σ = φ(T ). This means that the entry a is inserted in T immediately after b, and on its left, whence there is a ribbon between a and b in T . Conversely, if a ribbon in T links the two dots labeled a and b, the inverse insertion algorithm removes a immediately before b. Thus a = b + 1.

In a Dyck tableau T , the boxes placed below a dot (thus in a column) are called shadow boxes. Figure 19 illustrates this notion. Every column contains three types of boxes: exactly one dot and possibly clear and shadow boxes (cf. Figure 21). Proof. Let abc be a pattern 2 + 12 in the permutation σ. Thanks to bijection φ, we know that the column with entry b is between the columns of a and c. Proposition 8 implies that the pattern 2 + 2 corresponds to a ribbon which has been inserted after b. Thus the column of b intersects the ribbon and gives a shadow box. It is obvious that two different occurences of the pattern 2 + 12 give two distinct shadow boxes: the triples of columns of a, b and c are different.

Conversely, let us consider a shadow box. It is the intersection of a column labeled b and a ribbon of left and right endpoints labeled a and c. It should be clear that abc is an occurence of the pattern 2 + 12.

The proof is the same for the pattern 1 + 21.

A direct consequence of this proposition is the following corollary.

Corollary 1. Let σ be a permutation and i a letter of σ. The height of the dot labeled by i in the Dyck tableau T with φ(T ) = σ is equal to the number of patterns 1 + 21 in σ where i is the entry 2 in these patterns.

Bijection between Dyck tableaux and tree-like tableaux

Tree-like tableaux are combinatorial ojects introduced in [START_REF] Aval | Tree-like tableaux[END_REF]. A tree-like tableau B is a Ferrers diagram in which each box contains 0 or 1 dot (called respectively empty box or dotted box), with the following constraints:

1) the top-left-most box is dotted, and called the root of B;

2) for every non-root dotted box c, there exists a dotted box either above c in the same column, or to its left in the same row, but not both;

3) every column and every row has at least one dotted box.

The size of a tree-like tableau is defined as its number of dots. Figure 22 shows an example of tree-like tableau of size 9. An important property is that tree-like tableaux are endowed with a tree structure. The tree structure can be obtained graphically by drawing two lines from every dot of B, one down and one to the right, and stopping them at the boundary. We get in this way a binary tree with some edges crossings, which occur necessarly inside boxes of the Ferrers diagram. These boxes are called crossing boxes of the tree-like tableau. Figure 23 shows how to extract the tree structure of a tree-like tableau.

-→ -→

Figure 23: The tree structure of a tree-like tableau Like Dyck tableaux, tree-like tableaux are endowed with an insertion procedure [START_REF] Aval | Tree-like tableaux[END_REF]. We shall not give here details of this procedure, we just recall that there are k + 1 positions (the edges placed at the bottom and right boundary) to insert a dotted box in a tree-like tableau of size k. This explains why tree-like tableaux of size n are, as Dyck tableaux of the same size, enumerated by n!. We refer to [START_REF] Aval | Tree-like tableaux[END_REF] for a detailed presentation of these objects.

Although Dyck tableaux and tree-like tableaux are two different notions which have been designed for different purposes, their respective recursive structures are based on similar insertion procedures: in both cases, the key ingredients are the notion of special box together with the ribbon addition which ensures to inversibility of the procedure. Moreover, we will now explain that we have a canonical bijection between tree-like tableaux and Dyck tableaux. To do this, we label the edges of any tree-like tableau of size n following the boundary from left to right with integers from 0 to n. Then we may code a tree-like tableau B with an insertion table by recording at each insertion k the label of the edge chosen to insert the k-th dot. We may see this table as the history table of a Dyck tableau T , that is to say the non-inversion table of σ = φ(T ). We get in this way a bijection between tree-like tableaux T and Dyck tableaux D such that:

1) the number of dots in T is the number of dots in D;

2) there is a ribbon between dot j and dot j + 1 in T if and only if there is a ribbon between dot j and dot j + 1 in B or if dot j + 1 is the left son of dot j in the tree extracted from the tree-like tableau;

3) crossing boxes of B are in bijection with shadow boxes of T .

Figure 24 illustrates this bijection. 1. Evident from the insertion procedure.

2. Let H be the insertion table of a tree-like tableau B, thus the history table of the Dyck tableau T . When inserting j, we add a ribon between j and j + 1 in T if and only if H(j) ≥ H(j + 1). We add a ribon between j and j + 1 in a tree-like tableau if and only if H(j) > H(j + 1). Dot j + 1 is the left son of dot j if and only if H(j) = H(j + 1).

3. When inserting j in B, the number of crossing boxes added is the length of the ribbon: max(0, H(j) -H(j + 1)). It is precisely the number of shadow boxes added for the insertion of j in T .

The shape of a Dyck tableau

Thanks to the insertion algorithm, we are able to know the evolution of the path at the lower border of the Dyck tableau. In this section, we are interested in reading this shape without using the insertion algorithm, that is to say in reading it directly on the permutation.

We first define the right and left border. Consider the two steps in the Dyck path that are at the bottom of a column i in the Dyck tableau. The left one is called left border, the right one right border at position i. We denote by lb(i) (resp. rb(i)) the left (resp. right) border at position i. Proof. It suffices to observe that a ribbon added between two entries j = σ(i) and j +1 = σ(i ′ ) modifies the left and right borders only at positions i and i ′ .

Proposition 11. Let T be a Dyck tableau of size n, σ = φ(T ) and a position 1 ≤ i ≤ n. We let j = σ(i).

The left border at position i in T is obtained by:

lb(i) =    D if j = n; D if j + 1 is to the right of j in σ; U if j + 1 is to the left of j in σ.
The right border at position i in T is obtained by:

rb(i) =    U if j = 1; U if j is to the right of j -1 in σ; D if j is to the left of j -1 in σ.
For example, in σ = 24153, 4 = σ(2) is to the left of 3 and 5. The left and right borders at position 2 are both equal to D (see Figure 17).

Proof. Proposition 10 allows to look only at the entries j -1, j and j + 1.

⊲ If j = 1, there is no ribbon starting at position i thus rb(i) = U . ⊲ If j ∈ [2, n], since the right step at position i depends on whether there is a ribbon beginning at j, we consider the following:

either j is to the left of j -1, and rb(i) = D, -or j is to the right of j -1, and rb(i) = U .

⊲ If j = n, there is no ribbon ending at position i thus lb

(i) = D ⊲ If j ∈ [1, n -1]
, since the left step at position i depends on whether there is a ribbon ending at j, we consider the following:

either j + 1 is to the right of j, and lb(i) = D, -or j + 1 is to the left of j, and lb(i) = U .

The (RL/LR)-(minima/maxima) of a Dyck tableau

In this section, we want to interpret (RL/LR)-(minima/maxima) of a permutation directly on its associated Dyck tableau. Let σ be a permutation of size n. We shall say that j = σ(i) is a right-to-left minimum (RL-minimum for short) if and only if

∀i ′ > i, σ(i) < σ(i ′ ).
We define in the same manner RL-maxima, LR-minima and LR-maxima. By a slight abuse, we shall talk about (RL/LR)-(minima/maxima) of a Dyck tableau.

We let T denote a Dyck tableau of size n and σ = φ(T ).

Proposition 12. There is a bijection between RL-minima of σ and dotted boxes in T at height 0 with a right border equal to U .

Figure 26 shows this proposition for σ = 31428576 whose RL-minima are 6, 5, 2 et 1. Proof. First observe that a RL-minimum j can not have a ribbon above it (this would imply a smaller entry to its right), thus its height is 0. And since j -1 has to be to its left, rb(j) = U . Conversely, let j be an entry corresponding to a dotted box at height 0 with rb(j) = U . This implies that j -1 is to the left of j. Since there is no ribbon above j, all entries smaller than j are to the left of j.

Proposition 13. There is a bijection between LR-maxima of σ and dotted boxes in T with maximal height and with a left border equal to D.

Proof. Exactly the same argument as Proposition 12.

For the next two results, we need to identify the entries 1 and n on the Dyck tableau.

Proposition 14. The entry n corresponds to the rightmost dotted box with maximal height and a left border equal to D. The entry 1 corresponds to the leftmost dotted box with height 0 and a right border equal to U .

Proof. Since there is no ribbon under the dotted box corresponding to entry n, its height is maximal. There is also no ribbon on its left, thus its left border is D. Now, if two entries j and j ′ are such that j > j ′ and j to the left of j ′ , we have either lb(j ′ ) = U (if j ′ + 1 is to the left of j ′ ) or at least one ribbon under j ′ (if j ′ + 1 is to the right of j ′ ). This implies that among points with maximal height and with a left border equal to D, the greatest is the rightmost.

The argument is the same for the entry 1.

It should be clear that for any σ, n is a RL-maximum and 1 a LR-minimum.

Proposition 15. There is a bijection between RL-maxima of σ different from n and dotted boxes in T with maximal height, with a left border equal to U and placed to the right of n.

Proof. If j is a RL-maximum, then ⊲ there is no ribbon under j, thus it is at maximal height;

⊲ j + 1 is to the left of j, thus lb(j) = U ;

⊲ j has to be to the right of n.

Conversely, if j satisfies the three previous properties, j + 1 has to be to the left of j, there is no ribbon under j and since n is to its left, any entry greater than j has to be to its left also.

Proposition 16. There is a bijection between LR-minima of σ different from 1 and dotted boxes in T with height 0, with a right border equal to D and placed to the left of 1.

Proof. Same as Proposition 15.

Open questions and forthcoming work

As explained in the Introduction, a great motivation for this work is to try to find new objects and statistics that allow a simpler interpretation of the stationary distribution of the PASEP model in full generality. This general model depends on five parameters α, β, γ, δ, q. Corteel and Williams [START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials[END_REF] have given an explicit description of this distribution in terms of statistics defined on staircase tableaux. The set ST N of staircase tableaux of size N is partitioned into subsets ST τ N , for τ any of the 2 N states of the model. For each staircase tableau T , Corteel and Williams introduce a weight w(T ) in the five parameters α, β, γ, δ, q, then define

Z τ N = ST τ N w(T ) and Z N = ST N w(T )
and prove that the stationary probability of a state τ is given by the quotient Z τ N /Z N . A disadvantage of this description is that the definition of the weight w is really complicated, in particular its dependence to the parameter q. As a consequence, it seems out of reach to use this interpretation to try to define a Markov chain directly on the combinatorial objects (staircase tableaux) which should project to the PASEP. Such a Markov chain has been obtained by Duchi and Schaeffer [START_REF] Duchi | A combinatorial approach to jumping particles[END_REF] for γ = δ = q = 0 and more generally by Corteel and Williams [START_REF] Corteel | A Markov chain on permutations which projects to the PASEP (partially asymmetric exclusion process[END_REF] for γ = δ = 0.

In this perspective, the results of the present paper may be seen as a first step: we may use Dyck tableaux to describe the stationary probability of the PASEP for the special case where γ = δ = 0. In this case, a formula for Z τ N (α, β, 0, 0, q) was obtained in [START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process[END_REF], then interpreted in terms of statistics on permutations in [START_REF] Corteel | Bijections for permutation tableaux[END_REF][START_REF] Josuat-Vergès | Combinatorics of the three-parameter PASEP partition function[END_REF]. These results may be translated as:

Z τ N (α, β, 0, 0, q) = w ′ (T )
where the sum is over a subset of Dyck tableaux (which corresponds to the state τ , and for which we have an explicit description) and w ′ (T ) = α -l(T ) β -r(T ) q s(T )

with l(T ) the number of LR-minima of T , r(T ) the number of RL-minima of T , and s(T ) the number of shadow boxes in T . Moreover, we have a conjectural description in the case δ = 0 and β = 1 in terms of Dyck tableaux, but there is still work to be done.

Figure 1 :

 1 Figure 1: The staircase partition E4

Figure 2 :

 2 Figure 2: The Dyck paths of size 3

Figure 3 :

 3 Figure 3: First floor of a Dyck path

Figure 4 :

 4 Figure 4: The labeling of columns

Figure 5 :Figure 6 :

 56 Figure 5: A Dyck tableau of size 6

Figure 7 :

 7 Figure 7: Basement of size 5

Figure 8 :

 8 Figure 8: A Dyck tableau and its basement

⊲

  for a box of the basement; ⊲ D for a down step of the border; ⊲ U for an up step of the border; ⊲ i for a dot at height i. D0D D0D D1U D2U U 0U D1U U 0U

Figure 9 :

 9 Figure 9: Bijection between Dyck tableaux and weighted Dyck paths

Figure 10 illustrates

 10 Figure 10 illustrates this example on Dyck tableaux.

Figure 10 :

 10 Figure 10: Column addition

Figure 11

 11 Figure 11 illustrates this example on Dyck tableaux.

Figure 11 :

 11 Figure 11: A ribbon addition

Figure 12 :

 12 Figure 12: Special box of a Dyck tableau

Algorithm 1 1 : 4 :

 114 Insertion procedure Require: a weighted Dyck word of size k ≥ 0 If the size of the weighted Dyck word is 0 then ignore step 1 and 4. Find the special weight s. 2: Choose a letter. 3: Add a column at the position of the chosen ; If the chosen is to the left of s, perform a ribbon addition to the U letter following the new weight and the D letter preceding s. Ensure: a final weighted Dyck word of size k + 1.

Figure 13 Figure 13 :Figure 14 :

 131314 Figure13gives a complete example of insertion procedure where we have to add a ribbon at step 4.

Algorithm 2 1 : 2 :

 212 Inverse insertion procedure Require: a weighted Dyck word of size k ≥ 1 Find the special weight s. If the letter following s is a D, then find the leftmost maximal weight m placed to the right of s. The letter preceding m has to be a U . Delete the ribbon between D and U by permuting these two letters. 3: Delete the column of s : substitute the factor DsU by the letter. Ensure: a final valued Dyck word of size k -1.

Figure 15 : 3 Proposition 7 .

 1537 Figure 15: Generation tree for Dyck tableaux of size at most 3

Figure 17 :

 17 Figure 17: Bijection φ between permutations and Dyck tableaux

⊲ 4 patterns 2

 2 + 2 : 21, 43, 65 and 76; ⊲ 3 patterns 2 + 12: 746, 615 and 413; ⊲ 5 patterns 1 + 21: 271, 241, 261, 463 and 453.

Figure 18 :

 18 Figure 18: The ribbons represent the patterns 2 + 2 in the permutation

Figure 19 :

 19 Figure 19: Shadow boxes of a tableau

Figure 20 :

 20 Figure 20: Clear boxes of a tableau

Figure 21 :

 21 Figure 21: Clear and shadow boxes

Figure 22 :

 22 Figure 22: A tree-like tableau

Figure 24 :

 24 Figure 24: Bijection between tree-like tableaux and Dyck tableaux

3 D U Figure 25 :

 3U25 Figure 25: Left and right border in a Dyck tableau

6 Figure 26 :

 626 Figure 26: RL-minima of a Dyck tableau

Table 1 :

 1

A history table Figure 16: Dyck tableaux with history table of

Table 1

 1

  We may see this history table as a path connecting the empty Dyck tableau to a Dyck tableau in the generation tree presented in Section 2. A vector H ∈ N n is a history table if and only if∀1 ≤ j ≤ n, 0 ≤ H[j] < j.Thanks to Propositions 5 and 6, we know that two different Dyck tableaux give two different history tables. We obtain a template of bijection, since we may choose different interpretation of the history table as a permutation.In this paper, we shall use the following interpretation. Let σ be a permutation of size n. The non-inversion table of σ is the table N I σ ∈ N n defined by

Acknowledgment. The authors are very grateful to Xavier Viennot for many useful explanations and comments, and for his interest in this work. They also thank the anonymous referees for their valuable remarks.


Jean Fonlupt
email: jean.fonlupt@math.jussieu.fr

Alexandre Skoda
email: askoda@math.jussieu.fr

Strongly polynomial algorithm for the intersection of a line with a polymatroid

Keywords: Algorithm, graph, strength of a graph, submodular function, matroid, polymatroid, parametric linear programming

We present a new algorithm for the problem of determining the intersection of a half-line Δu = {x ∈ IR N | x = λu for λ ≥ 0} with a polymatroid. We then propose a second algorithm which generalizes the first algorithm and solves a parametric linear program. We prove that these two algorithms are strongly polynomial and that their running time is O(n 8 + γn 7 ) where γ is the time for an oracle call. The second algorithm gives a polynomial algorithm to solve the submodular function minimization problem and to simultaneously compute the strength of a network with complexity bound O(n 8 + γn 7 ).

Introduction

Let f be a set function on a finite set N = {1, . . . , n}. f is submodular if

f (S ∩ T ) + f (S ∪ T ) ≤ f (S) + f (T )
for all subsets S, T of N . If f is also normalized (f (∅) = 0) and monotone (f (U ) ≤ f (T ) whenever U ⊆ T ), the polymatroid associated with f is defined by:

P (f ) = {x ∈ IR N | x ≥ 0, x(T ) ≤ f (T ) for each T ⊆ N }.
Let u be a vector of IR N which describes the direction of the half-line

Δ u = {x ∈ IR N | x = λu for λ ≥ 0}. P (f ) ∩ Δ u is a closed interval [0, λ max ]u
where λ max is the value of the linear program:

max {λ | x ∈ P (f ) ∩ Δ u } (P)
This problem will be called the Intersection Problem.

We propose a strongly polynomial combinatorial algorithm for solving P. This algorithm called the Intersection Algorithm runs in time O(n 8 + γn 7 ) where γ is the time of an oracle call.

The Intersection Problem has interesting applications: consider the following parametric linear program:

z(λ) = max i∈N x i | x ∈ P(f), x ≤ λu (P λ )
Standard results in parametric linear programming show that the function λ -→ z(λ) is non-decreasing, concave and piecewise linear.

We prove that we need to solve at most n times the Intersection Problem to obtain a complete description of z(λ). This will be the object of the Parametric Intersection Algorithm which is a simple variant of the Intersection Algorithm. This second algorithm runs also in time O(n 8 + γn 7 ). As the solution of the parametric linear program for a certain choice of the parameter λ solves the submodular function minimization problem and for another choice of this parameter provides the value of the Strength of a Network if f is the rank function of a graphic matroid of a graph, we obtain a strongly polynomial algorithm with complexity bound O(n 8 + γn 7 ) for solving simultaneously these two problems. Polymatroids were introduced by Edmonds [START_REF] Edmonds | Submodular functions, matroids and certain polyhedra. Combinatorial structures and their applications[END_REF]. Examples of submodular functions are described in Fleischer [START_REF] Fleischer | Recent progress in submodular function minimization[END_REF], Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF], Korte and Vygen [START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF], Schrijver [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]. The Intersection Problem can be solved in strongly polynomial time using the ellipsoid method [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. Schrijver [START_REF] Schrijver | A combinatorial algorithm minimizing submodular functions in strongly polynomial time[END_REF] and Iwata, Fleischer and Fujishige [START_REF] Iwata | A combinatorial strongly polynomial time algorithm for minimizing submodular functions[END_REF] independently proposed combinatorial strongly polynomial algorithms for submodular function minimization. Vygen [START_REF] Vygen | A note on Schrijver's submodular function minimization algorithm[END_REF] showed that the running time of Schrijver's original algorithm was O(n 8 + γn 7 ) which was also the improvement given by Fleischer and Iwata [START_REF] Fleischer | Improved algorithms for submodular function minimization and submodular flow[END_REF]. Iwata [START_REF] Iwata | A faster scaling algorithm for minimizing submodular functions[END_REF] improved this bound to O((n 7 + γn 6 ) log n). Orlin [START_REF] Orlin | A faster strongly polynomial time algorithm for submodular function minimization[END_REF] developed a strongly polynomial algorithm in O(n 6 + γn 5 ) which is the best complexity bound known so far. All these approaches depend on the decomposition of feasible points of the polymatroid as convex combination of extreme points of this polytope; this idea was originated by Cunningham in [START_REF] Cunningham | Testing membership in matroid polyhedra[END_REF] and [START_REF] Cunningham | On submodular function minimization[END_REF]. Our own approach is based on the polymatroid itself and not on the base polyhedron associated to the polymatroid as do the above-cited authors; this is a major difference. Note however that an n-dimensional polymatroid can be seen as a projection of an (n + 1)-dimensional base polyhedron (see Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF]) but this observation can not be easily exploited from an algorithmic point of view. As a generalization of lexicographically optimal flow of Megiddo [START_REF] Megiddo | Optimal flows in networks with multiple sources and sinks[END_REF], Fujishige [START_REF] Fujishige | Lexicographically optimal base of a polymatroid with respect to a weight vector[END_REF] introduced the concept of lexicographically optimal base of a polymatroid. Problem P λ is known to be equivalent to the lexicographically optimal base problem [10] but we will not use this result.

Cunningham [START_REF] Cunningham | Optimal attack and reinforcement of a network[END_REF] in his study of the strength of a network had an approach based on the forest polytope of a graph. In [START_REF] Cheng | A faster algorithm for computing the strength of a network[END_REF], Cheng and Cunningham studied, for the problem of the strength of a network, a parametric linear program which can be seen as a specific case of our parametric linear program. Nagano [START_REF] Nagano | A strongly polynomial algorithm for line search in submodular polyhedra[END_REF] developped a strongly polynomial algorithm for the intersection of an extended polymatroid and a straight line, based on a direct application of the submodular function minimization problem. Although our algorithm is only designed for the intersection with a polymatroid, it provides a new algorithm for the submodular function minimization problem. Recently Nagano [START_REF] Nagano | A faster parametric submodular function minimization algorithm and applications[END_REF], extending Orlin's algorithm [START_REF] Orlin | A faster strongly polynomial time algorithm for submodular function minimization[END_REF] proposed an algorithm in O(n 6 + γn 5 ) to solve the parametric problem P λ . Our algorithm is not as good as Nagano's in time complexity but we hope that the interest of our approach is justified by the method we employ : we work directly on the polymatroid itself and we do not use known submodular function minimization algorithms. Many of the results presented here appear in the Ph.D thesis of Skoda [START_REF] Skoda | Force d'un graphe, multicoupes et fonctions sous-modulaires: aspects structurels et algorithmiques[END_REF].

The content of the paper can be summarized as follows. Section 2 recalls basic definitions and properties of polymatroids and present the general framework of the Intersection Algorithm. Section 3 describes the Intersection Algorithm and evaluates the time complexity of this algorithm. Section 4 describes the Parametric Intersection Algorithm and proves the strongly polynomiality of this algorithm; it is also shown in section 4 why this algorithm simultaneously solve the submodular minimization problem and finds the strength of a network. Many of the results in section 4 are standard (see for instance Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF]) but we include them with short proofs for completeness. Section 5 summarizes the results of the previous sections and proposes some new problems.

Preliminaries

1.

If ∅ ⊆ T ⊆ N , define f N \T by f N \T (A) = f (A) for all ∅ ⊆ A ⊆ N \ T .
f N \T is normalized, monotone and submodular.

The polymatroid P (f N \T ) is imbedded in the vector space IR N \T ; moreover

P (f N \T ) = P (f ) ∩ {x ∈ IR N | x i = 0 for i ∈ T }.

2.

We can treat and eliminate the following cases: if u / ∈ IR N + , λ max = 0. If there exists i ∈ N with u i = 0, P (f ) ∩ Δ u = P (f N \{i} ) ∩ Δ u and we can replace N by N \ {i}. Finally, assume that there exists i ∈ N with f ({i}) = 0; for any feasible point x ∈ P (f ),

x i = 0 since 0 ≤ x i ≤ f ({i}) and [0, λ max ]u = P (f N \{i} ) ∩ Δ u . If u i > 0, λ max = 0.
If u i = 0, we can replace N by N \ {i}. So, we will assume from now on that u > 0 and that f ({i}) > 0 for all i ∈ N .

3.

By order we mean in this paper a subset of N , called the support of the order, and a total order on this support. Elements in the support will be called ordered elements and elements not in the support will be called singletons. {O 0 , O 1 , . . . , O k , . . . , O k } is the set of distinct orders, K = {0, 1, . . . , k, . . . , k} is the set of upper indices listing the distinct orders. The order relation of O k will be denoted ≺ k . We will assume that, in the description of O k , the elements of the support S k are sorted in increasing order with respect to the order relation ≺ k :

O k = [i 1 , . . . , i l , . . . , i m ].
It was proved by Edmonds [6] that extreme points of P (f ) can be generated by the greedy algorithm: given an order O k = [i 1 , . . . , i m ] with support S k , the point a k ∈ IR N whose components are:

a k i1 = f ({i 1 }) a k i l = f ({i 1 , . . . , i l }) -f ({i 1 , . . . , i l-1 }) for l = 2, . . . , m a k i = 0 for all i ∈ N \ S k .
is an extreme point of P (f ). a k is the extreme point generated by O k . Edmonds proved also that any extreme point of P (f ) is generated by an order. Note also that

a k ({i 1 , . . . , i l }) = f ({i 1 , . . . , i l }) for l = 1, . . . , m. (1)
Two distinct orders may generate the same extreme point. In [START_REF] Bixby | The partial order of a polymatroid extreme point[END_REF] Bixby, Cunningham, and Topkis gave a complete characterisation of extreme points of P (f ). In particular they proved that the intersection of all the orders which generate the same extreme point is a minimal partial order and two minimal distinct partial orders generate two distinct extreme points. However we will not use this result here.

4.

We will associate to a matroid order O k the following oriented graph G(k):

The node-set of G(k) is {0} ∪ N where 0 is a new element; from now on we will use the term element rather than node. The edge-set of G(k) denoted E(k) is defined as follows:

* e = (0, i) k ∈ E(k) if and only if i is a singleton of O k , * e = (i, j) k ∈ E(k) if and only if i and j are ordered elements of O k and i ≺ k j.
If K ⊆ K we define the graph G(K) as:

G(K) = ({0} ∪ N, k∈K E(k)).
Note that G(K) may have (many) parallel edges: if i ≺ k1 j and i ≺ k2 j for k 1 , k 2 ∈ K, (i, j) k1 and (i, j) k2 are parallel edges.

5.

We will now define two operations on the order

O k = [i 1 , . . . , i m ]. If j is a singleton of O k , O k is
obtained by inserting j after the last element i m of O k and O k will be called the order associated to the edge e = (0, j) k . If i ≺ k j. O k is obtained by moving j just before i in O k and O k will be called the order associated to the edge e = (i, j) k . In both cases, we say that O k is an adjacent order to O k . Let us set b = a ka k . We recall (see for instance [START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF] or [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]) and prove for completeness the following result:

Lemma 1. If O k is associated to e = (0, j) k , b j ≥ 0; b i = 0 for i ∈ N \ {j}. If O k is associated to e = (i, j) k , b j ≥ 0; b l ≤ 0 for i ≺ k l ≺ k j or l = i, b l = 0 otherwise. Moreover n i=1 b i = 0.

Proof:

Set

T s = {r |r ∈ N, r ≺ k s} for s ∈ N and let S k be the support of O k . If O k is associated to e = (0, j) k , b i = 0 for i ∈ N \ {j}. As f is monotone, b j = a j k -a j k = f (S k ∪ {j}) -f (S k ) ≥ 0. If O k is associated to e = (i, j) k , as T i ⊂ T j and f is submodular, b j = a j k -a j k = f (T i ∪ {j}) -f (T i ) -(f (T j ∪ {j}) -f (T j )) ≥ 0. If i ≺ k l ≺ k j or l = i, b l = a l k -a l k = f (T l ∪ {j, l}) -f (T l ∪ {j}) -(f (T l ∪ {l}) -f (T l )) ≤ 0. O k and O k have the same support S k and n i=1 a k i = n i=1 a k i = f (S k ). Thus n i=1 b i = 0.

6.

We will express points of the half-line Δ u as convex combinations of extreme points of P (f ). So, let K ⊆ K. We say that K is a feasible set if the system:

L(K) ⎧ ⎨ ⎩ α k ≥ 0 for k ∈ K λu = k∈K α k a k k∈K α k = 1
has a feasible solution. If K is feasible and the vectors a k : k ∈ K are linearly independent, |K| ≤ n and the solution (α k , k ∈ K; λ) of L(K) is unique. If this solution is strictly positive, K is called a positive basis. λ will be called the value of the basis. If K is a feasible set, K contains a positive basis (this is Caratheodory's theorem). Let K be a positive basis and let K 1 be a subset of K. Assume that there exists K ⊆ K and a triangular set {b 1 , . . . , b n } with b r = a k ra kr where k r ∈ K and k r ∈ K 1 for r = 1, . . . , n. We can now establish the following easy but fundamental lemma: Lemma 2. There exists a positive basis contained in

A set {b 1 , . . . , b n } of vectors of IR n is called triangular if: * b k i = 0 whenever 1 ≤ k < i ≤ n, * b k i ≤ 0 whenever 1 ≤ i < k ≤ n, * b k k > 0 for k = 1, . . . , n. If {b 1 , . . . , b n } is triangular, the n × n matrix B induced
(K ∪ K ) \ {k 1 } for some k 1 ∈ K 1 .

Proof:

As {b 1 , . . . , b n } is a triangulated set, there exists n non-negative numbers μ r , r = 1, . . . , n such that

u = n r=1 μ r a k r - n r=1 μ r a kr . So, there exists non-negative numbers ν k , k ∈ K 1 ∪ K with : u = k∈K ν k a k -k∈K1 ν k a k k∈K ν k -k∈K1 ν k = 0. Let (α k , k ∈ K; λ) be the solution of L(K). For any λ > 0, (λ + λ )u = k∈K α k a k + λ ( k∈K ν k a k -k∈K1 ν k a k ) k∈K α k + λ ( k∈K ν k -k∈K1 ν k ) = 1 Set λ = min k∈K1 α k ν k (if ν k = 0, α k ν k = +∞
) and let k 1 ∈ K 1 be an upper indice which realizes this minimum. The set (K ∪ K ) \ {k 1 } is feasible and contains a positive basis. L((K ∪ K ) \ {k 1 }) has n + 1 rows and at most 2n columns. By standard results in linear programming, we can find the new feasible basis in a time O(n 3 ) (See for instance [START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF], chapter 4, exercise 5).

7.

Our initial positive basis will be K = {1, . . . , n} where

O k = [k] for i = 1, . . . , n. Thus a k i = 0 if i = k and a k k = f ({k})
; the solution associated to this basis is:

α k := λu k f ({k}) k = 1, . . . , n; λ := 1 n k=1 u k f ({k})
.

The Intersection Algorithm

Let (α k for k ∈ K; λ) be the solution associated to a positive basis K. λu(T ) ≤ f (T ) for any T ⊆ N ; equality holds for λ max and T min ⊆ N with

f (T min ) u(T min ) = min f (T ) u(T ) | ∅ ⊂ T ⊆ N .
Optimality occurs when the following condition holds:

Proposition 1. If 0 is not a root of G(K), let T be the set of elements of N not reachable from 0; λ max = λ and T min = T .

Proof:

If 0 is not a root of G(K), let T be the set of elements of N not reachable from 0. Let

O k = [i 1 , . . . , i m ] for some k ∈ K. If (0, i) k is an edge of G(K), i is a singleton of O k and i / ∈ T ; so T ⊆ {i 1 , . . . , i m }. If r ≺ k l and l ∈ T , then r ∈ T . This implies that T = {i 1 , i 2 , . . . , i l } for some 1 ≤ l ≤ m; equations (1) imply that a k (T ) = f (T ). λu(T ) = k∈K α k a k (T ) = ( k∈K α k )f (T ) = f (T )
and our lemma is proved.

So we will study now the case where 0 is a root of G(K). As the set K will be updated at each iteration of the algorithm, we can always assume that K = {1, 2, . . . , |K|}. Let d 1 (i) denote the distance from 0 to i for each i ∈ N . d 1 (i) will be the first parameter assigned to i. We say that an element j ∈ N is in bad position on O k if, either j is a singleton of O k , or if there exists an element i with i ≺ k j and d 1 (i) < d 1 (j). The number of elements in bad position on O k will be denoted α(k) and we set:

K(j) = {k ∈ K | j is in bad position on O k }.
Our second parameter d 2 (j) is defined by: d 2 (j) = max k∈K(j) α(k). We say that k ∈ K(j) is critical for j if d 2 (j) = α(k) and we say that k is a critical upper-indice of K if k is critical for at least one element of N . K 1 will denote the set of critical indices. Finally the third parameter d 3 (j) assigned to j is:

d 3 (j) = k j = min(k | k is critical for j).
We will also associate to K three parameters:

Δ 1 (K) = n j=1 d 1 (j); Δ 2 (K) = n j=1 d 2 (j); Δ 3 (K) = |K 1 |.
Before describing our algorithm, we need to implement a special procedure which renames the elements of N according to the following rules:

Note that there exists a unique way to rename the elements of N if we apply these four rules (except for singletons which can be renamed in many ways since rule 4 do not apply to singletons). Let j ∈ N ; if d 1 (j) = 1, j is a singleton for O kj and we will associate to j the edge e j = (0, j) kj . If d 1 (j) > 1, j is in bad position on O kj for some k j ∈ K; there exists an element i ∈ N with i ≺ kj j and d 1 (i) < d 1 (j) and we can choose for i the smallest predecessor of j on O kj which satisfies this property; we will associate to j the edge e j = (i, j) kj . Let O k j be the adjacent orders induced by e j for j ∈ N and consider the set of vectors {b 1 , . . . , b n } with b j = a k ja kj for j = 1, . . . , n. The following result holds: Lemma 3. Either one of the vectors b 1 , . . . , b n is the null vector, or the set {b 1 , . . . , b n } is triangulated.

Proof:

Assume that b j = 0 for j = 1, . . . , n. If e j = (0, j) kj , b j j ≥ 0 and b j i = 0 for i = j by lemma 1. As b j = 0, b j j > 0.

If e j = (i, j) kj , b j j ≥ 0 but n l=1 b j l = 0 by lemma 1 and b j l ≤ 0 for l = j by lemma 1, therefore b j j > 0. As d 1 (i) < d 1 (j), i < j by rule 1. Let l ∈ N distinct from i and j.

If l does not satisfy the relation

i ≺ kj l ≺ kj j, b j l = 0; if i ≺ kj l ≺ kj j, b j l ≤ 0 by lemma 1. But d 1 (l) = d 1 (j) -1 or d 1 (l) = d 1 (j); if d 1 (l) = d 1 (j) -1, then l < j (rule 1). if d 1 (l) = d 1 (j), l is in bad position on O kj ; d 2 (l) ≥ α(k j ) = d 2 (j). If d 2 (l) > d 2 (j), then l < j (rule 2); if d 2 (l) = d 2 (j), k j is critical for l and k l ≤ k j . If k l < k j , then l < j (rule 3).
If k l = k j , l ≺ kj j, then l < j (rule 4). So, for all possible situations, we have b j l ≤ 0 for 1 ≤ l < j, b j j > 0 and b j l = 0 for j < l ≤ n; this proves our statement. We propose now a strongly polynomial algorithm to compute λ max :

INTERSECTION ALGORITHM

Input: A normalized, monotone, submodular function f ; a direction u ∈ IR N . Output: λ max , T min . step 1. Take for initial positive basis the set K := {1, . . . , n} and compute the initial solution (α 1 , . . . , α n , λ) associated to this basis. step 2.

Represent G(K) by the list of the set of out-neighbours of each node of G(K). step 3. If 0 is not a root, let T be the set of elements not reachable from 0, λ max = λ, T min = T ; return λ max , T min ; then stop. else compute the distance d 1 (j) from 0 to each element j ∈ N . step 4.

Compute for each k ∈ K the number α(k) and for each element j ∈ N the parameters d 2 (j) and d 3 (j) = k j . Compute the numbers Δ 1 (K), Δ 2 (K), Δ 3 (K). step 5. Implement the relabeling procedure on the set N using rules 1,2,3,4. step 6.

Find the edges e j := (i, j) kj and the vectors b j := a k ja kj for j ∈ N . step 7.

If one of this vector say b j = a k ja kj is the null vector, set K := K ∪ {k j }, K := K \ {k j } and go to step 2. else set K := {k 1 , . . . , k n } and K 1 be the set of critical indices of K; apply the procedure described in lemma 2. Let K 2 ⊆ (K ∪ K ) \ {k j } for some k j ∈ K 1 be the positive basis obtained after application of this procedure; K := K 2 , go to step 2.

It remains to analyze the complexity of this algorithm. First, we study the running time of each step of an iteration. The most critical step is step 2 where we have to represent the graph G(K) which may have O(n 3 ) edges. Let L be the (n + 1) × (n + 1) adjacency matrix of G(K) where L(i, j) = 1 if j is an out-neighbour of i and L(i, j) = 0 otherwise. We start to build the adjacency matrix L k for each graph G({k}) (k ∈ K): first we read the sequence

O k = [i 1 , . . . , i m ] in O(n log n) time.
Then we fill the coefficients L k (0, j) for 1 ≤ j ≤ n in O(n) time (these coefficients are associated to singletons). To get the rest of the adjacency matrix L k we start from the m× m adjacency matrix associated to the ordered set: [1, . . . , m]. This matrix is upper triangular with coefficients equal to 1 above the diagonal and 0 otherwise and can be obtained in O(n 2 ) time. Permuting the rows and the columns of this matrix requires O(n 2 ) elementary operations. The permutation which produces the matrix L k is obtained by sorting the elements of

O k = [i 1 , . . . , i m ] by increasing value of the indices in time O(n log n). So the global time is O(n 2 ). All the matrices L k are obtained in O(n 3 ) time since |K| ≤ n. Now, L(i, j) = 1 if, for some k ∈ K, L k (i, j) = 1 and L(i, j) = 0 otherwise; each coefficient L(i, j) is computed in O(n) time.
Thus the total running time for obtaining L is O(n 3 ). Using the adjacency matrix for G(K), the running time of step 3 is O(n 2 ). in step 4 each α(k) is computed in O(n 2 ) and all the α(k) in O(n 3 ). All parameters d 2 (j) and d 3 (j) for j ∈ N can be computed in O(n 2 ) time. The three numbers Δ 1 , Δ 2 , Δ 3 are obtained in linear time. So, the total amount of work for step 4 is O(n 3 ). The relabeling procedure of step 5 can be implemented in O(n 2 ) time: we first have to sort the elements of N by increasing distance, then by decreasing value of the second parameter d 2 (j), then by increasing value of the third parameter k j and finally by describing the list of the ordered elements of O kj . In step 6 we have n 2 oracle calls and a time O(γn 2 ) if γ is the time for an oracle call. We compute each vector a k j in O(n 2 ) time. Thus, the total amount of work to implement all the parts of step 6 is O(n 3 + γn 2 ). We already noticed in lemma 2 that step 7 can be implemented in O(n 3 ) time. As a consequence, the time needed to perform all the steps of the current iteration is O(n 3 + γn 2 ). We need now to find the maximum number of iterations of the algorithm. Let K and K be the positive bases in two successive iterations of the algorithm. The analysis of the complexity of the algorithm is based on the three following claims:

Claim. Δ 1 (K) ≥ Δ 1 (K) Δ 1 (K) = Δ 1 (K), Δ 2 (K) < Δ 2 (K) or Δ 1 (K) = Δ 1 (K), Δ 2 (K) = Δ 2 (K), Δ 3 (K) < Δ 3 (K)
. By the preceding claims these bases are totally ordered with the lexicographic order; hence the triplets (Δ 1 (K), Δ 2 (K), Δ 3 (K)) are all different. But the value of a distance cannot exceed n and Δ 1 (K) ≤ n 2 ; the value of each second parameter cannot exceed n and Δ 2 (K) ≤ n 2 ; finally Δ 3 (K) ≤ n. so the total number of iterations cannot exceed n 5 . The total running time is O(n 8 + γn 7 ). Note that this is precisely the running time of the original algorithms for submodular function It may be possible to improve this complexity bound by, for instance, updating informations from an iteration to the next iteration. It may also be possible that the number of iterations is not greater than n 4 but we did not investigate these questions.

The Parametric Intersection Algorithm

A parametric linear program

We consider in this section the following parametric linear program:

z(λ) = max i∈N x i | x ∈ P(f), x ≤ λu (P λ ) H λ will be the polytope: {x ∈ IR N ; 0 ≤ x ≤ λu}. A subset T ⊆ N is such that z(λ) = λu(N \ T ) + f (T )
for some λ ≥ 0 will be called λ-tight.

The following two propositions are standard results. We give short proofs for completeness. For a generalization of Proposition 2, see theorem 7.15 of [START_REF] Fujishige | Submodular functions and optimization[END_REF].

The property given in Proposition 3 corresponds to theorem 4.6 in Megiddo [START_REF] Megiddo | Optimal flows in networks with multiple sources and sinks[END_REF] and is also used in Fujishige's algorithm [START_REF] Fujishige | Lexicographically optimal base of a polymatroid with respect to a weight vector[END_REF][START_REF] Fujishige | Submodular functions and optimization[END_REF] for finding the lexicographically optimal base of a polymatroid with respect to a weight vector.

Proposition 2. There exists λ 0 = 0 < λ 1 < . . . < λ s < λ s+1 = +∞ with s ≤ n and a unique increasing family of sets T 0 = ∅ ⊂ T 1 , . . . , ⊂ T s = N such that:

z(λ) = λu(N \ T r ) + f (T r ) for λ r ≤ λ ≤ λ r+1 , r = 0, . . . , s.
Moreover T r is the unique λ-tight set for λ r < λ < λ r+1 , r = 0, . . . , s.

Proof:

We will use the following theorem of Edmonds [START_REF] Edmonds | Submodular functions, matroids and certain polyhedra. Combinatorial structures and their applications[END_REF] (this theorem gives the rank formula of a polymatroid):

The Parametric Intersection Algorithm

Some of the ideas of our Parametric Intersection Algorithm appear in Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF]. We will study the case when the Intersection Algorithm returns λ 1 = λ max and the set T min . The case λ r for r > 1 is similar and will not be treated. x 1 = λ 1 u is the solution of P λ1 ; (α 1 k , k ∈ K; λ 1 ) is the solution of L(K) where K is the last positive basis K returned by the Intersection Algorithm:

L(K) ⎧ ⎨ ⎩ α k ≥ 0 for k ∈ K λu = k∈K α k a k k∈K α k = 1
and T 1 is the set of nodes of G(K) not reachable from 0. Instead of stopping as in the Intersection Algorithm, we could try to use these informations in order to find the second value λ 2 . By proposition 3, λ 2 is the value of the linear program:

λ 2 = max{λ | x ∈ P (f ), x = λ 1 u + (λ -λ 1 )u 1 , λ ≥ λ 1 }
where u 1 is the new direction defined as in proposition 3. So our original system L(K) is changed into a different system:

L 1 (K) ⎧ ⎨ ⎩ α k ≥ 0 for k ∈ K λ 1 u + (λ -λ 1 )u 1 = k∈K α k a k k∈K α k = 1 Since λ 1 is fixed, the variables of L 1 (K) are (α k , k ∈ K; λ) and (α 1 k , k ∈ K; λ = 0) is the unique solution of L 1 (K).
T 1 is the set of elements of G(K) not reachable from 0 and N 1 = N \ T 1 is the set of elements reachable from 0; we will set |T 1 | = l ≥ 1. If T 1 = N , λ 1 = λ s and we stop. So, we will assume that l < n. d 1 (i) is the distance from 0 to i for i ∈ N 1 . We observed in the proof of Proposition 1 that the elements of T 1 are the first elements of the sequence describing O k for each k ∈ K: if

O k = [i 1 , . . . , i l , i l+1 , . . . , i m ] T 1 = {i 1 , . . . , i l }.
To maintain this property throughout the next iterations of the algorithm, we assign to each element i of T 1 a first parameter d 1 (i) equal to n: if j ∈ N , d 1 (i) ≥ d 1 (j) and i will never be in bad position for any order O k in the forthcoming iterations . The numbers α(k) for k ∈ K are computed as in the Intersection Algorithm. Note however that no upper indice k is critical if i ∈ T 1 , so we will set d 2 (i) = 0 for i ∈ T 1 . The third parameter will play no role for elements in T 1 and will be discarded. Let T 1 = {nl + 1, . . . , n}. The elements of T 1 will never be affected by the relabeling procedure because of the first rule of this procedure. Next, we will find the edges e j := (i, j) kj and the vectors b j := a k ja kj as in step 6. However these edges exist only for j ∈ N 1 since no indice k is critical for j ∈ T 1 . Thus there exists |N 1 | edges e j and |N 1 | vectors b j . The elements of T 1 remain in the first position in any new order O k j introduced in step 6. Since b j i = 0 for i ∈ T 1 and j = 1, . . . , nl the linear system μ 1 b 1 + . . . + μ n b n-l = u 1 has a non-negative solution. We can terminate step 7 as in the Intersection Algorithm.

n, n). At the final iteration no element is reachable from 0 and the triplet is (n 2 , 0, 0). As in the proof of the Intersection Algorithm, all the bases are distinct and the number of iterations cannot exceed n 5 ; the complexity of the Parametric Intersection Algorithm is O(n 8 + γn 7 ). Let us give now two applications of this algorithm.

Strength of a polymatroid

Consider the last discontinuity λ s of z(λ):

z(λ) = f (N ) = f (N \ T s-1 ) + λ s u(T s-1 ). λ s = f (N )-f (N \Ts-1) u(Ts-1) . If (T, N \ T ) is a partition of N with f (N ) > f(N \ T ), f (N ) = f (N \ T s-1 ) + λ s u(T s-1 ) ≤ f (N \ T ) + λ s u(T )
and it is easy to see that:

λ s = f (N )-f (N \Ts-1) u(Ts-1) ≥ f (N )-f (N \T ) u(T ) . If we set σ(f, u) = min{ u(T ) f (N )-f (N \T ) for all T ⊂ N ; such that f (N ) > f(N \ T )}, σ(f, u) = 1
λs . By analogy with graphs, we call σ(f, u) the strength of the polymatroid P (f ). If f is the rank function of a graphic matroid, σ(f, u) is precisely the strength of a network.

Minimization of a submodular function

Let f be a submodular set function defined on N . f may not be monotone or normalized. The submodular function minimization problem consists in finding a subset of N which realizes the minimum of f . We will prove that this subset can be returned by the Parametric Intersection Algorithm for a well chosen value of the parameter λ. Let us first make (n + 2) oracle calls: f (i) for i ∈ N , f (N ) and f (∅). Set δ = max i∈N f (i) and δ 0 = min(0, f (N )).

Lemma 4. Let

λ = 2(nδ -δ 0 ) + 1. Define f by f (T ) = f (T ) + λ|T | -f (∅),
f is normalized, monotone and submodular.

Proof:

Clearly f is normalized and submodular. Let T ⊆ N ; By the submodularity of f , f (T )

≤ i∈N f ({i}) ≤ nδ ≤ nδ -δ 0 . As δ 0 ≤ f (N ) ≤ nδ, λ > 0. f (T ) ≥ f (N ) -f (N \ T ) ≥ δ 0 -nδ. If S

Conclusion

We were motivated in the study of the intersection of a polymatroid and a half-line by problems in the Telecommunication industry, suggested by Jérôme Galtier and Alexandre Laugier, where the strength of a network is a useful parameter; by choosing randomly the direction u according to a uniform distribution law it was possible to show that the average number of iterations for the Intersection Algorithm is O(n); in a forthcoming paper, we will prove that the theoretical average complexity of a very simple algorithm for solving the Intersection Problem is O(n 5 ), confirming the good practical bound observed by numerical tests. The complexity of the Intersection Problem of a polytope with a straight line is trivial if the inequalities describing the polytope are explicitly given as input, by enumeration of these inequalities; if the polytope is given by its extreme points, the existence of a combinatorial algorithm to solve the Intersection Problem is a difficult open problem since it is possible to show that the existence of such an algorithm would answer positively the following question: does there exist a combinatorial, "simplex-like" algorithm for linear programming? Finally the remaining case is when the polytope and the straight line are embedded in a vector space IR n with the number of inequalities describing the polytope not polynomial in n. The question is to find a strongly polynomial algorithm in n for solving the Intersection Problem. Of course a condition should be satisfied: the optimization problem on this polytope has to be solvable in polynomial time thanks to the ellipsoid method for instance. So we may hope that there exists strongly polynomial combinatorial algorithms when we replace the polymatroid by the matching polytope, the branching polytope, or the stable set polytope of a perfect graph. All these questions seem to be opened.

  by this set of columnvectors is upper triangular and non-singular since b k k > 0 for k = 1, . . . , n. Thus the linear system μ 1 b 1 + . . . + μ n b n = u > 0 has a unique solution μ = (μ 1 , . . . , μ n ) and by standard results in linear algebra the inverse of B is non-negative and μ > 0. This solution can be computed in O(n 2 ) time.

Theorem 2 .

 2 and T are two subsets of N , -λ ≤ f (S)f (T ) ≤ λ. Assume that S ⊂ T :f (T )f (S) ≥ f (T )f (S) + λ ≥ 0 and f is monotone. Let u be the vector with all components equal to 1. If S ⊆ N is λ-tight, z(λ) = f (S) + λ|N \ S| = min(f (T ) + λ|N \ T | for all T ⊆ N ), f (S)+λ|S|-f (∅)+λ|N \S| =min(f (T )+λ|T |-f(∅)+λ|N \T | for all T ⊆ N ). This proves that f (S) = min(f (T )| T ⊆ N ).We just proved the following result: The Parametric Intersection Algorithm solves the submodular function minimization problem and simultaneously computes the strength of the polymatroid in O(n 8 + γn 7 ) time.

This research has been supported by a grant of "France Telecom R&D Sophia Antipolis" during three years.

Proof:

Let e j = (i, j) kj be the edge associated to j ∈ N in step 6; O k j is the adjacent order of O kj . Let (l, l ) k j be an edge of G(k j ). If (l, l ) kj is also an edge of G(k j ), d 1 (l )d 1 (l) ≤ 1; if (l, l ) kj is not an edge of G(k j ), there are two possible cases: either j is a singleton of O kj and l = j; as d 1 (j) = 1, d 1 (l )d 1 (l) ≤ 1. or j is an ordered element of O kj , l = j and l = i or i ≺ kj l ≺ kj j; but d 1 (i) = d 1 (j) -1 ≤ d 1 (l ) ≤ d 1 (j) and d 1 (l )d 1 (l) ≤ 1. So, the relation d 1 (l )d 1 (l) ≤ 1 always hold. This shows that the distances in G(K) and in G(K ∪ {k j }) are equal. G(K ∪ K ) is obtained by adding successively to G(K) all the edge-sets of the graphs G(k j ) for all k j ∈ K . Thus the distances are the same in ∪ K ) and in G(K). But G(K) is obtained from G(K ∪ K ) by deletion of a subset of edges. Hence the distances can only increase in G(K) and

Proof:

Let e j = (i, j) kj be the edge of the previous claim. As the distances are equal in G(K) and G(K) j is in bad position on O kj but is not in bad position on O k j ; this is obvious if j is a singleton; this is also true if j is not a singleton by our choice of i; indeed recall that i is the first element such that d 1 (i) < d 1 (j) and i ≺ kj j when we describe O kj = [i 1 , . . . , i m ] from i 1 to i m . Elements distinct from j are in bad position on O k j if and only if they are in bad position on O kj . Thus α(k j ) = α(k j ) -1. For an element l in bad position on O kj and O k j , we have

deletion of a subset of upper indices. Therefore, either d 2 (l) remains unchanged or d 2 (l) strictly decreases. This proves the claim.

Proof:

Let us continue the proof of the preceding claim. If the parameters d 2 (j) are unchanged and l is in bad position on O k j , d 2 (l) ≥ α(k j ) > α(k j ). Hence k j is not critical for l and k j cannot be a critical indice of K. The set of critical indices of K is included in K 1 ; but there exists at least a critical indice k j of K 1 which does not belong to K; this implies that Δ 3 (K) < Δ 3 (K). We can state now our main result: Theorem 1. The running time of the Intersection Algorithm is O(n 8 + γn 7 ), where γ is the time for an oracle call.

Proof:

Define a lexicographic order among the positive bases enumerated during the algorithm. We say that

The fonction λ ∈ IR + -→ z(λ) which is the minimum of a finite set of nondecreasing affine functions is a piecewise-linear non-decreasing concave function. There exists λ 0 = 0 < λ 1 < . . . < λ s and a family of sets T 0 , T 1 , . . . , T s such that:

For 0 ≤ λ ≤ λ max , P (f ) ∩ H λ = H λ ; x = λu is the solution of (P λ ) and z(λ) = λu(N ). For λ > λ max , λu / ∈ P (f ) and λu(N ) > z(λ). This implies that λ 0 = 0, λ 1 = λ max , T 0 = ∅. For λ large enough, H λ ∩ P (f ) = P (f ) and z(λ) = f (N ); so z(λ) = f (N ) for λ ≥ λ s and T s = N . For λ 1 ≤ λ ≤ λ s , let A and B be two λ-tight sets. By the submodularity of f , A ∩ B and A ∪ B are also λ-tight sets; hence we can assume that A (resp. B) is the unique λ-tight set of minimum (resp. maximum) cardinality and A ⊆ B. If A ⊂ B, u(N \ B) < u(N \ A) since u > 0; by the concavity and the continuity of z(λ), there exists ε > 0 such that z(λ

is not a linear function in any neighborhood of λ; thus λ ∈ {λ 1 , . . . , λ s }.

Finally r ≤ n since the number of sets T r cannot exceed n. This finishes the proof. Let x r be the solution of (P λr ) and define a new direction:

We want to find now the extremities of the closed interval

If x is the solution of the linear program defined in the statement of proposition 3, there exists a tight set S ⊆ N for x which contains at least one element i ∈ S \ T r . But S ∪ T r which strictly contains T r is also tight for x by the submodularity of f and x(N

x is solution of P λ . But we know by proposition 2 that T r is the largest λ r -tight set and that T r is the unique λ-tight set in the interval λ r < λ < λ r+1 . Thus the set S ∪ T r can exist only if λ = λ r+1 .

PARAMETRIC INTERSECTION ALGORITHM

Input: A normalized, monotone, submodular function f ; a direction u ∈ IR N . Output: s ≥ 1; λ 0 , . . . , λ s ; T 0 , . . . , T s .

step 1.

Take for initial positive basis K := {1, . . . , n} and compute the initial solution (α 1 , . . . , α n , λ) associated to this basis. Set r = 0, λ 0 = 0, T 0 = ∅. step 2.

Represent G(K) by the list of the set of out-neighbours of each node of G(K). step 3.

If 0 is not a root, let T be the set of elements not reachable from 0; compute the distance d 1 (j) from 0 to each element j

Compute for each k ∈ K α(k) and for each element j ∈ N \ T the parameters d 2 (j) and k j . Compute the numbers Δ 1 (K), Δ 2 (K), Δ 3 (K). step 5.

Implement the relabeling procedure on the set N \ T with rules 1,2,3,4. step 6.

Find the edges e j := (i, j) kj and the vectors b j := a k ja kj for j ∈ N \ T . step 7.

If one of this vector say b j = a k ja kj is the null vector, set K := K ∪ {k j }, K := K \ {k j } and go to step 2. else set K := {k 1 , . . . , k n } and let K 1 be the set of critical indices of K; apply the procedure described in lemma 2. Let K 2 ⊆ (K ∪ K ) \ {k j } for some k j ∈ K 1 be the positive basis obtained after application of this procedure; K := K 2 and go to step 2.

At the first iteration of the algorithm, all the elements of N are singletons and K 1 = K. Thus, the triplet associated to the initial basis is (n, (n -1) ×