Martha Salazar-Neumann
email: msalazar@ulb.ac.be

The robust shortest path and the single-source shortest path problems : interval data

Keywords: Plus court chemin robuste, modélisation de l'incertitude Minimax regret optimization, Robust shortest path problem, uncertainty modeling, arc problem

Cet article traite de deux problèmes combinatoires robustes. Le premier concerne une version robuste du plus court chemin entre deux nøeuds préfixés 1 et m (trouver un plus court chemin robuste). Le second porte sur les chemins robustes entre un nøeud fixé et tous les autres. Dans ces deux problèmes, les coûts (ou longueurs) des arcs sont modélisés par des intervalles. On énonce des conditions suffisantes permettant de déterminer des arcs dits dits forts ou faibles appartenant ou non au plus court chemin robuste.

Introduction

The first problem that we consider is the robust deviation version of the problem to find a path of minimum weight connecting two specified nodes 1 and m,robust deviation shortest path problem on finite directed graphs under arc length uncertainties. We model data uncertainty by treating the arc lengths as nonnegative interval numbers, where each arc length can take any value in its interval.

In Zielinski [START_REF] Zielinski | The computational complexity of the relative robust shortest path problem with interval data[END_REF] this problem is shown to be NP-hard and to remain NP-hard even when a graph is restricted to be directed acyclic planar and regular of degree three.

In Averbakh et al. [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF] authors prove that this problem is strictly NP-hard for acyclic directed graphs. Then in solving this problem, reducing the solution space becomes an important issue. In [START_REF] Karasan | The robust shortest path problem with interval data[END_REF] authors show that for each optimal solution p of the robust deviation shortest path problem there exists a scenario s for which p is an optimal solution of the deterministic problem corresponding to the scenario s.

They show also that knowing those arcs which are never on shortest paths we can preprocess a graph prior to solution of the robust path problem. They study the arc problems on acyclic directed graphs and present a procedure to check whether an arc incident at nodes 1 or m is weak or not. Then authors give a necessary condition for an arc to be non-weak give a procedure to determine if an intermediate arc is non-weak and propose a mixed integer programming approach with preprocessing for the problem. First, the mixed integer program is preprocessed by removing some arcs which will never be in an optimal path, and then it is solved by standard software. They show by computational results that preprocessing of graphs is an efficient method in solving the robust deviation path problem. Montemani et al. [START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF], provide a branch and bound algorithm to solve the robust deviation path problem but they do not implement the preprocessing proposed in [START_REF] Karasan | The robust shortest path problem with interval data[END_REF] because in practice it can be used only for acyclic layered graphs with small width.

Another way to reduce the solution space, is by detecting the arcs that are always on a shortest path from 1 to m. In Karasan et al. [START_REF] Karasan | The robust shortest path problem with interval data[END_REF] authors study the robust deviation shortest path problem with interval data, unfortunately, no algorithm to detect the arcs that are always on the solution is given.

In another well-known robust combinatorial problem, the robust deviation spanning tree problem with interval data, Yaman et al. [START_REF] Yaman | The robust spanning tree problem with interval data Oper[END_REF] present a mixed integer programming formulation with preprocessing for the problem. The preprocessing removes the non-weak edges and sets the variables corresponding to the strong edges equal to 1. They show by computational results that knowing non-weak and strong edges helps shorten significantly the computation of the robust deviation solution. In Salazar-Neumann [START_REF] Salazar-Neumann | The robust minimum spanning tree problem: compact and convex uncertainty Operations[END_REF] characterizations of strictly strong and non-weak edges for the robust deviation spanning tree problem with compact and convex uncertainty are given, and in the case of polyhedral uncertainty we give polynomial time recognition algorithms.

In this work we study the arc problem on a larger class of graphs, finite directed graphs. We give sufficient conditions for an arc to be always or never on a shortest path from 1 to m (strictly strong arcs and non weak arcs respectively ). We present polynomial time algorithms to find some strictly strong arcs and some non weak arcs.

The second problem that we consider is the robust version of the problem to find shortest paths from a fixed node 1 to all the remaining nodes of G, the single-source shortest path problem. We give sufficient conditions for an arc (k, r) to be always ( for all realization of data) on a shortest path from 1 to r ( T-strictly strong arcs) and a characterization of the arcs that are never on a shortest path from 1 to another node of G (non T-weak arcs). Finally, we present polynomial time algorithms to find some T-strictly strong arcs and all the non T-weak arcs.

In [START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF] authors mention two important applications of this problem ; "the transportation problems that are usually represented as a weighted digraph, where each arc is associated with a road and costs represent travel times. A shortest path problem has to be solved every time the quickest way to go from one place to another has to be calculated. A similar problem arises in telecomunications when a packet has to be sent from a source node to a destination node on a network. Also in this case, where the network is usually modeled as a weighted digraph and costs are associated with transmission delays, a shortest path problem is faced. In reality it is not easy to estimate arc costs exactly. To overcome this problem, the interval data model is an alternative".

Notation and definitions

Most of the following definitions can be found in [START_REF] Bondy | Graph Theory with applications[END_REF]. Let G be a finite directed graph, we denote by V (G) and A(G), the set of nodes and arcs of G respectively, we suppose that | V (G) |= m, | A(G) |= n. We consider two special nodes of G, the origin node 1 and the destination node m. We denote by (i, j) the arc from node i to node j. Let A ′ be a nonempty subset of A(G), the subgraph of G with edge set A(G) \ A ′ is written simply as G -A ′ ; it is the subgraph obtained from G by deleting the arcs in

A ′ . If A ′ = {(i, j)} we write G -(i, j) instead of G -{(i, j)}.
Consider the following deterministic problem called shortest path problem on digraphs : Given G and nonnegative length l ij associated with each arc (i, j) ∈ A, we want to find a shortest directed path connecting two specified nodes 1 and m, where the length of a path is the sum of the lengths of its arcs. An efficient O(| V | 2 ) algorithm to solve this problem was given by Dijkstra. It finds not only a shortest (1,m)-path, but shortest paths from 1 to all nodes of G.

We will use some notations given in [START_REF] Karasan | The robust shortest path problem with interval data[END_REF]. Let S be the set of scenarios for the lengths of the arcs of G and let D be the set of our input data. We denote by l s ij the nonnegative length of the arc (i, j) in the scenario s and we will assume that D is a Cartesian product of intervals, that is to say, each l s ij can take an arbitrary value in the interval [l ij , l ij ]. We denote by s the scenario for which for all (i, j) ∈ A, l s ij = l ij and by s the scenario for which for all (i, j) ∈ A, l s ij = l ij . We denote by P 1 (G) the set of all the 1-paths of G, by P * 1 (G, s) the set of all shortest 1-paths of G under the scenario s and by P 1j (G) the set of all (1,j)-paths of G. For a path p ∈ P 1j (G) we denote by A(p) the set of arcs of p.

To evaluate a path p ∈ P 1 (G) under the scenario s we use a function f :

P 1 (G)×D → R : (p, l s ) → f (p, l s ) .
In this work we assume that this function is the sum of the lengths of the arcs of p under the scenario s.

f (p, l s ) = (i,j)∈A(p) l s ij .
By simplicity we will denote by l s p the length of path p in the scenario s. In the case where we want to find a shortest directed path connecting two specified nodes 1 and m. We define ;

f (p * s , l s ) = min p∈P 1m (G) f (p, l s )
The first problem that we will consider in this work is the robust version of the shortest path from 1 to m problem on digraphs under arc length uncertainties. The following definition can be found in the book [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF] .

ROBUST DEVIATION : The robust deviation path p d is such that

max s∈S (f (p d , l s ) -f (p * s , l s )) = min p∈P 1m (G) max s∈S (f (p, l s ) -f (p * s , l s )) where p * s ∈ P * 1m (G, s). A worst deviation scenario for a path p ∈ P 1m (G) is a scenario s in which f (p, l s ) - f (p * s , l s
), the difference between the cost of the (1,m)-path p and the cost of a shortest path from 1 to m in this scenario is maximum.

The following three definitions can be found in [START_REF] Karasan | The robust shortest path problem with interval data[END_REF] ; Definition A path is said to be a weak path if it is a shortest path from 1 to m for at least one realization of arc lengths.

Definition An arc is a weak arc if it lies on some weak path.

Definition An arc is a strong arc if it lies on a shortest path from 1 to m for all scenario.

Now we introduce the following definition ;

Definition An arc is a strictly strong arc if it lies on all shortest path from 1 to m for all scenario.

The second problem that we will consider is the robust version of the problem to find shortest paths from a fixed node 1 to all the remaining nodes of G, the robust single-source shortest path problem. We consider this problem on digraphs under nonnegative arc length uncertainties. We call a feasible solution of the deterministic problem a spanning 1-tree, an optimal solution a minimum spanning 1-tree of G and a shortest path from 1 to another node of G a shortest 1-path.

We denote by T 1 (G) the set of all the spanning 1-trees of G, by T * 1 (G, s) the set of all minimum spanning 1-trees of G under the scenario s. For a spanning 1-tree T ∈ T 1 (G) we denote by A(T ) the set of arcs of T .

To evaluate a spanning 1-tree T ∈ T 1 (G) under the scenario s we use a function

F : T 1 (G) × D → R : (T, l s ) → F (T, l s ) . Where F (T, l s ) = (i,j)∈A(T ) l s ij .
By simplicity we will denote by l s T the length of a 1-tree T in the scenario s. We define ;

F (T * s , l s ) = min T ∈T 1 (G) F (T, l s )
ROBUST DEVIATION : The robust deviation spanning 1-tree T d is such that

max s∈S (F (T d , l s ) -F (T * s , l s )) = min T ∈T 1 (G) max s∈S (F (T, l s ) -F (T * s , l s ))
where

T * s ∈ T * 1 (G, s). A worst deviation scenario for a 1-tree T ∈ T 1 (G) is a scenario s in which F (T, l s ) - F (T * s , l s
), the difference between the cost of the spanning 1-tree T and the cost of a minimum spanning 1-tree in this scenario is maximum.

In order to deal with the robust single-source shortest path problem we introduce the following concepts ; Definition A path p ∈ P 1 (G) is said to be a T-weak path if p is a shortest 1-path for at least one realization of arc lengths. Definition An arc (i, j) is a T-strictly strong arc if it lies on all shortest path from 1 to j for all scenario.

Remark We observe that an arc is a non T-weak arc, if and only if it never lies on a minimum spanning 1-tree and an arc is a T-strictly strong arc if and only if it lies on all minimum spanning 1-tree for all scenario.

The robust shortest path problem : strictly strong and non-weak arcs

The following proposition give a characterization of the strictly strong arcs.

Proposition 1 Let (k, r) be such that on the graph G -(k, r) the node m is reachable from the node 1. For each s ∈ S let p * s ∈ P * 1m (G, s). The arc (k, r) is a strictly strong arc of G if and only if for all q ∈ P 1m (G -(k, r)) and for all s ∈ S, l s q > l s p * s Proof : Let (k, r) be such that on the graph G -(k, r) the node m is reachable from the node 1. If (k, r) is a strictly strong arc of G and q ∈ P 1m (G -(k, r)), then q is not a shortest path of G from 1 to m for each scenario s, and consequently for all s ∈ S, l s q > l s p * s . Now, if for all q ∈ P 1m (G -(k, r)) and for all s ∈ S, l s q > l s p * s , then q is never a shortest path of G from 1 to m for each scenario s, so for all s ∈ S a shortest path of G from 1 to m under the scenario s contains the arc (k, r), and (k, r) is then an strictly strong arc.

Remark Let (k, r) be such that there exist p ∈ P 1m (G) such that (k, r) ∈ A(p) and on the graph G -(k, r) the node m is not reachable from the node 1, then the arc (k, r) is a strictly strong arc.

We can observe that in the last characterization of the strictly strong arcs, the number of extreme scenarios can be exponential, then in the next theorem we will give a sufficient condition easy to test for an arc to be strictly strong. We will use the last proposition on the proof.

Theorem 1 Let G(V, A) be a finite directed graph, with origin node 1 and destination node m. We suppose that each node j ∈ V (G) is reachable from the node 1. Let p be the shortest path from 1 to m found by Dijkstra algorithm under the scenario s. Let (k, r) ∈ A(p), and let s ′ the scenario such that,

l s ′ ij = l ij if (i, j) ∈ A(p), and
l s ′ ij = l ij if (i, j) / ∈ A(p). If on the graph G -(k, r) the node m is reachable from the node 1, let q ′ ∈ P * 1m (G -(k, r), s ′ ) be a shortest path from 1 to m under the scenario s ′ . If l s ′ q ′ > l s ′ p
then the arc (k, r) is a strictly strong arc.

Proof : Let p be the shortest path from 1 to m found by Dijkstra algorithm under the scenario s, let (k, r) ∈ A(p). Now consider the scenario s ′ such that l s ′ ij = l ij if (i, j) ∈ A(p), and l s ′ ij = l ij if (i, j) / ∈ A(p). Let q ′ a shortest path of G -(k, r) from 1 to m under the scenario s ′ . If l s ′ q ′ > l s ′ p then for all q ∈ P 1m (G -(k, r)) l s ′ q ≥ l s ′ q ′ > l s ′ p and then for all q ∈ P 1m (G -(k, r))

(i,j)∈q\p l ij = (i,j)∈q\p l s ′ ij > (i,j)∈p\q l s ′ ij = (i,j)∈p\q l ij
and then for all s ∈ S (i,j)∈q\p

l s ij ≥ (i,j)∈q\p l ij > (i,j)∈p\q l ij ≥ (i,j)∈p\q l s ij
this implies that for all s ∈ S and for all q ∈ P 1m (G -(k, r)), we have l s q > l s p and if p * s ∈ P * 1m (G, s), l s q > l s p ≥ l s p * s . By proposition 1, (k, r) is a strictly strong arc. Theorem 1 allow us to derive a polynomial time algorithm to find some strictly strong arcs. An algorithm to find some non-weak arcs is presented in the following section.

Choose an arc (k, r) ∈ A(p).

Construct the scenario s

′ for which l s ′ ij = l ij if (i, j) ∈ A(p), and l s ′ ij = l ij if (i, j) / ∈ A(p).
4. Apply Dijkstra to G -(k, r) under the scenario s ′ . If there exists a shortest path q ′ from 1 to m, go to step 5. Otherwise (k, r) is strictly strong.

5. Compute l s ′ q ′ and l s ′ p . 6. If l s ′ q ′ > l s ′ p then the arc (k, r) is a strictly strong arc. 7. Go to step 2. Choosing another arc in A(p) and continue.

Example 1 To clarify the above procedure, we apply it on the first graph given in Figure 1. We set the lengths of all the arcs to their upper bounds and we find a shortest path p from the node 1 to the node m, we represent such path with bold lines. We construct the scenario s ′ setting the arcs (1, a) and (a, m) to their upper bounds and the lengths of the remaining arcs to their lower bounds. We delete the arc (1, a) ∈ A(p) and we apply Dijkstra to G -(1, a) under the scenario s ′ . As there exists a shortest path q ′ from 1 to m, we compute l s ′ q ′ = 7 and l s ′ p = 6. As l s ′ q ′ > l s ′ p then the arc (1, a) is a strictly strong arc. Then we take the second arc (a, m) of p, we delete the arc (1, a) ∈ A(p) and we apply Dijkstra to G -(a, m) under the scenario s ′ . As there exists a shortest path q ′ from 1 to m, we compute l s ′ q ′ = 6 and l s ′ p = 6. As l s ′ q ′ = l s ′ p we have not a conclusion for the arc (a, m).

The robust single-source shortest path problem : Tstrictly strong and non T-weak arcs

The following proposition give a characterization of the T-strictly strong arcs.

Proposition 2 Let (k, r) ∈ A(G) be such that on the graph G -(k, r) the node r is reachable from the node 1. For each s ∈ S let p * s ∈ P * 1r (G, s). The arc (k, r) is a T-strictly strong arc of G if and only if for all q ∈ P 1r (G -(k, r)) and for all s ∈ S, l s q > l s p * s . Proof : Let (k, r) be such that on the graph G -(k, r) the node r is reachable from the node 1. If (k, r) is a T-strictly strong arc of G and q ∈ P 1r (G -(k, r)), then q is not a shortest path of G from 1 to r for each scenario s, and then for all s ∈ S, l s q > l s p * s . Now if for all q ∈ P 1r (G -(k, r)) and for all s ∈ S, l s q > l s p * s then q is never a shortest path of G from 1 to r for each scenario s, so for all s ∈ S a shortest path of G from 1 to r under the scenario s contains the arc (k, r), then (k, r) is an T-strictly strong arc.

Remark Let (k, r) be such that there exist p ∈ P 1r (G) such that (k, r) ∈ A(p) and on the graph G -(k, r) the node r is not reachable from the node 1, then the arc (k, r) is a T-strictly strong arc.

FIG. 2 -T-strictly strong arcs algorithm

On the last proposition, the number of extreme scenarios can be very large, and in that case we can apply the next theorem that give a sufficient condition easy to test for an arc to be T-strictly strong. The proof of next theorem uses the proposition 2.

(i,j)∈q\p l s ij ≥ (i,j)∈q\p l ij > (i,j)∈p\q l ij ≥ (i,j)∈p\q l s ij
this implies that for all s ∈ S and for all q ∈ P 1r (G -(k, r)), if p * s ∈ P * 1r (G, s), l s q > l s p ≥ l s p * s and then by proposition 2, (k, r) is a T-strictly strong arc. The following proposition give a characterization of the non T-weak arcs.

Proposition 3 For each s ∈ S let p * s ∈ P * 1k (G, s). The arc (k, r) is a non T-weak arc of G if and only if for each s ∈ S there exist a path q ∈ P 1r (G), such that l s q < l s p * s + l kr . Proof : Let (k, r) be a non T-weak arc of G, then for all p * s ∈ P * 1k (G, s), p * s + (k, r) is never a shortest path of G from 1 to r, so for all s ∈ S there exists a path q ∈ P 1r (G) such that l s q < l s p * s + l kr . Now if for all s ∈ S, exists a path q ∈ P 1r (G) such that the inequality ; l s q < l s p * s + l kr holds, then for all p ∈ P 1k (G) l s q < l s p * s + l kr ≤ l s p + l s kr then all path of G from 1 to r that use the arc (k, r) is never a shortest path from 1 to r for the scenario s ∈ S, then the arc (k, r) is a non T-weak arc.

The following theorem give another characterization easy to test for an arc to be a non T-weak arcs.

Theorem 3 Let G(V, A) be a finite directed graph, with origin node 1. We suppose that each node j ∈ V (G) is reachable from the node 1. Let T the directed tree found by Dijkstra algorithm under the scenario s and let (k, r) ∈ A \ A(T ). Let p ∈ P 1k (G) such that A(p) ⊂ A(T ). Let s ′ be the scenario for which, l s ′ kr = l kr , l s ′ ij = l ij if (i, j) ∈ A(p), and l s ′ ij = l ij if (i, j) / ∈ A(p) and (i, j) = (k, r). Let q ′ be a shortest path of G from 1 to r for the scenario s ′ . An arc (k, r) is a non T-weak arc if and only if l s ′ q ′ < l s ′ p + l kr . Proof : Let T be the directed tree found by Dijkstra algorithm under the scenario s, let (k, r) ∈ A \ A(T ), and let p ∈ P 1k (G) such that A(p) ⊂ A(T ), then p is a shortest path of G from 1 to k under the scenario s. Consider the scenario s ′ described before and let q ′ ∈ P * 1r (G, s ′ ).

If l s ′ q ′ < l s ′ p + l kr (i,j)∈q ′ \p l s ij ≤ (i,j)∈q ′ \p l ij = (i,j)∈q ′ \p l s ′ ij < (i,j)∈p\q ′ l s ′ ij + l kr then l s q ′ < l s ′ p + l kr but l s ′ p = l s p ≤ l s p *
s then for all s ∈ S l s q ′ < l s ′ p + l kr ≤ l s p * s + l kr and by proposition 8 that implies that (k, r) is a not T-weak arc. Now suppose that the arc (k, r) is a non T-weak arc then by the proposition 8, for each s ∈ S there exist a path q ∈ P 1r (G), such that l s q < l s p * s + l kr . In particular for the scenario s ′ there exists a path q ∈ P 1r (G), such that l s ′ q < l s ′ p * s ′ + l kr . Consider the shortest path q ′ from 1 to r under the scenario s ′ (q ′ ∈ P * 1r (G)) then

l s ′ q ′ ≤ l s ′ q < l s ′ p * s ′ + l kr ≤ l s ′ p + l kr
and we have the result.

Remark All the non T-weak arcs are non-weak arcs.

The last two theorems allow us to derive polynomial time algorithms to find some T-strictly strong arcs all the non T-weak arcs and some non-weak arcs ;

Algorithm to find some T-strictly strong arcs 1. Apply Dijkstra algorithm to G under the scenario s to obtain T .

2. Choose an arc (k, r) ∈ A(T ).

3. We consider the path p ∈ P 1r (G) such that A(p) ⊂ A(T ).

Construct the scenario s

′ for which l s ′ ij = l ij if (i, j) ∈ A(p), and
l s ′ ij = l ij if (i, j) / ∈ A(p).
5. Apply Dijkstra to G -(k, r) under the scenario s ′ . If there exists a shortest path q ′ from 1 to r, go to step 5. Otherwise (k, r) is T-strictly strong.

6. Compute l s ′ q ′ and l s ′ p . 7. If l s ′ q ′ > l s ′ p then the arc (k, r) is a T-strictly strong arc. 8. Go to step 2. Choosing another arc in A(T ) and continue.

Example 2 To clarify the above procedure, we apply it on the first graph given in Figure 2. We set the lengths of all the arcs to their upper bounds and we find shortest paths from the node 1 to all nodes of G. We represent such tree T with bold lines. We choose the arc (a, b) and we construct the scenario s ′ setting the arcs (1, a), and (a, b) to their upper bounds and the lengths of the remaining arcs to their lower bounds. We delete the arc (a, b) ∈ A(p) and we apply Dijkstra to G -(a, b) under the scenario s ′ . As there exists a shortest path q ′ from 1 to b, we compute l s ′ q ′ = 5 and l s ′ p = 4. As l s ′ q ′ > l s ′ p then the arc (a, b) is a T-strictly strong arc. Then we take a second arc (a, m) of T , we construct the scenario s ′ setting the arcs (1, a), and (a, m) to their upper bounds and the lengths of the remaining arcs to their lower bounds. We delete the arc (a, m) ∈ A(T ) and we apply Dijkstra to G -(a, m) under the scenario s ′ . As there exists a shortest path q ′ from 1 to m, we compute l s ′ q ′ = 6 and l s ′ p = 6. As l s ′ q ′ = l s ′ p then we have not a conclusion for the arc (a, m).

Algorithm to find all the non T-weak arcs and some non weak arcs.

1. Apply Dijkstra algorithm to G under the scenario s to obtain T .

Choose an arc (k, r) ∈ A \ A(T ).

3. Consider the path p ∈ P 1k (G) such that A(p) ⊂ A(T ).

Construct the scenario s

′ for which l s ′ kr = l kr , l s ′ ij = l ij if (i, j) ∈ A(p), and l s ′ ij = l ij if (i, j) /
∈ A(p) and (i, j) = (k, r).

5.

Apply Dijkstra to G under the scenario s ′ to obtain q ′ a shortest path from 1 to r.

6. Compute l s ′ q ′ and l s ′ p . 7. If l s ′ q ′ < l s ′ p + l kr then the arc (k, r) is a non T-weak arc and then a non weak arc. Otherwise (k, r) is a T-weak arc.

Example 3 To clarify the above procedure, we apply it on the first graph given in Figure 3. We set the lengths of all the arcs to their lower bounds and we find shortest paths from the node 1 to all nodes of G. We represent such tree T with bold lines. We choose the arc (b, a) ∈ A(T ) and we consider a path p ∈ P 1b (G) such that A(p) ⊂ A(T ). We construct the scenario s ′ setting the arcs (b, a), and (1, a) to their lower bounds and the lengths of the remaining arcs to their upper bounds. We apply Dijkstra to G under the scenario s ′ to obtain a shortest path q ′ from 1 to a, we compute l s ′ q ′ = 1, l s ′ p = 3 and l ba = 4. As l s ′ q ′ < l s ′ p +l ba then the arc (b, a) is a non T-weak arc. Then we take a second arc (1, b) ∈ A(T ) and we consider a path p ∈ P 11 (G) such that A(p) ⊂ A(T ). We construct the scenario s ′ setting the arc (1, b), to their lower bound and the lengths of the remaining arcs to their upper bounds. We apply Dijkstra to G under the scenario s ′ to obtain a shortest path q ′ from 1 to b, we compute l s ′ q ′ = 4, l s ′ p = 0 and l 1b = 5. As l s ′ q ′ < l s ′ p + l 1b then the arc (1, b) is a non T-weak arc. Finally we choose the arc (b, m) ∈ A(T ) and we consider a path p ∈ P 1b (G) such that A(p) ⊂ A(T ). We construct the scenario s ′ setting the arcs (b, a), and (1, a) to their lower bounds and the lengths of the remaining arcs to their upper bounds. We apply Dijkstra to G under the scenario s ′ to obtain a shortest path q ′ from 1 to m, we compute l s ′ q ′ = 5, l s ′ p = 3 and l bm = 2. As l s ′ q ′ = l s ′ p + l ba then the arc (b, m) is a T-weak arc.

Conclusions and extensions :

We have given sufficient conditions for an arc (k, r) to be always on an optimal solution of the robust shortest path and for the single-source shortest path problems (strictly strong arcs and T-strictly strong arcs resp.) and for an arc to be never on an optimal solution (non weak arcs and non T-weak arcs resp.). Such conditions are based on the topology of the graph combined with the structure of the data set. Based on these results we have presented polynomial time recognition algorithms that can be used to preprocess a given graph with interval data prior to the solution of the robust problem. In [START_REF] Karasan | The robust shortest path problem with interval data[END_REF] was shown that such type of preprocessing procedures are quite effective in reducing the time to compute the solution of the robust deviation path problem.

FIG. 1 -

 1 FIG. 1 -Strictly strong arcs algorithm

FIG. 3 -

 3 FIG. 3 -Non T-weak arcs algorithm

FutureFIG. 4 -

 4 FIG. 4 -Classification of the arcs

Theorem 2 Let G(V, A) be a finite directed graph, with origin node 1. Let T the directed tree found by Dijkstra algorithm under the scenario s, and let (k, r) ∈ A(T ). Let p ∈ P 1r (G) such that A(p) ⊂ A(T ). Let s ′ be the scenario for which

) the node r is reachable from the node 1, let q ′ ∈ P * 1r (G -(k, r), s ′ ) be a shortest path from 1 to r under the scenario s ′ . If l s ′ q ′ > l s ′ p then the arc (k, r) is a T-strictly strong arc. Proof : Let T be the directed tree found by Dijkstra algorithm under the scenario s, let (k, r) ∈ A(T ), and let p ∈ P 1r (G) such that A(p) ⊂ A(T ). We observe that p is a shortest path of G from 1 to r under the scenario s.

Now consider the scenario s

p then for all q ∈ P 1r (G -(k, r)) l s ′ q ≥ l s ′ q ′ > l s ′ p and then for all q ∈ P 1r (G -(k, r))

and then for all s ∈ S


Golnaz Badkobeh
email: golnaz.badkobeh@googlemail.com

Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Computing maximal-exponent factors in an overlap-free word ✩

Keywords: Word, string, repetition, power, repeat, periodicity, word exponent, return word, algorithm, automaton. 2000 MSC: 68W40, 68R15, 68Q45

The exponent of a word is the quotient of its length over its smallest period. The exponent and the period of a word can be computed in time proportional to the word length. We design an algorithm to compute the maximal exponent of all factors of an overlap-free word. Our algorithm runs in linear-time on a fixed-size alphabet, while a naive solution of the question would run in cubic time. The solution for non overlap-free words derives from algorithms to compute all maximal repetitions, also called runs, occurring in the word.

We also show there is a linear number of occurrences of maximal-exponent factors in an overlap-free word. Their maximal number lies between 0.66n and 2.25n in a word of length n. The algorithm can additionally locate all of them in linear time.

Introduction

We consider the question of computing the maximal exponent of factors (substrings) of a given word (string). The exponent of a word is the quotient of the word length over the word smallest period. For example alfalfa has period 3 and exponent 7/3, and restore has period 5 and exponent 7/5.

A word with exponent e is also called an e-power. The exponent indicates better than the period the degree of repetitiveness of factors occurring in a word.

In this article we focus on factors whose exponent is at most 2. Such factors can uniquely be written as uvu where u is the longest border of uvu, that is, the longest proper prefix that is also a suffix of the factor. Note that the exponent is 1 if and only if u is the empty word, while it is 2 if and only if v is the empty word. Consistently with the existing literature a word whose exponent is 1, the minimal possible exponent, admits only the empty word as a border and is called border-free. A word is called a square when its exponent is a positive even integer. In this article, a factor whose exponent is smaller than 2 is called a repeat, while a factor whose exponent is at least 2 is called a repetition or a periodic factor. In other words, in the former case the factor u repeats at two distant positions.

The study of repeats in a word is relevant to long-distance interactions between separated occurrences of the same segment (the u part) in the word.

Although occurrences may be far away from each other, they may interact when, for example, the word is folded as it is the case for genomic sequences.

A very close problem to considering those repeats is that of computing maximal pairs (positions of the two occurrences of u) with gaps constraints as described by Gusfield [START_REF] Gusfield | Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology[END_REF] and later improved by Brodal et al. [START_REF] Brodal | Finding maximal pairs with bounded gap[END_REF].

From a combinatorial point of view, the question is related to return words: z is a return word associated with u if u is a prefix of zu and u has no internal occurrence in zu. For instance, if u has only two occurrences in uvu (as a prefix and a suffix) then uv is a return word for u. The word then links two consecutive occurrences of u. The analysis of return words provide characterisations for word morphisms and infinite words. For example, a binary infinite Sturmian word, generalisation of Fibonacci word, is characterised by the fact that every factor (occurring infinitely many times) admits exactly two return words (see [START_REF] Vuillon | A characterization of Sturmian words by return words[END_REF] and references therein).

The notion of maximal exponent is central to questions related to the avoidability of powers in infinite words. An infinite word is said to avoid e-powers (resp. e + -powers) if the exponents of its finite factors are smaller than e (resp. no more than e). Dejean [START_REF] Dejean | Sur un théorème de Thue[END_REF] introduced the repetitive threshold RT(a) of an a-letter alphabet: the smallest rational number for which there exists an infinite word on a letters whose finite factors have exponent at most RT(a). In other words, the maximal exponent of factors of such a word is RT(a), the minimum possible. The word is also said to be RT(a) + -power free.

It is known from Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF] that r(2) = 2, Dejean [START_REF] Dejean | Sur un théorème de Thue[END_REF] proved that r(3) = 7/4 and stated the exact values of RT(a) for every alphabet size a > 3. Dejean's conjecture was eventually proved in 2009 after partial proofs given by several authors (see [START_REF] Rao | Last cases of Dejean's conjecture[END_REF][START_REF] Currie | A proof of Dejean's conjecture[END_REF] and references therein).

The exponent of a word can be calculated in linear time using basic string matching that computes the smallest period associated with the longest border of the word (see [START_REF] Crochemore | Algorithms on Strings[END_REF]). A straightforward consequence provides a O(n 3 )time solution to compute the maximal exponent of all factors of a word of length n since there are potentially of the order of n 2 factors. However, a quadratic time solution is also a simple application of basic string matching.

By contrast, our solution runs in linear time on a fixed-size alphabet.

When a word contains runs, that is, maximal periodicities of exponent at least 2, computing their maximal exponent can be achieved in linear time by adapting the algorithm of Kolpakov and Kucherov [START_REF] Kolpakov | On maximal repetitions in words[END_REF] that computes all the runs occurring in the word. Their result relies on the fact that there exists a linear number of runs in a word [START_REF] Kolpakov | On maximal repetitions in words[END_REF] (see [START_REF] Rytter | The number of runs in a string[END_REF][START_REF] Crochemore | The "runs" conjecture[END_REF] for precise bounds). Nevertheless, this does not apply to square-free words, which we are considering here.

Our solution works indeed on overlap-free words, not only on square-free words, that is, on words whose maximal exponent of factors is at most 2. Thus, we are looking for factors w of the form uvu, where u is the longest border of w. In order to accomplish this goal, we exploit two main tools: the Suffix Automaton of some factors and a specific factorisation of the whole word.

The Suffix Automaton (see [START_REF] Crochemore | Algorithms on Strings[END_REF]) is used to search for maximal-exponent factors in a product of two words due to its ability to locate occurrences of all factors of a pattern. Here, we enhance the automaton to report the rightmost occurrences of those factors. Exploiting only the Suffix Automaton in a balanced divide-and-conquer manner produces a O(n log n)-time algorithm.

In order to eliminate the log factor we additionally exploit a word factorisation, namely the f-factorisation (see [START_REF] Crochemore | Algorithms on Strings[END_REF]), a type of LZ77 factorisation (see [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF]) fit for word algorithms. It has now become common to use this factorisa-tion to derive efficient or even optimal algorithms. The f-factorisation allows one to skip larger and larger parts of the words during an online processing.

For our purpose, it is composed of factors occurring before their current position with no overlap. The factorisation can be computed in O(n log a)-time (where a is the alphabet size) using a Suffix Tree or a Suffix Automaton, and in linear time on an integer alphabet using a Suffix Array [START_REF] Crochemore | Computing longest previous nonoverlapping factors[END_REF].

The running time of the proposed algorithm depends additionally on the repetitive threshold of the underlying alphabet size of the word. The threshold restricts the context of the search for a second occurrence of u associated with a factor uvu.

We show a very surprising property of factors whose exponent is maximal in an overlap-free word: there are no more than a linear number of occurrences of them, although the number of occurrences of maximal (i.e. non-extensible) factors can be quadratic.

We show a lower bound of 0.66n and an upper bound of 2.25n on their maximal number for a word of length n. They improve on the bounds given in a preliminary version [START_REF] Badkobeh | Computing the maximalexponent repeats of an overlap-free string in linear time[END_REF] of the article. The lower bound is based on a result of Pansiot [START_REF] Pansiot | A propos d'une conjecture de F. Dejean sur les répétitions dans les mots[END_REF] on the repetitive threshold of four-letter alphabets.

As a consequence, the algorithm can be modified to output all occurrences of maximal-exponent factors of an overlap-free word in linear time.

The question would have a simple solution by computing MinGap on each internal node of the Suffix Tree of the input word, as is discussed in the conclusion. MinGap of a node is the smallest difference between the positions assigned to leaves of the subtree rooted at the node. Unfortunately, the best algorithms for MinGap computation, equivalent to MaxGap computation, run in time O(n log n) (see [START_REF] Berkman | The subtree max gap problem with application to parallel string covering[END_REF][START_REF] Iliopoulos | Covering a string[END_REF][START_REF] Brodal | Finding maximal quasiperiodicities in strings[END_REF] and the discussion in [START_REF] Christou | Efficient seeds computation revisited[END_REF]).

A remaining question to the present study is to unify the algorithmic approaches for locating runs in non overlap-free words and maximal-exponent factors in overlap-free words.

The plan of the article is as follows. After defining the problem in the next section we present the general scheme of the algorithm that relies on the f-factorisation of the input word in Section 3. The sub-function operating a Suffix Automaton is described in Section 4 and the complexity of the complete algorithm is studied in Section 5. In Section 6 we prove lower and upper bounds on the number of occurrences of maximal-exponent factors. A conclusion follows.

Maximal-exponent factors

We consider words (strings) on a finite alphabet A of size a. If x is a word of length |x| = m, x[i] denotes its letter at position i, 0 ≤ i < m. A factor of x is of the form x[i]x[i + 1] . . . x [j] for two positions i and j and is denoted by x[i . . j] (it is the empty word if j < i). It is a prefix of x if i = 0 and a suffix of x if j = m -1.

The word x has period p, 0 < p ≤ m, if x[i] = x[i + p] whenever both sides of the equality are defined, i.e. for i = 0, . . . , m-p-1. The period of x, period(x), is its smallest period and its exponent is exp(x) = m/period(x).

For example, exp(restore) = 7/5, exp(mama) = 2 and exp(alfalfa) = 7/3.

An overlap-free word contains no factor of exponent larger then 2, that is, no factor of the form bwbwb for a letter b and a word w.

We consider a fixed overlap-free word y of length n and deal with its factors having the maximal exponent among all factor exponents. They are called maximal-exponent factor or MEF for short. They have exponent at most 2 since y is overlap-free.

A MEF w in y is of the form uvu, where u is its longest border (longest factor that is both a prefix and a suffix of w). Then period(w) = |uv| and exp(w) = |uvu|/|uv| = 1 + |u|/period(w). By convention, in the following we allow a border-free factor to be considered as a MEF of exponent 1, though it contains no repeat in the common sense since the repeating element u is empty and it can appear only if no letter in y appears more than once, i.e. if its length is no more than the alphabet size.

First note that a MEF uvu contains only two occurrences of u since this would produce a factor with a larger exponent. Second, any occurrence of the MEF uvu is maximal in the sense that it cannot be extended with the same period. That is, the two occurrences of u are followed by two distinct letters and preceded by two distinct letters. These remarks are stated in Lemmas 3 and 2 respectively.

The maximality of occurrences of repetitions in non overlap-free words implies their linear number but unfortunately this property does not hold for MEF occurrences.

Computing the maximal exponent of factors

The core result of the article is an algorithm, MaxExpFac, that computes the maximal exponent of factors of the overlap-free word y. The algorithm has to look for factors of the form uvu, for two words u and v, u being (iii) the second occurrence of u is internal to

z 1 z 2 z i-1 z i u 1 u 1 (i) u 2 u 2 (ii) u 3 u 3 (ii) (iii) u 4 u 4 (iii) u 5 u 5 (iv)
z i ; (iv) the second occurrence of u is internal to z i-1 z i .
the longest border of uvu. The aim of this algorithm is accomplished with the help of Algorithm MaxExp, designed in the next section, which detects those factors occurring within the concatenation of two words.

Algorithm MaxExpFac relies on the f-factorisation of y, a type of LZ77 factorisation [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF] defined as follows. It is a sequence of non-empty words,

z 1 , z 2 , . . . , z k , called phrases and satisfying y = z 1 z 2 • • • z k where z i is the longest prefix of z i z i+1 • • • z k occurring in z 1 z 2 • • • z i-1 . When this longest prefix is empty, z i is the first letter of z i z i+1 • • • z k ,
thus it is a letter that does not occur previously in y. This definition is equivalent to the definition in [START_REF] Crochemore | Algorithms on Strings[END_REF], in which a phrase z i can overlap with its previous occurrence, because the word y is overlap-free. We adapt the factorisation to the purpose of our problem by defining z 1 as the longest prefix of y in which no letter occurs more than once. Then, |z 1 | ≤ a and MaxExpFac(z 1 ) = 1. Note that

MaxExpFac(z 1 z 2 ) > 1 if z 1 = y.
When the factorisation of y is computed, Algorithm MaxExpFac processes the phrases sequentially, from z 2 to z k . After z 1 , z 2 , . . . , z i-1 have been processed, the variable e stores the maximal exponent of factors of

z 1 z 2 • • • z i-1 .
Then, the next factors to be considered are those involving phrase z i . Such factors uvu can either be internal to z i or involve other phrases. However, the crucial property of the factorisation is that the second occurrence of u is only to be searched for in z i-1 z i because it cannot contain a phrase as this would contradict the definition of the factorisation.

We further distinguish four possible cases according to the position of the factor uvu as follows (see Figure 1):

(i) The two occurrences of u are contained in z i .

(ii) The first occurrence of u is contained in z i-1 and the second ends in z i .

(iii) The first occurrence of u starts in z i-1 and the second occurrence is contained in z i .

(iv) The first occurrence of u starts in z 1 (see [START_REF] Dejean | Sur un théorème de Thue[END_REF]).

MaxExpFac(y) 1 (z 1 , z 2 , . . . , z k ) ← f-factorisation of y 2 z 1 is the longest prefix of y in which no letter repeats 3 e ← 1 4 for i ← 2 to k do 5 e ← MaxExp(z i-1 , z i , e) 6 e ← MaxExp( z i , z i-1 , e) 7 if i > 2 then 8 e ← MaxExp( z i-1 z i , z 1 • • • z i-2 ,
Another technical remark is that the instruction at line 6 can be tuned to deal only with type (iii) factors of the form u 4 vu 4 (see Figure 1), i.e. factors for which the first occurrence of the border starts in z i-1 and ends in z i , because line 5 finds those of the form u 3 vu 3 . However, this has no influence on the asymptotic running time.

Theorem 1. For any overlap-free word input, MaxExpFac computes the maximal exponent of factors occurring in the word.

Proof. We consider a run of MaxExpFac(y). Let e 1 , e 2 , . . . , e k be the successive values of the variable e, where e i is the value of e just after the execution of lines 5-8 for index i. The initial value e 1 = 1 is the maximal exponent of factors in z 1 as a consequence of its definition. We show that e i is the maximal exponent of factors occurring in

z 1 z 2 • • • z i if e i-1 is that of z 1 z 2 • • • z i-1 , for 2 ≤ i ≤ k.
To do so, since e i is at least e i-1 (use of max at lines 5-8), all factors occurring in z 1 z 2 • • • z i-1 are taken into account and we only have to consider factors coming from the concatenation of z 1 z 2 • • • z i-1 with z i , that is, factors of the form uvu where the second occurrence of u ends in z i . As discussed above and illustrated in Figure 1, only four cases are to be considered because the second occurrence of u cannot start in

z 1 z 2 • • • z i-2 without contradicting the definition of z i-1 .
Line 5 deals with Case (ii) by the definition of MaxExp. Similarly, line 6 is for Case (iii), and line 8 for Case (iv).

If a factor occurs entirely in z i , Case (i), by the definition of z i it occurs also in

z 1 z 2 • • • z i-1 , which is reported by e i-1 .
Therefore, all relevant factors are considered in the computation of e i , which is then the maximal exponent of factors occurring in z 1 z 2 • • • z i . This implies that the exponent e k returned by the algorithm is the exponent of

z 1 z 2 • • • z k = y as stated.

Locating repeats in a product

In this section, we describe Algorithm MaxExp applied to (z, w, e) for computing the maximal exponent of factors in zw that end in w, whose left border occurs in z, and whose exponent is at least e. MaxExp is called in the main algorithm of the previous section.

To locate factors under consideration, the algorithm examines positions j on w and for each computes the longest potential border of a factor, a longest suffix u of zw[0 . . j] occurring in z. The algorithm is built upon an algorithm that finds all of them using the Suffix Automaton of word z.

The Suffix Automaton of z, denoted S(z), is used to locate borders of factors. It is the minimal deterministic finite automaton whose language is the set of suffixes of z (see [9, Section 6.6] for more description and for efficient construction). An example is given in Figure 2. The data structure has an initial state denoted initial(S) and a state called last(S) that is the accepting state of z itself (it is the only state with no outgoing arcs). In

L[0] = 0, L[1] = 1, L[2] = 2, L[3] = 3, L[4] = 4, L[5] = 5, L[6] = 6, L[7] = 7, L[8] = 8, L[9] = 9, L[10] = 1, L[11] = 1, L[12] = 2.
Minimal extension lengths:

sc[0] = 0, sc[1] = 0, sc[2] = 7, sc[3] = 6, sc[4] = 5, sc[5] = 4, sc[6] = 3, sc[7] = 2, sc[8] = 1, sc[9] = 0, sc[10] = 3, sc[11] = 1, sc[12] = 0.
contains the failure link F z and the length function L z , both defined on the set of states. The link is defined as follows: let p = goto(initial(S(z)), x) for

x ∈ A + ; then F z (p) = goto(initial(S(z)), x ), where x is the longest suffix of

x for which this latter state is not p. As for the length function, L z (p) is the maximal length of words x for which p = goto(initial(S(z)), x).

The next two lemmas show that, after u is located with the Suffix Automaton, although some of its suffixes may have an exponent higher than e, we can discard many of them. Proof. The hypothesis implies that the right-most occurrence of u ends at the same positions on z as u (see Figure 3). Then, u v u and uvu have the same period |vu| = |v u | but since u v u is not longer than uvu, the exponent of u v u is not greater than that of uvu.

z w 0 j (1) u v u (2) u v u
Note that a suffix u of u may have an internal occurrence in uvu, which would lead to a factor having a larger exponent. For example, let z = abadba and w = cdaba. The factor abadbacdaba with border aba has exponent 11/8

while the suffix ba of aba infers the factor bacdaba of greater exponent 7/5. The proof of the following lemma can be deduced from the remark in MaxExp to avoid some exponent calculations as follows. Let uvu be a factor ending at j on zw[0 . . j] and for which u is the longest word associated with state q = goto(initial(S), u), where goto is the transition function of the automaton. Then next occurrences of u and of any of its suffixes cannot produce factors with an exponent larger than that of uvu. State q is then marked to inform the next steps of the algorithm that it has been visited.

z w 0 j k (1) u v u (2) u v u
We need another function, sc z , defined on states of S(z) as follows:

sc z (p)
is the minimal length of paths from p to a terminal state; in other terms, if p = goto(initial(S(z)), x), then sc z (p) = |x | where x is the shortest word for which xx is a suffix of z. With this precomputed extra element, computing an exponent is a mere division (see Figure 5).

z 0 j a u v u - -

sc[q]

j + 1

Figure 5: The maximal exponent of all factors in question bordered by u, longest factor of z ending at j, is ( + sc[q] + j + 1)/(sc[q] + j + 1). Exponents of factors are given by the expression ( + sc[q] + j + 1)/(sc[q] + j + 1). The last line is for exponents corresponding to suffixes of u. The maximal exponent of all factors is 7/4.

MaxExp(z, w, e)

1 S ← Suffix Automaton of z 2 mark initial(S) 3 (q, ) ← (F [last(S)], L[F [last(S)]]) 4 for j ← 0 to min{ |z|/(e -1) -1 , |w| -1} do 5 while goto(q, w[j]) = NIL and q = initial(S) do 6 ( q, ) ← (F [q], L[F [q]]) 7

if goto(q, w[j]) = NIL then 8 ( q, ) ← (goto(q, w[j]), + 1) 9 ( q , ) ← (q, ) 10 while q unmarked do 11 e ← max{e, ( + sc[q ] + j + 1)/(sc Second, given a position j on w, we show that the algorithm examines all the possible concerned factors having an exponent at least e and ending at j.

[q ] + j + 1)} 12 if = L[q ] then 13 mark q 14 (q , ) ← (F [q ], L[F [q ]]) 15 return e
The following property related to variables q, state of S, and is known from [9, Section 6.6]: let u be the longest suffix of zw[0 . . j] that is a factor of z, then q = goto(initial(S), u) and = |u|. The property is also true just after execution of line 3 for z alone due to the initialisation of the two variables.

Then, word u is the border of a factor ending in w and whose left border occurs in z. Lines 9 to 14 check the exponents associated with u and its suffixes. If q is unmarked, the exponent is computed as explained before (see Figure 5). If the condition at line 11 is met, which means that u is the longest word satisfying q = goto(initial(S), u), due to Lemma 3 the algorithm does not need to check the exponent associated with later occurrences of u, nor with the suffixes of u since they have been checked before. Due to Lemma 2, suffixes of u ending at the same right-most position on z do not have a larger exponent. Therefore the next suffix whose associated exponent has to be checked is the longest suffix leading to a different state of S: it is F (q ) and the length of the suffix is L(F (q )) by definition of F and L.

Finally note the initial state of S is marked because it corresponds to an empty word u, that is a factor of exponent 1, which is not larger than the values of e. This proves the algorithm runs through all possible relevant factors and completes the proof.

Complexity analysis

In this section we analyse the running time and memory usage of our algorithms. Proof. The space is used mostly for storing the automaton, which is known to have no more than 2|z| states and 3|z| edges (see [START_REF] Crochemore | Algorithms on Strings[END_REF]). It can be stored in linear space if edges are implemented by successor lists, which adds a multiplicative log a factor on transition time.

It is known from [9, Section 6.6] that the algorithm runs in linear time on a fixed alphabet, including the automaton construction with elements F , L and sc, if we exclude the time for executing lines 9 to 14.

It remains to enumerate the number of times line 11 is executed. It is done once for each position j associated with an unmarked state. If it is done more than once for a given position, then the second value of q comes from the failure link. A crucial observation is that condition at line 12 holds for such a state. Therefore, since S(z) has no more than 2|z| states, the total number of extra executions of line 11 is at most 2|z|, which gives the stated result.

The proof of the linear running time of Algorithm MaxExpFac additionally relies on a combinatorial property of words. It is the notion of repetitive threshold RT(a) for an alphabet of size a mentioned in Introduction. Proof. Computing the f-factorisation (z 1 , z 2 , . . . , z k ) of the input takes time and space O(n) on a fixed-size alphabet using any suffix data structure. (It can even be done in time O(n) on an integer alphabet, see [START_REF] Crochemore | Computing longest previous nonoverlapping factors[END_REF].)

The next instructions execute in linear extra space from Proposition 5.

Line 5 takes time O(|z

i-1 | + min{ |z i-1 |/(e -1) -1 , |z i | -1}), which is bounded by O(|z i-1 | + |z i-1 |/(e -1) -1), for i = 2, . . . , k.
O(Σ k i=2 |z i-1 |). Similarly it is O(Σ k i=2 |z i |) for Line 6 and O(Σ k i=2 |z i-1 z i |) for Line 8. Thus the overall runtime is bounded by O(Σ k i=1 |z i |), which is O(n) as expected.

Counting maximal-exponent factors

This section is devoted to the combinatorial aspects of maximal-exponent factors (MEF). We exhibit upper and lower bounds on their maximal number of occurrences in an overlap-free word.

The upper bound shows there is no more than a linear number of MEF occurrences in a word according to its length. In addition, the lower bound proves that this is optimal up to a multiplicative factor that remains to be discovered.

Note that on the alphabet {a, a 1 , . . . , a n } the word aa 1 aa 2 a . . . aa n a of length 2n + 1 has a quadratic number of maximal factors. Indeed all occurrences of factors of the form awa for a non-empty word w are non extensible.

But only the n factors of the form aca for a letter c have the maximal exponent 3/2.

Upper bound

Before giving an upper bound, we start with a simple property of MEFs, which does not lead to their linear number, but is used later to tune the upper bound. If we count the occurrences of MEFs by their border lengths after Lemma 7

we get an initial part of the harmonic series, a quantity that is not linear with respect to the length of y.

To get a linear upper bound on the number of occurrences of MEFs we introduce the notion of δ-MEFs, for a positive real number δ, as follows. A

MEF uvu is a δ-MEF if its border length b = |u| = |uvu|period(uvu) satisfies 2δ < b ≤ 4δ. Then any MEF is a δ-MEF for some δ ∈ Δ, where Δ = {1/4, 1/2, 1, 2, 2 2 , 2 3 , . . .}. This is the technique used for example in [START_REF] Rytter | The number of runs in a string[END_REF][START_REF] Crochemore | The "runs" conjecture[END_REF] to count runs in words. Note that w, the overlap of the two left borders, occurs at least at two other positions. For example, in the first case, it occurs as a suffix of the right border of u and as a prefix of the right border of ū. Due to the periodicity of the two factors, uvu and ūvū, the last two occurrences of w are p -p positions apart. Therefore the factor z starting with one occurrence and ending with the other has exponent at least (it can be larger if w is not the longest border of z): , 2) (8, 1.5) (9, 1.5) (10, 1.5) (11, 2) (12, 1.5) (12, 1.5) (13, 1.5) (14, 1.5)

y i j u v u ū v ū w w w - < δ larger exponent y i j u v u ū v ū w w w - < δ larger exponent y i j u v u ū v ū ū - < δ larger exponent
1 + |w| p -p = 1 + |w|(e -

Lower bound

We now deal with a lower bound on the maximal number of occurrences of maximal-exponent factors. We first consider an infinite word whose factors have maximal exponent 3/2 and then show that its prefixes contain a linear number of occurrences of these factors.

There exists an infinite word on the four-letter alphabet A 4 = {a, b, c, d} whose maximal exponent of its factors is 7/5. The existence of such a word was proved by Pansiot [START_REF] Pansiot | A propos d'une conjecture de F. Dejean sur les répétitions dans les mots[END_REF] and it is easy to see that the exponent value cannot be smaller for an infinite word on A 4 . Indeed, the result is part of the conjecture of Dejean [START_REF] Dejean | Sur un théorème de Thue[END_REF] who stated the repetitive threshold for all alphabet sizes; the proof of this conjecture was eventually completed by Rao [START_REF] Rao | Last cases of Dejean's conjecture[END_REF] and by Currie and Rampersad [START_REF] Currie | A proof of Dejean's conjecture[END_REF]. Here is an example of such a word given by Pansiot [START_REF] Pansiot | A propos d'une conjecture de F. Dejean sur les répétitions dans les mots[END_REF]: p = bacdabcadcbacdbcabdacbad . . .

From the word p we define q on the alphabet A 5 = {a, b, c, d, e} by inserting letter e in between any two consecutive letters. That is, for each integer i ≥ 0,

q[2i] = e q[2i + 1] = p[i]
or in other words q = f (p), where f is the morphism defined by f (a) = ea, for any letter a ∈ A 4 . The word q is: q = ebeaecedeaebeceaedecebeaecedebeceaebedeaecebeaed . . . Let uvu be a factor of p, where u is its longest border and then |uv| is its smallest period. By the choice of p, we have exp(uvu) = |uvu|/|uv| ≤ 7/5.

In addition, we know that the period length of all 7/5-powers in p is at least 10 (see [START_REF] Badkobeh | Finite repetition threshold for large alphabets[END_REF]). Thus the induced factor f (uvu)e in q has exponent (2|uvu| + 1)/2|uv|, which is 29/20 when uvu is a 7/5-power. This value is less than 3/2.

As another example, consider the factor abcda of p. It has exponent 5/4 and its induced factor in q, f (abcda)e = eaebecedeae, has exponent 11/8, which is less than 3/2 again. By contrast, the factor abca of p has exponent 4/3 and its induced factor in q, eaebeceae has exponent 9/6 = 3/2.

The next lemma shows that very few factors of q have exponent 3/2, the maximal value. Lemma 10. Let w be a factor of q, then exp(w) ≤ 3/2. Additionally exp(w) = 3/2 when w = f (uvu)e with either uvu = v = a or u = a and v = bc up to a permutation of letters.

Proof. Let w be a factor with maximal exponent among the factors of q.

Its first letter is e because otherwise its length could be increased by one unit without changing the period, which would increase the exponent. Similarly, its last letter is e. Then, w is of the form f (uvu)e for a factor uvu of p whose longest border is u.

Assume that exp(w) ≥ 3/2. Then Finally, if |u| = 2, |uv| = 5 and exp(uvu) = 7/5. But as recalled above, no factor of p with that exponent has period 5. This case is impossible, which concludes the proof.

The conclusion of the previous lemma is that the maximal exponent of factors is 3/2. The lower bound on the occurrence number of 3/2-powers in q requires another property of p, which is used in the proof of the following corollary.

Figure 1 :

 1 Figure 1: The only four possible locations of a factor uvu involving phrase z i of the factorisation of the word: (i) internal to z i ; (ii) the first occurrence of u is internal to z i-1 ;(iii) the second occurrence of u is internal to z i ; (iv) the second occurrence of u is internal to z i-1 z i .

  e) 9 return e Note that variable e can be initialised to the repetitive threshold RT(a) (see Introduction) when the alphabet of word y is of size a and if the word is long enough. The maximal length of words containing no factor of exponent at least RT(a) is 3 for a = 2, 38 for a = 3, 121 for a = 4, and a + 1 for a ≥ 5

Figure 2 :

 2 Figure 2: Suffix Automaton of abcadbeca. Suffix links:F [1] = 0, F [2] = 10, F [3] = 11, F [4] = 1, F [5] = 0, F [6] = 10, F [7] = 0, F [8] = 11, F [9] = 12, F [10] = 0, F [11] = 0, F [12] = 1. Maximal incoming word lengths: L[0] = 0, L[1] = 1, L[2] = 2, L[3] = 3, L[4] = 4, L[5] = 5, L[6] = 6, L[7] = 7, L[8] = 8, L[9] = 9, L[10] = 1, L[11] = 1, L[12] = 2. Minimal extension lengths: sc[0] = 0, sc[1] = 0, sc[2] = 7, sc[3] = 6, sc[4] = 5, sc[5] = 4, sc[6] = 3, sc[7] = 2, sc[8] = 1, sc[START_REF] Crochemore | Algorithms on Strings[END_REF] = 0, sc[START_REF] Kolpakov | On maximal repetitions in words[END_REF] = 3, sc[START_REF] Rytter | The number of runs in a string[END_REF] = 1, sc[START_REF] Crochemore | The "runs" conjecture[END_REF] = 0.

Figure 3 :

 3 Figure 3: When u and its suffix u end at the same right-most position on z, factor (1) has a larger exponent than factor (2).

Figure 3 Lemma 2 .

 32 Figure 3 illustrates the proof of the following lemma.

Figure 4 :

 4 Figure 4: Factor (1) ending at position j has a larger exponent than factor (2) ending at position k > j.

Figure 4 . 3 .

 43 Figure 4.

Figure 6 :

 6 Figure 6: Computing exponents when searching zw for factors uvu. The first occurrence of u is in z and the second ends in zw. The Suffix Automaton of z = abcadbeca with function sc is in Figure 2. The search is done by parsing w = decadbecad with the automaton.Exponents of factors are given by the expression ( + sc[q] + j + 1)/(sc[q] + j + 1). The last line is for exponents corresponding to suffixes of u. The maximal exponent of all factors is 7/4.

Figure 6 Theorem 4 .

 64 Figure 6 illustrates a computation done by the algorithm using the Suffix

Proposition 5 .

 5 Applied to words z and w and to the rational number e, Algorithm MaxExp requires O(|z|) space in addition to inputs and runs in total time O(|z| + min{ |z|/(e -1) -1 , |w| -1}) on a fixed size alphabet. It performs less than 2|z|+min{ |z|/(e-1)-1 , |w|-1} exponent computations.

Theorem 6 .

 6 Applied to any overlap-free word of length n on a fixed-size alphabet, Algorithm MaxExpFac runs in time O(n) and requires O(n) extra space.

  For a long enough input, e is eventually at least RT(a) where a is the input alphabet. The time is then bounded by O(|z i-1 | + |z i-1 |/(RT(a) -1) -1), thus O(|z i-1 |) because RT(a) is a constant. The contribution of Line 5 to the total runtime is then

Lemma 7 .

 7 Consider two occurrences of MEFs with the same border length b starting at respective i and j on the word y, i < j. Then, j -i > b. Proof. The two MEFs having the same border length, since they have the same exponent, they have also the same period and the same length. Let b be their border length and p their period. Assume ab absurdo j-i ≤ b. The word y[i . . i+b-1] = y[i+p . . i+p+b-1] is the border of the first MEF. The assumption implies that y[i+b] = y[i+p+ b] because these letters belong to the border of the second MEF. It means the first MEF can be extended with the same period, producing a larger exponent, a contradiction. Therefore, j -i > b as stated.

Figure 7 : 1 . 8 . 7 .

 7187 Figure 7: Two δ-MEFs, uvu and ūv ū, having mid-positions of their left borders at close positions induce a factor with a larger exponent, a contradiction.

1 ,

 1 ≥ |uv| . Also, since uvu is a factor of p, it satisfies |uvu|/|uv| ≤ 7/5 , which is only possible for |u| = 0, 1, or 2. If |u| = 0, |v| = |uv| = 1, and the induced factor in q is of the form eae, for a letter a ∈ A 4 , and has exponent 3/2. If |u| = 1, |uv| = 3, and then uvu is of the form abca up to a permutation of letters, inducing a factor of exponent 3/2 in q.

  • • • z i-2 and the second occurrenceis contained in z i-1 z i .Case (i) needs no action and other cases are dealt with calls to Algorithm MaxExp as described in the code below where x denotes the reverse of word x. For any two words z and w and a positive rational number e, MaxExp(z, w, e) is the maximal exponent of factors in zw whose occurrences start in z and end in w, and whose exponent is at least e; it is e itself if there is no such factor.

  There are less than 2.25 n occurrences of maximal-exponent factors in a word of length n.

	Theorem 9. Proof. According to Lemma 7 there are less than
							b=5 b=1	n b + 1	= 1.45 n
	occurrences of MEFs with border length at most 5.
	We then apply Lemma 8 with values of δ ∈ Γ that cover all remaining
	border lengths of MEFs: Γ = {(5/2), 5, 10, 20, . . .}. It gives the upper bound
		δ∈Γ	n δ	=	1 5	2 + 1 +	1 2	+	1 2	2	+ . . . n =	4 5	n
	for the number of occurrences of MEFs with border length at least 6. There-
	fore the global upper bound we obtain is 2.25 n.
	Note that the border length 5 minimises the expression
	b=k b=1	n b + 1	+	1 k		2 + 1 +	1 2	+		1 2		b=k b=1	n b + 1	+	4 n k
	n	5				6		7			8	9	10	11	12
	binary	2				3		4			5	5	6	6	8
	ternary (2, 1.5) (3, 1.5) (4, 2) (5, 2) (5, 2) (6, 1.5) (6, 2) (8, 2)
	n δ 4-ary (2, 1.5) (3, 1.5) (4, 2) (5, 2) (5, 2) (6, 1.5) (7, 1.5) (8, 2) = n 4 + 2 + 1 + 1 2 1 + 2 13 14 15 16 17 18 19 δ∈Δ 8 9 9 11 11 12 12	20 14
	The next statement refines the above upper bound by combining results (8, 2) (9, 2) (9, 2) (11, 2) (11, 2) (12, 2) (12, 2) (14
	of Lemmas 7 and 8.

1) (|u| -|ū|) . Now, from inequalities 2δ < |ū| ≤ |u| ≤ 4δ and the definition of w, we have both |w| > |u|/2 and |u| -|ū| < |u|/2. Then |w| > |u| -|ū| and since e -1 > 0 the exponent of z is then larger than e, a contradiction. Therefore |j -i| ≥ δ as stated. A direct consequence of the previous lemma is the linear number of MEF occurrences. Because Lemma 8 implies that the number of δ-MEF occurrences in y is no more than n/δ. And since values of δ in Δ cover all border lengths, the total number of occurrences of MEFs is bounded by 2 + . . . < 8 n. 2 + . . . n = with respect to k, which means the technique is unlikely to produce a smaller bound. By contrast, experiments show that the number of occurrences of MEFs is smaller than n and not even close to n, at least for small values of n. The following table displays the maximal number of MEFs for overlapfree word lengths n = 5, 6, . . . , 20 and for alphabet sizes 2, 3 and 4. It also displays (second element of pairs) the associated maximal exponent. In the binary case we already know that it is 2 since squares are unavoidable in words whose length is greater than 3.

Corollary 11. The number of occurrences of maximal-exponent factors in

prefixes of q tends to 2n/3 with the prefix length n.

Proof.

From the previous lemma, maximal-exponent factors in q are induced by factors of the form a or abca, up to a permutation of the four letter of A 4 , in p.

It is clear from the definition of q that at every two of its positions occur one of the factors eae, ebe, ece, ede. Their occurrence number then tends to n/2.

Turning to the other factors of exponent 3/2, it is known that the six factors of the form abca appear at every three positions in p. Indeed, an occurrence of abca, can extend to abcad and abcadb but not to abcadbc whose suffix bcadbc has exponent 6/4 = 3/2 > 7/5. Therefore, the induced factors of exponent 3/2 occur at every six positions in q, leading to a limit of n/6.

Summing up the two limits, the occurrence numbers of 3/2-powers in prefixes of q tend to n/2 + n/6 = 2n/3 as stated.

Conclusion

The result of Section 6 implies that Algorithm MaxExpFac can be modified to output all the MEFs occurring in the input word in the same asymptotic time. Indeed, the only occurrences of MEFs that are skipped by the algorithm when computing the maximal exponent are those occurring inside a phrase of the f-factorisation (Case (i) of Section 3). However storing the previous occurrences of MEFs and listing them can be done in time proportional to their number, which does not affect the asymptotic running time of the algorithm and yields the next statement.

Corollary 12. All the occurrences of maximal-exponent factors of a word can be listed in linear time with respect to its length.

The present work triggers the study of a uniform solution to compute both repetitions (of exponent at least 2) and repeats. However, exponent 2 seems to reflect a transition phase in the combinatorics of these studied objects. For instance, the number of repetitions in a word can be of the order of n log n and the number of maximal periodicities (runs) is linear, while the number of maximal occurrences of factor uvu can be quadratic.

An interesting question is to select factors related to repeats that occur only a linear number of times or slightly more. An attempt has been achieved in [START_REF] Kolpakov | On maximal repetitions of arbitrary exponent[END_REF] where it is shown that the number of maximal repetitions of any exponent more than 1 + is bounded by 1 n ln n. See also the discussions at the end of [START_REF] Kolpakov | On maximal repetitions in words[END_REF] and of [START_REF] Crochemore | Maximal repetitions in strings[END_REF].

Other interesting problems are the exact evaluation of the maximal number of occurrences of MEF and the calculation of the maximal number of (distinct) MEFs occurring in a word.

Acknowledgements

We warmly thank G. Kucherov and R. Kolpakov for interesting discussions on repetitions, runs and repeats in words. We also thank the reviewers whose comments greatly helped us improve the presentation of this article.