Refael Hassin
email: hassin@post.tau.ac.il.

Jérôme Monnot
email: monnot@lamsade.dauphine.fr.

Danny Segev
email: segevd@post.tau.ac.il.

The complexity of Bottleneck Labeled Graph Problems

Keywords: Bottleneck labeled problems, approximation algorithms, hardness of approximation, s-t path, s-t cut, spanning tree, perfect matching

In the present paper, we study bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph of prescribed structure (such as that of being an s-t path, a spanning tree, or a perfect matching) while trying to avoid over-picking or under-picking edges from any given color.

Introduction

Let G = (V, E) be a directed or undirected graph, with a weight function w : E → R + and a labeling function L : E → {c 1 , . . . , c q }. We interchangeably refer to the elements of L(E) as labels or colors. In addition, for E ′ ⊆ E and 1 ≤ i ≤ q, we use L i (E ′ ) = {e ∈ E ′ : L(e) = c i } to denote the collection of c i -colored edges in E ′ . With this notation in mind, the c i -color weight of an edge set E ′ ⊆ E is defined as e∈L i (E ′ ) w(e), i.e., the total weight of all c i -colored edges in E ′ . Now let P be a given graph property defined on subsets of E, such as that of inducing a spanning tree, an s-t path, an s-t cut, or a perfect matching. The min-max weighted labeled P problem (henceforth, WL-min-max P) asks to compute an edge set E ′ ⊆ E satisfying P that minimizes max i e∈L i (E ′ ) w(e), the maximum color weight of E ′ . Similarly, in max-min weighted labeled P (WL-max-min P), the minimum color weight should be maximized. We refer to both versions as weighted labeled bottleneck P problems. Furthermore, for ease of presentation, we denote by UL-min-max P the unweighted special case of WL-min-max P, that asks to minimize the maximum color frequency. Analogous notation will also be used for the corresponding max-min variant.

The complexity of WL-min-max P has been investigated for several graph properties by Richey and Punnen [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF], Punnen [START_REF] Punnen | Traveling salesman problem under categorization[END_REF][START_REF] Punnen | On bottleneck assignment problems under categorization[END_REF], and Averbakh and Berman [START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF], in the context of "optimization problems under categorization". As indicated in [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF][START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF], WL-min-max P contains both min-max weighted P and min-sum weighted P as special cases. One simply has to assign a distinct label to each edge in the former variant, and a single label for all edges in the latter variant. Similar arguments lead to an analogous result, stating that max-sum weighted P can be formulated in terms of WL-max-min P. Consequently, whenever min-sum weighted (respectively, max-sum weighted) P is NP-hard, so is WL-min-max (respectively, max-min) P. 1

Our results

We now provide, for each problem considered in this paper, a brief description of our main findings, accompanied by a concise summary of previous work.

Labeled bottleneck s-t path

Previous work:

1. Averbakh and Berman [START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF] showed that WL-min-max s-t path is weakly NP-hard, even in bicolored graphs. Moreover, they proved that UL-min-max s-t path is NP-hard for an arbitrary number of colors. These results apply to both directed and undirected graphs.

2. In [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [GT54], p. 203), it was mentioned that the pair-choice vertex problem is NP-hard. Here, we are given a directed graph G = (V, E), two specified nodes {s, t} ⊆ V , and a collection of pairwise-disjoint pairs of arcs. The objective is to determine whether there exists an s-t path traversing at most one arc from any given pair. Since UL-min-max directed s-t path can be viewed as a special case of this problem (pairs correspond to colors), the former cannot be approximated within a factor of 2ǫ for any fixed ǫ > 0, unless P=NP.

3. It is not difficult to verify that UL-max-min s-t path generalizes the longest path problem, even in monochromatic graphs. Therefore, the results of Karger, Motwani and Ramkumar [START_REF] Karger | On approximating the longest path in a graph[END_REF]Thm. 11] imply that UL-max-min s-t path cannot be approximated within a factor of 2 O(log 1-ǫ n) for any fixed ǫ > 0, unless NP ⊆ DTIME(2 O(log 1/ǫ n) ).

New results:

1. UL-max-min s-t path is not approximable at all, unless P=NP (Theorem 4.1).

2. For a fixed number of colors, there is a fully polynomial-time approximation scheme for WL-min-max s-t path (Corollary 3.2).

3.

For an arbitrary number of colors, there is a polynomial-time algorithm that constructs a feasible solution to UL-min-max s-t path in undirected graphs using O( √ nOPT) edges from any given color. Here, n = |V | and OPT denotes the objective value of an optimal solution (Subsection 4.2). For directed graphs, the path we construct traverses O( √ mOPT) edges from any color, where m = |E| (Subsection 4.3).

Labeled bottleneck spanning tree

Previous work: Richey and Punnen [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF] showed that WL-min-max spanning tree is weakly NP-hard, even in bicolored graphs. We are not aware of previous work regarding the max-min version of this problem.

New results:

1. WL-min-max spanning tree is strongly NP-hard (Corollary 5.2); it can be approximated within a factor of O(log n) (Subsection 5.3).

2. UL-min-max spanning tree can be solved in polynomial time (Theorem 5.4).

3. UL-max-min spanning tree can be solved in polynomial time (Theorem 5.3). WL-maxmin spanning tree is strongly NP-hard (Corollary 5.2), and it is also weakly NP-hard in planar bicolored graphs (Theorem 2.1).

4. For a fixed number of colors, there is a fully polynomial-time approximation scheme for both versions of weighted labeled bottleneck spanning tree (Corollary 3.2).

Labeled bottleneck perfect matching

Previous work:

1. Richey and Punnen [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF] showed that WL-min-max perfect matching is weakly NP-hard, even in bicolored graphs. A stronger result has recently been obtained by Punnen [START_REF] Punnen | On bottleneck assignment problems under categorization[END_REF], who proved that even the simpler WL-min-max assignment problem is strongly NPhard.

2. Itai, Rodeh, and Tanimoto [START_REF] Itai | Some matching problems for bipartite graphs[END_REF] proved that the following problem is NP-complete: Given a bipartite graph and a collection of pairs of edges, decide whether there exists a perfect matching that picks at most one edge from any given pair. This problem remains NP-complete for a collection of disjoint pairs [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [GT59], p. 203).

Since UL-min-max perfect matching can be viewed as a special case of this problem, the former cannot be approximated within a factor of 2ǫ for any fixed ǫ > 0, unless P=NP.

3. Karzanov [START_REF] Karzanov | Maximum matchings of given weight in complete and complete bipartite graphs[END_REF], and Yi, Murty and Spera [START_REF] Yi | in colored networks[END_REF] proved that, given a complete bipartite graph K n,n with edges colored either red or blue, the problem of finding a perfect matching consisting of exactly r red edges and nr blue edges is polynomial-time solvable 1 . Therefore, UL-min-max and UL-max-min perfect matching in complete bipartite bicolored graphs can be solved to optimality in polynomial time.

4. To our knowledge, WL-max-min perfect matching has not been studied in the literature.

New results:

1. WL-max-min perfect matching is weakly NP-hard in bicolored planar graphs (Theorem 2.1). UL-max-min perfect matching is not approximable at all in general graphs, unless P=NP (Theorem 6.1).

2. There is an approximation-preserving reduction from UL-min-max directed s-t path to UL-min-max perfect matching (Theorem 6.2).

3. For a fixed number of colors, there is a fully polynomial-time approximation scheme for both versions of weighted labeled bottleneck perfect matching (Corollary 3.2).

Labeled bottleneck s-t cut

Previous work: To our knowledge, both versions of this problem have not been studied yet.

New results:

1. UL-min-max s-t cut is NP-hard in bicolored graphs (Theorem 2.3). When the underlying graph is planar, UL-min-max s-t cut cannot be approximated within a factor of 2ǫ for any fixed ǫ > 0, unless P=NP (Theorem 7.1), and the weighted version of this problem is weakly NP-hard when the graph is bicolored as well (Theorem 2.1).

2. WL-max-min s-t cut is weakly NP-hard in planar bicolored graphs (Theorem 2.1).

For an arbitrary number of colors, this problem is not approximable at all in planar multigraphs, unless P=NP (Theorem 7.2).

Related work

In this section, we provide a brief survey of several frameworks to which our contributions are related. Since some of the settings under consideration have received a great deal of attention in recent years, it is beyond the scope of this writing to present an exhaustive overview. We refer the reader to the undermentioned papers and to the references therein for a more comprehensive review of the literature.

Multiobjective combinatorial optimization [START_REF] Ehrgott | A survey and annotated bibliography of multiobjective combinatorial optimization[END_REF][START_REF] Ehrgott | Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey[END_REF][START_REF] Ulungu | Multi-objective combinatorial optimization problems: A survey[END_REF][START_REF] White | A bibliography on the applications of mathematical programming multipleobjective methods[END_REF]. The basic ingredients of a multiobjective optimization problem are typically: A set of instances I; a set of feasible solutions F(x) associated with every instance x ∈ I; and a collection of cost functions w 1 (x, y), . . . , w k (x, y) associated with every instance x ∈ I and feasible solution y ∈ F(x).

Given an instance x ∈ I, the goal is to solve min y∈F (x) {w 1 (x, y), . . . , w k (x, y)}, where the exact meaning of "min" depends on the particular setting in question. For example, it may stand for Pareto optimality (see Section 3), for aiming to minimize the worst cost function, or for lexicographically minimizing the vector of cost functions. It is not difficult to verify that WL-min-max P is actually a multiobjective optimization problem in disguise: The set of feasible solutions consists of all edge sets that satisfy P; for every color c i there is a corresponding cost function w i which is exactly the c i -color weight; and the goal is to minimize the maximum cost function. Minor adjustments allow us to treat WL-max-min P in a similar way.

Robust discrete optimization [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF][START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Dhamdhere | How to pay, come what may: Approximation algorithms for demand-robust covering problems[END_REF]. Very informally, robust optimization deals with decision making in environments of considerable data uncertainty, trying to come up with solutions that hedge against the worst contingency that may arise. Several alternative approaches for coping with uncertainty have been explored and exploited; however, the scenario-based framework of Kouvelis and Yu [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF] seems most relevant to our paper. In this context, future developments are described by a finite number of scenarios, each of which corresponds to a possible realization of the unknown model parameters. The objective is to optimize against the worst possible scenario by using a min-max objective. Once again, we note that WL-min-max P can be easily cast as a scenario-based robust optimization problem: For every color c i there is an analogous scenario s i , in which the weight w s i (e) of an edge e ∈ E is set to w(e) if its color is c i , and to 0 otherwise. In addition, the cost of an edge set E ′ ⊆ E in scenario s i is given by e∈E ′ w s i (e), which is exactly the c i -color weight of this set.

The min-sum-max setting. A complementary line of work [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF][START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF][START_REF] Punnen | On bottleneck assignment problems under categorization[END_REF] on edge-colored graphs attempts to minimize the sum of the maximal edge weight picked from every given color. In particular, when all edges are associated with unit weights, a problem of this nature reduces to that of constructing subgraphs satisfying a required property while minimizing the number of colors used. Some properties that have recently been studied in this context include spanning trees [START_REF] Chang | The minimum labeling spanning trees[END_REF][START_REF] Broersma | Spanning trees with many or few colors in edge-colored graphs[END_REF][START_REF] Brüggemann | Local search for the minimum label spanning tree problem with bounded color classes[END_REF], 17], s-t paths [START_REF] Broersma | Paths and cycles in colored graphs[END_REF]17], and perfect matchings [START_REF] Monnot | The labeled perfect matching in bipartite graphs[END_REF].

2 Fixed Number of Colors: Hardness Results

Weak NP-hardness in bicolored graphs

In what follows, we prove that several weighted labeled bottleneck problems are NP-hard, even in planar bicolored graphs. As indicated in Subsection 1.1, WL-min-max P is known to be NP-hard in bicolored graphs [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF][START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF] for P ∈ {spanning tree, s-t path, perfect matching}.

Theorem 2.1. WL-min-max P and WL-max-min P are NP-hard, even in planar bicolored graphs, for P ∈ {s-t path, s-t cut, perfect matching, spanning tree}.

Proof. We propose a reduction from the partition problem, whose instances consist of a collection of integers {a 1 , . . . , a n }, and the goal is to decide whether or not there exists a subset J ⊆ {1, . . . , n} such that j∈J a j = j / ∈J a j . To this end, for every 1 ≤ i ≤ n consider a 4-edge cycle on the set of vertices {x i , l i , y i , r i }, listed clockwise, with edge colors

L(x i , l i ) = L(y i , r i ) = c 1 , L(x i , r i ) = L(y i , l i ) = c 2 , and weights w(x i , l i ) = w(x i , r i ) = a i , w(y i , l i ) = w(y i , r i ) = 0.
These n cycles describe a graph H ′ . For the perfect matching case, we define H = H ′ . For the s-t path and spanning tree cases, we construct H from H ′ by identifying y i and x i+1 to a single vertex (for every 1 ≤ i ≤ n -1), and setting s = x 1 , t = y n . Finally, for the s-t cut case, we construct H from H ′ by deleting the vertex y i along with the edges (y i , r i ) and (y i , l i ) in each 4-cycle, and identifying r 1 , . . . , r n to a vertex s, and l 1 , . . . , l n to t.

In each of these cases, it is easy to verify that the resulting WL-min-max P instance has an objective value of at most 1 2 n j=1 a j if and only if there exists J ⊆ {1, . . . , n} with j∈J a j = j / ∈J a j . Similarly, WL-max-min P has an objective value of at least 1 2 n j=1 a j , for P ∈ {s-t path, s-t cut, perfect matching}. Regarding WL-max-min spanning tree, some edge weights need to be changed: We set w(y i , l i ) = w(y i , r i ) = n j=1 a j , for every 1 ≤ i ≤ n. Consequently, the latter problem has an objective value of at least (n + 1 2 ) n j=1 a j if and only if there exists J ⊆ {1, . . . , n} with j∈J a j = j / ∈J a j .

Strong NP-hardness for s-t cuts

Aissi, Bazgan and Vanderpooten [START_REF] Aissi | Pseudo-polynomial algorithms for min-max and min-max regret problems[END_REF] proved that min-max robust P with a fixed number of scenarios admits pseudo-polynomial algorithms for s-t paths and spanning trees in general graphs and for perfect matchings in planar graphs. Since WL-min-max P can be viewed as a special case of these settings (see Subsection 1.2), it follows that the corresponding min-max labeled problems have pseudo-polynomial algorithms for a fixed number of colors.

In contrast, we proceed by proving that WL-min-max s-t cut is strongly NP-hard in bicolored graphs. A similar result was established for bi-criteria s-t cut [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF]Thm. 6], and more recently for min-max robust s-t cut with two scenarios [START_REF] Aissi | Complexity of the min-max (regret) versions of cut problems[END_REF]Cor. 1]. Unfortunately, in their reductions the resulting instances do not correspond to WL-min-max s-t cut instances, and it appears as if we cannot conclude the result for WL-min-max s-t cut in an obvious way. However, we can slightly modify the construction of Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF].

Theorem 2.2. WL-min-max s-t cut is strongly NP-hard in bicolored graphs.

Proof. We propose a reduction from the bisection width problem. Given a connected graph

G = (V, E) on 2n vertices, a bisection is a cut (V 1 , V 2 ) of G with |V 1 | = |V 2 | = n.
The decision version of bisection width asks to determine, for a given integer k, whether there exists a bisection with at most k edges. This problem is known to be NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [ND17], p. 210).

Given an instance of bisection width, as described above, we construct an instance I = (G ′ , w, L) of WL-min-max s-t cut, with G ′ = (V ′ , E ′ ) and L(E ′ ) = {c 1 , c 2 }, as follows:

• G ′ has two additional vertices, s and t, each of which is connected to every vertex of G.

• L(s, v) = c 1 for every v ∈ V ; all other edges have color c 2 .

• w(s, v) = k(n + 1) and w(t, v) = kn for every v ∈ V ; w(e) = n for every original edge e ∈ E.

We now argue that G has a bisection of size at most k if and only if I has an s-t cut whose min-max value is at most kn

(n + 1). If (V 1 , V 2 ) is a bisection with at most k edges, then ({s} ∪ V 1 , {t} ∪ V 2 ) is an s-t cut in G ′ that picks c 1 -colored edges of total weight e∈({s},V 2 ) w(e) = kn(n + 1) and c 2 -colored edges of total weight e∈({t},V 1 ) w(e) + e∈(V 1 ,V 2 ) w(e) = kn 2 + kn = kn(n + 1). Conversely, let ({s} ∪ V 1 , {t} ∪ V 2 ) be an s-t cut in G ′ with
min-max value of at most kn(n + 1). Since each c 1 -colored edge of this cut has a weight of k(n + 1), it follows that |V 2 | ≤ n. In addition, the c 2 -colored edges of this cut have a total weight of n|E ′′ | + kn|V 1 |, where E ′′ = (V 1 , V 2 ), and we conclude that

|V 1 | ≤ n + 1. Now, if |V 1 | = n + 1 the inequality n|E ′′ | + kn|V 1 | ≤ kn(n + 1) implies E ′′ = ∅, so G is clearly disconnected (contradicting our initial assumption); thus |V 1 | ≤ n. Finally, since |V 1 | ≤ n and |V 2 | ≤ n, we have |V 1 | = |V 2 | = n, and therefore (V 1 , V 2 ) is a bisection with at most k edges.
Theorem 2.3. UL-min-max s-t cut is NP-hard in bicolored graphs.

Proof. To prove the theorem, we show that a ρ-approximation for UL-min-max s-t cut can be converted in polynomial time into a ρ-approximation for WL-min-max s-t cut when the edge weights are integers upper bounded by a polynomial in n. The theorem follows from the combination of this result and Theorem 2.2.

Let I = (G, w, L) be an instance of WL-min-max s-t cut, where G = (V, E) has n vertices and max e∈E w(e) = O(n O (1) ). We replace each edge e = (u, v) ∈ E by a collection H(e) of w(e) edge-disjoint paths of length two (connecting u and v), each edge of which is colored by L(e). The vertices u and v will be called extreme vertices of H(e), whereas other vertices of H(e) will be called inner vertices. We refer to the resulting UL-min-max s-t cut instance as

I ′ = (G ′ , L ′ ).
Consider an s-t cut (S ′ , T ′ ) in G ′ , with s ∈ S ′ and t ∈ T ′ . We iteratively apply the following procedure for each original edge e ∈ E: If the extreme vertices of H(e) appear in the same set of the partition, assign all inner vertices of H(e) to that set. These changes can only decrease the total weight of L(e)-colored edges in the current s-t cut, and therefore also its min-max value. From the resulting s-t cut (S ′ , T ′ ), we can find an s-t cut in G of identical min-max value by considering (S ′ ∩ V, T ′ ∩ V ), the restriction of this cut to G.

Fixed Number of Colors: An FPTAS

In what follows, we present a fully polynomial-time approximation scheme for weighted labeled bottleneck s-t path, spanning tree, and perfect matching, for a fixed number of colors.

Approximate Pareto curves

Let P be a property described in Section 1, and consider the multiobjective version of P (henceforth, Multi k P). An instance I of this problem consists of a graph G = (V, E), and a weight vector w(e) = (w 1 (e), . . . , w k (e)) for each edge e ∈ E. An edge set E ′ ⊆ E forms a feasible solution to Multi k P if it satisfies P, and the objective value of E ′ is given by the vector ( e∈E ′ w 1 (e), . . . , e∈E ′ w k (e)). In a minimization problem, we say that a solution E ′ is dominated by E ′′ if e∈E ′′ w i (e) ≤ e∈E ′ w i (e) for every 1 ≤ i ≤ k, and the inequality is strict for at least one index; the inequalities are reversed for a maximization problem. The goal is to compute the Pareto curve C(I), which is the set of all undominated solutions to I. Finally, an ǫ-approximate Pareto curve for the minimization (respectively, maximization) version of Multi k P is a set C ǫ (I) of solutions such that 1. |C ǫ (I)| is polynomially bounded in terms of the input size and 1 ǫ . 2. For every E * ∈ C(I), there exists

E ′ ∈ C ǫ (I) with e∈E ′ w i (e) ≤ (1 + ǫ) e∈E * w i (e)
for every 1

≤ i ≤ k (respectively, e∈E ′ w i (e) ≥ (1 -ǫ) e∈E * w i (e)).
When k is fixed, Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF]Cor. 5] proposed an FPTAS for constructing ǫ-approximate Pareto curves of multiobjective s-t walk, spanning tree, and perfect matching.

The approximation scheme

We now relate the approximability of several weighted labeled bottleneck problems to that of their multiobjective counterparts. This approach has already been suggested in the context of robust optimization [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF]2], implying that results similar to those described in the next theorem can be immediately derived for the min-max variants.

Theorem 3.1. For a fixed number of colors, the efficient construction of an ǫ-approximate Pareto curve for the version of Multi k P implies a (1-ǫ)-approximation to WLmax-min P. A similar result for the minimization version leads to a (1 + ǫ)-approximation to WL-min-max P.

Proof. For purposes of brevity, we deal with the maximization setting, noting that the arguments below can be easily adapted to the corresponding minimization problem. Let I = (G, L, w) be an instance of WL-max-min P such that L(E) = {c 1 , . . . , c k }. We construct an instance I ′ = (G, w ′ ) of Multi k P, where the weight vector w ′ (e) = (w ′ 1 (e), . . . , w ′ k (e)) associated with each edge e ∈ E is defined by setting w ′ i (e) = w(e) if L(e) = c i , and w ′ i (e) = 0 otherwise. As a result, the objective vector of a feasible solution E ′ to I ′ is given by ( e∈L 1 (E ′ ) w(e), . . . , e∈L k (E ′ ) w(e)).

Now let E * be an optimal solution to the instance I of WL-max-min P, with an objective value of OPT(I); if this instance does not have a unique optimal solution, E * is picked so that k i=1 e∈L i (E * ) w(e) is maximized. Clearly, the Pareto curve C(I ′ ) contains E * . Now, consider an ǫ-approximate Pareto curve C ǫ (I ′ ) for the maximization version of Multi k P. We pick a solution E ′ ∈ C ǫ (I ′ ) maximizing min i e∈E ′ w i (e) as a solution for WL-max-min P; since C ǫ (I ′ ) can be constructed and enumerated in polynomial time, so is our algorithm. Moreover, by definition of C ǫ (I ′ ), since E * ∈ C(I ′ ) there exists

E ′′ ∈ C ǫ (I ′ ) satisfying e∈E ′′ w i (e) ≥ (1 -ǫ) e∈E * w i (e) for every 1 ≤ i ≤ k. Hence, we conclude that E ′ constitutes a (1 -ǫ)-approximation to I, since min 1≤i≤k e∈L i (E ′ )
w(e) ≥ min

1≤i≤k e∈L i (E ′′ )
w(e) ≥ (1ǫ)

e∈L i (E * )
w(e) = (1ǫ)OPT(I) .

By combining Theorem 3.1 and the results of Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] mentioned earlier, Corollary 3.2 follows. However, an important remark is in place. Even though the algorithm in [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] constructs an ǫ-approximate Pareto curve of multiobjective s-t walk, note that any such walk can be converted (by eliminating cycles) to an s-t path of no greater min-max objective value. An analogous claim regarding the max-min version is incorrect. Corollary 3.2. For a fixed number of colors, weighted labeled bottleneck spanning tree and perfect matching admit a fully polynomial-time approximation scheme. A similar result also holds for WL-min-max s-t path.

Arbitrary Number of Colors: Labeled Bottleneck s-t Paths

For a fixed number of colors, UL-min-max s-t path is polynomial time solvable. This claim follows from the observation that we can decide whether there exists a walk connecting s and t whose objective value is exactly p ∈ {1, . . . , n -1} by means of dynamic programming. In contrast, we proceed by showing that both versions of the problem under consideration become NP-hard for an arbitrary number of colors. We complement these results by devising efficient approximation algorithms.

Hardness results

We now derive new inapproximability bounds for both versions of labeled bottleneck s-t path, in undirected as well as directed graphs. To our knowledge, these results do not follow from existing work. Theorem 4.1. UL-min-max s-t path is not (2-ǫ)-approximable for any fixed ǫ > 0, and ULmax-min s-t path is not approximable at all, unless P=NP. Similar results hold for directed graphs.

Proof. oncoming reductions will be based on the set packing and set covering problems. Given a family of sets S = {S 1 , . . . , S m } over a ground set X = {x 1 , . . . , x n } and an integer k, the objective of the set packing problem is to decide whether S contains at least k disjoint sets. The set covering problem asks whether X can be covered by at most k sets in S. Both set packing and set covering are known to be NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problems [SP3] and [SP5], p. 221-222).

Given (S, X), we create an instance I = (G, L) of unweighted labeled bottleneck s-t path, where L has n colors {c 1 , . . . , c n }. For each set S i = {x i 1 , . . . , x ip } we define a distinct path H(S i ) consisting of p edges, each given a unique color from {c i 1 , . . . , c ip }. Now, the graph = (V, E) is constructed in the following way:

• Create a path of length k on the vertices v 1 , . . . , v k+1 , in left-to-right order.

• Replace each edge (v j , v j+1 ) by m paths connecting v j and v j+1 ; for every 1 ≤ i ≤ m, the i-th path is a copy of H(S i ).

• Finally, set s = v 1 and t = v k+1 .

It is not difficult to verify that the objective value of the UL-min-max s-t path instance I is at most 1 if and only if there exists a set packing of size at least k. In addition, the objective value of the UL-max-min s-t path instance I at least 1 if and only if there exists a set covering of size at most k. Thus, we conclude that it is NP-complete to distinguish between OPT(I) = 1 and OPT(I) ≥ 2 for UL-min-max s-t path, and also between OPT(I) = 0 and OPT(I) ≥ 1 for UL-max-min s-t path.

UL-min-max s-t path: Approximating the undirected case

In what follows, we show how to efficiently construct an undirected s-t path using O( √ nOPT) edges from any given color, where n = |V | and OPT denotes the cost of an optimal solution. An essential building block of our algorithm is a constant-factor approximation for multibudget maximum coverage. An instance of this problem consists of a ground set U and a collection of subsets S ⊆ 2 , which is partitioned into {S 1 , . . . , S r }. Given an integral budget b t for each part S t , the objective is to find a subcollection S ′ ⊆ S such that S ′ picks at most b t sets from each S t and such that the of elements covered by S ′ is maximized. For these particular settings, a performance guarantee of 1 -1 e can be achieved by adopting the coverage heuristic of Ageev and Sviridenko [1, Rem. 2].

The algorithm. For simplicity of presentation, it would be convenient to assume that OPT is known in advance. Clearly, this assumption can be enforced by testing 1, . . . , n -1 as candidate values, and returning the best solution found. We also make use of ∆ = ∆(n, OPT) as a parameter whose value will be determined later.

1. F ← ∅, H ← G.
2. While dist H (s, t) > ∆ (a) Create a multi-budget maximum coverage instance by: The ground set is V (H);

for each edge e ∈ E(H) there is a corresponding subset V e , consisting of the endpoints of e; these subsets are partitioned into {S 1 , . . . , S q }, where S i = {V e : L(e) = c i }; each S i has a budget of OPT.

Approximate the instance defined above, and let F + be the collection of edges e ∈ E(H) for which V e is picked by the resulting solution.

(c) F ← F ∪ F + , H ← the contraction of F + in H.

3.

Let P be a shortest s-t path in H. Return F ∪ P . Proof. We begin by showing that, for any value of ∆, step 2 terminates within no more than 4n ∆ iterations. For this purpose, it is sufficient to prove that the number of vertices in H decreases by at least ∆ 4 whenever an edge set is contracted. Let E * ⊆ E be an optimal solution, with max i |L i (E * )| = OPT, and consider a single iteration. Since the edges E * ∩ E(H) form a subgraph of H containing an s-t it follows that {V e : e ∈ E * ∩ E(H)} is a feasible solution to the multi-budget maximum coverage instance defined in step 2a. Moreover, as the s-t distance in H is at least ∆, the latter solution satisfies

| e∈E * ∩E(H) V e | ≥ ∆. Consequently, for the current F + we must have | e∈F + V e | ≥ (1 -1
e )∆, implying that the contraction of F + decreases the number of vertices by at least 1 2 (1 -1 e )∆ > ∆ 4 . Now, starting with an empty set of edges, in each iteration of step 2 we augment F with an edge set F + that contains at most OPT edges from each color. Therefore, by setting ∆ = √ nOPT, the maximum number of edges we pick from any given color is at most

4n ∆ OPT + |P | ≤ 4n ∆ OPT + ∆ = 5 √ nOPT .
4.3 UL-min-max s-t path: Approximating the directed case

In the following, we demonstrate that ideas similar to those presented in Subsection 4.2 can be employed to construct a directed s-t path using O( √ mOPT) arcs from any given color. Here, m = |E| and OPT denotes the cost of an optimal solution.

The algorithm. Once again, we assume that OPT is known in advance, and let ∆ = ∆(m, OPT) be a parameter whose value will be determined later.

1. F ← ∅, χ E\F ← characteristic function E \ F .
2. While dist χ E\F (s, t) > ∆ (a) Create a multi-budget maximum coverage instance by: The ground set is V ; for each arc e = (u, v) ∈ E \ F there is a corresponding singleton V e = {v}; these subsets are partitioned into {S 1 , . . . , S q }, where S i = {V e : L(e) = c i }; each S i has a budget of OPT.

(b) Approximate the instance defined above, and let F + be the collection of arcs e ∈ E \ F for which V e is picked by resulting solution.

(c) F ← F ∪ F + .

3. Let P be a shortest s-t (with respect to χ E\F ). Return P . Proof. We first demonstrate that step 2 consists of at most 2m ∆ iterations, by showing that we always have |F + | ≥ ∆ 2 . Let P * be an optimal solution, with max i |L i (P * )| = OPT. In each iteration, {V e : e ∈ P * \ F } is a feasible solution to the multi-budget maximum coverage instance defined in step 2a. Moreover, as dist χ E\F (s, t) > ∆, the latter solution satisfies

| e∈P * \F V e | ≥ ∆. Consequently, we must have |F + | ≥ | e∈F + V e | ≥ (1 -1 e )∆ > ∆ 2
. Now, starting with an empty set of arcs, in each iteration of step 2 we augment F with an arc set F + that contains at most OPT arcs from each color. Therefore, by setting ∆ = √ mOPT, the maximum number of edges P from any given color is at most

|F | + ∆ ≤ 2m ∆ OPT + ∆ ≤ 3 √ mOPT .

Arbitrary Number of Colors: Labeled Bottleneck Spanning Trees

In Corollary 3.2 we have shown that, for a fixed number of colors, both versions of weighted labeled spanning tree admit an FPTAS. In this section, we provide hardness results, exact algorithms, and approximation algorithms for the general case of an arbitrary number of colors.

Hardness results

As indicated in Subsection 1.1, WL-min-max spanning tree is known to be weakly NP-hard [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF]. Here, we show that both weighted labeled bottleneck spanning tree problems are in fact strongly NP-hard.

Theorem 5.1. Both weighted labeled bottleneck spanning tree problems are strongly NP-hard in multigraphs.

Proof. We propose a reduction from 3-partition. The input to this problem consists of a collection of integers {a 1 , . . . , a 3m }, satisfying σ 4 < a i < σ 2 , where σ = 1 m 3m i=1 a i . The objective is to decide whether there is a partition of {1, . . . , 3m} into sets S 1 , . . . , S m with i∈S j a i = σ for 1 ≤ j ≤ m. The 3-partition problem is known to be strongly NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [SP15], p. 224).

Let {a 1 , . . . , a 3m } an instance of 3-partition. We construct an instance I = (G, w, L) for both weighted labeled bottleneck spanning tree versions, where L(E) = {c 1 , . . . , c m } and G is a graph on the set of vertices u, v 1 , . . . , v 3m . For every 1 ≤ i ≤ 3m, there are m parallel edges connecting u to v i ; each of these edges is given a distinct color in {c 1 , . . . , c m } and its weight is set to a i .

The claim follows from the observation that there is a 3-partition of {a 1 , . . . , a 3m } if and only if the optimal value of the WL-min-max (respectively, max-min) spanning tree instance is at most σ (respectively, at least σ).

Corollary 5.2. Both weighted labeled bottleneck spanning tree problems are strongly NP-hard in simple graphs.

Proof. We show how to transform the multigraph defined in the proof of Theorem 5.1 into a simple graph. For this purpose, for every 1 ≤ i ≤ 3m we split the vertex v i into v i,1 , . . . , v i,m (thereby creating a unique copy for each parallel edge connecting u to v i ), add a new vertex v i,m+1 , and add the edges (v i,1 , v i,2 ), . . . , (v i,m , v i,m+1 ). For every 1 ≤ j ≤ m, the color of (v i,j , v i,j+1 ) is set to c j , but its weight depends on the problem in question. For WL-min-max spanning tree, w(v i,j , v i,j+1 ) = 0, whereas for the max-min version w(v i,j , v i,j+1 ) = mσ. In the former case, the conclusion is identical to that of the original proof. In the latter case, there is a 3-partition of {a 1 , . . . , a 3m } and only if the optimal value of the WL-max-min spanning tree instance is at least (3m 2 + 1)σ.

Exact algorithms

Broersma and Li [START_REF] Broersma | Spanning trees with many or few colors in edge-colored graphs[END_REF] devised a polynomial-time algorithm based on matroid intersection for computing a spanning tree using a maximum number of colors. Here, we prove that both unweighted labeled bottleneck spanning tree problems can also be solved in polynomial time by utilizing matroid intersection. It is interesting to observe that this result is in contrast to the weighted case, which was shown to be strongly NP-hard in Corollary 5.2. Theorem 5.3. UL-max-min spanning tree can be solved to optimality in polynomial time.

Proof. Given an instance (G, L) of UL-max-min spanning tree, with G = (V, E), we may assume without loss of generality that OPT is known in advance, since we can test 0, . . . , n-1 as candidate values for this parameter, and return the best solution found. Now, since the optimal tree picks at least OPT edges from every color in L(E) = {c 1 , . . . , c q }, it follows that there exists a forest picking exactly OPT edges from any given color. Moreover, such a forest can be efficiently constructed by computing a maximum cardinality intersection 2 of the matroids M 1 and M 2 , where

• M 1 = (E, I 1 ) is the graphic matroid, that is, I 1 = {F ⊆ E : F is a forest}. 2 See, for example, [START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF]Chap. 8].

• M 2 = (E, I 2 ) is a partition matroid, with

I 2 = {F ⊆ E : |L i (F )| ≤ OPT for every 1 ≤ i ≤ q}.
We complete the resulting forest into a spanning tree in an arbitrary way, noting that this augmentation leaves the objective value unchanged.

Theorem 5.4. UL-min-max spanning tree can be solved to optimality in polynomial time.

Proof. The algorithm for this version is nearly identical to the one given for UL-maxmin spanning tree; however, an important remark is in place. After we "guess" OPT and compute a maximum cardinality intersection F ⊆ E of M 1 and M 2 , there is no need to complete the subgraph induced by F into a spanning tree, implying that its objective value remains unchanged. This claim follows from observing that |F | = |V | -1, since the edge set of the optimal spanning tree forms a feasible solution to the matroid intersection problem we solve.

WL-min-max spanning tree: A logarithmic approximation

In what follows, we show that a matroid intersection algorithm is not only a useful tool for solving the unweighted version to optimality; rather, it can also be applied to approximate the weighted min-max version.

The algorithm. For ease of exposition, we assume without loss of generality that an estimator of the optimum W ∈ [OPT, 2 • OPT] is known in advance. Otherwise, for every 0 ≤ k ≤ ⌈log nwmax w min ⌉, we can test 2 k w min a candidate value and return the best solution found, where w min and w max denote the minimum and maximum non-zero edge weights, respectively.

1. Delete all edges of weight greater than W , and define a partition of the undeleted edges as follows:

(a) For every 1 ≤ i ≤ q and 0 ≤ k ≤ ⌊log n⌋, let E i,k be the set of edges e with L(e) = c i and w(e) ∈ ( W 2 k+1 , W 2 k ]. (b) In addition, let E free be the set of remaining edges (of weight at most W n ).

2. By applying a matroid intersection algorithm, find a spanning tree T that picks at most 2 k+1 edges from each E i,k and any number of edges from E free . Return T .

Note that the suggested algorithm is well-defined. To establish this claim, it is sufficient to show that a spanning tree satisfying the constraints of step 2 indeed exists. It is easy to verify that all edges of the optimal tree T * survive step 1 and that |T * ∩ E i,k | ≤ 2 k+1 , or otherwise there is a color c i from which T * picks edges of total weight strictly greater than W ≥ OPT.

Theorem 5.5. The edges picked by T from any given color have an overall weight of at most (4⌊log n⌋ + 6)OPT.

Proof. Consider some color c i . Then,

e∈L i (T ) w(e) = ⌊log n⌋ k=0 e∈T ∩E i,k w(e) + e∈L i (T ∩E free ) w(e) ≤ ⌊log n⌋ k=0 |T ∩ E i,k | • max e∈T ∩E i,k w(e) + |T ∩ E free | • max e∈T ∩E free w(e) ≤ ⌊log n⌋ k=0 2 k+1 W 2 k + (n -1) W n ≤ (2⌊log n⌋ + 3)W ≤ (4⌊log n⌋ + 6)OPT .
The In Theorem 2.1 we proved that both versions of weighted labeled bottleneck perfect matching are NP-hard in bicolored graphs. In this section, we provide hardness of results.

Theorem 6.1. UL-max-min perfect matching is not approximable at all, unless P=NP, even in planar bipartite graphs.

Proof. We describe a reduction from (3, B2)-SAT. An instance (C, X) this problem consists of a collection C = (C 1 , . . . , C m ) of m clauses of size exactly 3 over the set X = {x 1 , . . . , x n } of boolean variables, such that every variable occurs exactly twice positively and twice negatively. The objective is to decide whether there exists a truth assignment that satisfies all clauses. This problem was shown to be NP-complete by Berman, Karpinski and Scott [6, Thm. 1].

Given an instance I = (C, X) of (3, B2)-SAT, as described above, we construct an instance I ′ = (G, L) of UL-max-min perfect matching, where = (V, E) is a collection of n vertexdisjoint cycles of length 4 and L(E) = {c 1 , . . . , c m }: 1. Each variable x i has its own cycle of length 4, to which we refer as H(x i ).

2. Now let {C j 1 , C j 2 } ⊆ C be the clauses in which x i appears in positive form, and {C j 3 , C j 4 } ⊆ C be those in which it appears in negative form. Then, the edges of H(x i ) are colored by c j 1 , c j 3 , c j 2 , c j 4 (clockwise).

This construction guarantees that the edges with colors corresponding to clauses containing the literal x i form a matching in H(x i ), and so do the edges corresponding to clauses containing xi . Consequently, the original instance I is satisfiable if and only if there exists a perfect matching M in G using each color at least once. We conclude that it is NP-hard to between UL-max-min perfect matching instances of objective values 0 and 1.

We now present an approximation-preserving reduction from UL-min-max directed s-t path to UL-min-max perfect matching. By combining this result with Theorem 4.1, we derive new inapproximability results for the latter problem. Theorem 6.2. UL-min-max perfect matching is not (2-ǫ)-approximable for any fixed ǫ > 0, unless P=NP, even in bipartite graphs.

Proof. Since Theorem 4.1 establishes, for any fixed ǫ > 0, a lower bound of 2ǫ on the approximability of UL-min-max directed s-t path, it is sufficient to show that a ρapproximation for this problem will be implied by the existence of a ρ-approximation for UL-min-max perfect matching in bipartite graphs.

Given an instance I = (G, s, t, L) of UL-min-max directed s-t path, we transform it into an instance I ′ = (G ′ , L ′ ) of UL-min-max perfect matching, where G ′ is an undirected bipartite graph. The latter is created by splitting each vertex v ∈ V \ {s, t} to v in and v out , followed by adding the edge (v in v out We also cancel the orientation, and replace each arc by a corresponding edge of identical color. Finally, each new edge of the form (v in , v out ) is given a unique color, c ′ v . We first claim that OPT(I ′ ) ≤ OPT(I). To this end, consider a directed path s = v 1 , v 2 , . . . , v k = t constitutes an optimal solution to I. Then, by picking the union of {(v i out , v i+1 in ) : 1 ≤ i ≤ k -1} and {(v in , v out ) : v ∈ V \ {v 1 , . . . v k }} we obtain a perfect matching in G ′ whose objective value is exactly OPT(I). Consequently, it remains to show that, given a perfect matching M in G ′ , we can efficiently find a directed s-t path in G whose objective value does not exceed that of M The reduction described above guarantees that there exists a collection of vertices V M ⊆ V such that M consists of an edge set {(v in , v out ) : v ∈ V M } and an edge set {(u out , v in ) : u, v ∈ V \ V M }. It is not difficult to verify that the latter set induces a directed s-t path in G (and quite possibly one or more directed cycles). The objective value of this path is upper bounded by that of M .

7 Arbitrary Number of Colors: Labeled Bottleneck s-t Cuts 2.2, we proved that WL-min-max s-t cut is strongly NP-hard. However, careful examination reveals that the instances resulting from our reduction are not necessarily planar. Since the maximum s-t cut problem is polynomially solvable in planar graphs [START_REF] Orlova | Finding the maximum cut in a graph[END_REF][START_REF] Hadlock | Finding a maximum cut of a planar graph in polynomial time[END_REF], it is of interest to show that the former problem remains computationally intractable in such graphs. We also provide new inapproximability results for UL-max-min s-t cut.

Theorem 7.1. UL-min-max s-t cut is not (2ǫ)-approximable in planar graphs for any fixed ǫ > 0, unless P=NP.

Proof. We propose a reduction from the set packing problem, whose definition is given in Theorem 4.1. Let I = (S, X, k) be a set packing instance, where S = {S 1 , . . . , S m } is a family of sets over a ground set X = {x 1 , . . . , x n }. We define an instance of UL-min-max s-t cut, consisting of a planar graph G = (V, E) whose edges are given colors from the set {c 0 , c 1 , . . . , c n }. The graph initially a collection of k interior-disjoint paths 1 , . . . , P k connecting s to t, each of length m. for each path P i , we perform the following modification: For every 1 ≤ j ≤ m, the j-th edge e j = (x, y) of P i is replaced by a collection of |S j | interior-disjoint paths of length 2 connecting x to y; letting S j = {x j 1 , . . . , x jp }, we spread the colors {c j 1 , . . . , c jp } on the first edges of these |S j | paths, and set the color of their second edges to c 0 . The theorem follows from the observation that I has a set packing of size at least k if and only if the objective value of the newly defined UL-min-max cut instance is at most 1.

Theorem 7.2. UL-max-min s-t cut is not approximable at all in planar multigraphs, unless P=NP.

Proof. We describe a reduction from the satisfiability problem, whose instances consist of a collection C = (C 1 , . . . , C m ) of clauses over a set X = {x 1 , . . . , x n } of boolean variables. The goal is to decide whether there is a truth assignment that satisfies all clauses. This problem is known to be NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [LO1], p. 259).

We construct an instance of UL-max-min s-t cut, where G = (V, E) and L(E) = {c 1 , . . . , c m }. The set of vertices is V = {s, t, v 1 , . . . , v n }, and there are n i (respectively, ni parallel edges joining s (respectively, t) and v i , where n i (respectively, ni ) is the number of i (respectively, xi ) occurrences. Finally, the colors of these edges are given by the clauses containing x i (respectively, xi ). It is not difficult to verify that I is satisfiable if and only if there exists an s-t cut in G whose objective value is at least 1.

Theorem 4 . 2 .

 42 By setting ∆ = √ nOPT, the subgraph induced by F ∪ P picks at most 5 √ nOPT edges from any given color.

Theorem 4 . 3 .

 43 By setting ∆ = √ mOPT, the directed path P traverses at most 3 √ mOPT arcs from any given color.

  second inequality holds since |T ∩ E i,k | ≤ 2 k+1 for every 0 ≤ k ≤ ⌊log n⌋, and since |T ∩ E free | ≤ n -1. The last inequality follows from the assumption W ≤ 2 • 6 Arbitrary Number of Colors: Labeled Bottleneck Perfect Matchings

On the other hand, the complexity of this problem in general bipartite graphs is still open.

Acknowledgments. We thank Shlomi Rubinstein for suggesting the reduction in Theorem 4.1, which simplified our original proof.


Stéphane Devismes

David Ilcinkas

Colette Johnen

Sch éma g én éral auto-stabilisant et silencieux de constructions de type arbres couvrants †

Keywords: Algorithmes distribués, auto-stabilisation, arbre couvrant, élection de leader, plus courts chemins

Nous proposons un schéma général, appelé Scheme, qui calcule des structures de données de type arbres couvrants dans des réseaux quelconques. Scheme est auto-stabilisant, silencieux et malgré sa généralité, est aussi efficace. Il est écrit dans le modèle à mémoires localement partagées avec atomicité composite, et suppose un démon distribué inéquitable, l'hypothèse la plus faible concernant l'ordonnancement dans ce modèle. Son temps de stabilisation est d'au plus 4n maxCC rondes, où n maxCC est le nombre maximum de processus dans une composante connexe. Nous montrons également des bornes supérieures polynomiales sur le temps de stabilisation en nombre de pas et de mouvements pour de grandes classes d'instances de l'algorithme Scheme. Nous illustrons la souplesse de notre approche en décrivant de telles instances résolvant des problèmes classiques tels que l'élection de leader et la construction d'arbres couvrants.

Introduction

A self-stabilizing algorithm is able to recover a correct behavior (defined by a set of legitimate configurations) in finite time, regardless of the arbitrary initial configuration of the system, and therefore also after a finite number of transient faults. Among the vast self-stabilizing literature, many works (see [START_REF] Gärtner | A survey of self-stabilizing spanning-tree construction algorithms[END_REF] for a survey) focus on spanning-tree-like constructions, i.e. constructions of specific distributed spanning treeor forest-shaped data structures. Most of these constructions achieve an additional property called silence: a silent self-stabilizing algorithm converges within finite time to a configuration from which the values of the communication registers used by the algorithm remain fixed. Such a configuration is called terminal. Silence is a desirable property, as it facilitates composition of different algorithms and may utilize less communication operations and communication bandwidth. We consider the locally shared memory model with composite atomicity, which is the most commonly used model in self-stabilization. In this model, n processes communicate according to a given communication network using a finite number of locally shared registers, called variables. Each process can read its own variables and those of its neighbors, but can write only to its own variables. In this model, executions proceed in atomic steps and the asynchrony of the system is captured by the notion of daemon. The weakest (i.e., the most general) daemon is the distributed unfair daemon, meaning that while the configuration is not terminal, the daemon should select at least one enabled process, maybe more. Hence, solutions stabilizing under such an assumption are highly desirable, because they work under any other daemon assumption. Moreover, under an unfair daemon, the stabilization time can also be bounded in terms of steps (and moves, i.e., local state updates), which capture the execution time according to the fastest process, and not only in terms of rounds, which capture the execution time according to the slowest process. Note that if the number of moves (and thus steps) is unbounded, this means that there are processes whose moves do not make the system progress, hence wasting resources. There are many self-stabilizing algorithms proven under the distributed unfair daemon. However, analyses of the stabilization time in steps (or moves) is rather unusual and this may be an important issue. Indeed, recently, several self-stabilizing algorithms which work under a distributed unfair daemon have been shown to have an exponential stabilization time in steps in the worst case [DJ16, ACD + 17].

Contribution. We propose a general scheme, called Algorithm Scheme, to compute spanning-tree-like data structures on bidirectional weighted networks of arbitrary (not necessarily connected) topology. Scheme is self-stabilizing and silent. It is written in the locally shared memory model with composite atomicity, assuming the distributed unfair daemon. Despite its versatility, Scheme is efficient. Indeed, its stabilization time is at most 4n maxCC rounds, where n maxCC is the maximum number of processes in a connected component. Moreover, its stabilization time in moves is polynomial in usual cases. Precisely, we exhibit polynomial upper bounds on its stabilization time in moves that depend on the particular problems we consider. To illustrate the versatility of our approach, we propose instantiations of Scheme solving classical spanning-tree-like problems. Assuming an input set of roots but no identifiers, we propose two instantiations to compute a spanning forest of unconstrained, resp. shortest-path, trees, with non-rooted components detection. ‡ The first instantiation stabilizes in O(n maxCC n) moves, which matches the best known step complexity for spanning tree construction [START_REF] Cournier | A new polynomial silent stabilizing spanning-tree construction algorithm[END_REF] with explicit parent pointers. The second instantiation stabilizes in O(W max n maxCC 3 n) moves (W max is the maximum weight of an edge). This move complexity also matches the best known move complexity for this problem [START_REF] Devismes | Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps[END_REF]. Then, assuming the network is identified (i.e., processes have distinct IDs), we propose two instantiations of Scheme for electing a leader in each connected component and building a spanning tree rooted at each leader. The first instantiation stabilizes in O(n maxCC 2 n) moves, matching the best known step complexity for leader election [ACD + 17]. The second instantation stabilizes in O(n maxCC 3 n) moves but the built spanning tree is a Breadth first search tree. From these various examples, one can easily derive other silent self-stabilizing spanning-tree-like constructions.

Algorithm Scheme

• P root(u) ≡ canBeRoot u ∧ st u = C ∧ parent u = ⊥ ∧ d u = distRoot(u) • P abnormalRoot(u) ≡ ¬P root(u)∧ st u = I∧ [parent u / ∈ Γ(u)∨ st parentu = I ∨ d u ≺ d parentu ⊕ ω u (parent u )∨ (st u = st parentu ∧ st parentu = EB)] • P reset(u) ≡ st u = EF ∧ P abnormalRoot(u) • P updateNode(u) ≡ (∃v ∈ Γ(u) | st v = C ∧ d v ⊕ ω u (v) ≺ d u ) • P updateRoot(u) ≡ canBeRoot u ∧ distRoot(u) ≺ d u • P nodeImp(u) is problem dependent. If P nodeImp(u)
, then P updateNode(u) ∨ P updateRoot(u); if P updateRoot(u) then P nodeImp(u). P nodeImp(u) only depends on the values of st u , d u , P updateRoot(u), and min

(v∈Γ(u) ∧ stv=C) (d v ⊕ ω u (v)).

Functions

• beRoot(u): st u := C; parent u := ⊥; d u := distRoot(u);

• computePath(u): st u := C; parent u := argmin (v∈Γ(u) ∧ stv=C) (d v ⊕ ω u (v)); d u := d parentu ⊕ ω u (parent u ); if P updateRoot(u) then beRoot(u); • Children(u) : {v ∈ Γ(u) | st u = I ∧ st v = I ∧ parent v = u ∧ d v d u ⊕ ω v (u) ∧ (st u = st v ∨ st u = EB)}. Rules R U (u): st u = C ∧ P nodeImp(u) → computePath(u); R EB (u): st u = C ∧ ¬P nodeImp(u) ∧ (P abnormalRoot(u) ∨ st parentu = EB) → st u := EB; R EF (u): st u = EB ∧ (∀v ∈ Children(u) | st v = EF) → st u := EF; R I (u): P reset(u) ∧ ¬canBeRoot u ∧ (∀v ∈ Γ(u) | st v = C) → st u := I; R R (u): (P reset(u) ∨ st u = I) ∧ [canBeRoot u ∨ (∃v ∈ Γ(u) | st v = C)] → computePath (
u); ‡. By non-rooted components detection, we mean that every process in a connected component that does not contain the root should eventually take a special state notifying that it detects the absence of a root.

Schéma général auto-stabilisant et silencieux de constructions de type arbres couvrants

According to the specific problem we consider, we may want to minimize the weight of the trees using some kind of distance. So, we assume that each edge {u, v} has two weights: ω u (v) denotes the weight of the arc (u, v) and ω v (u) denotes the weight of the arc (v, u). Both values belong to the domain DistSet. Let (DistSet, ⊕, ≺) be an ordered magma, i.e., ⊕ is a closed binary operation on DistSet and ≺ is a total order on this set. The definition of (DistSet, ⊕, ≺) is problem dependent. We assume that, for every edge {u, v} of E and for every value d of DistSet, we have

d ≺ d ⊕ ω u (v) and d ≺ d ⊕ ω v (u).
The silent self-stabilizing algorithm Scheme (see Algorithm 1 for its code), converges to a terminal configuration where a specified spanning forest (maybe a single spanning tree) is distributedly defined. Each process u uses as input a name pname u (pname u =⊥, for every process u if the network is anonymous), a constant boolean value canBeRoot u , which is true if u is allowed to be root of a tree, and in this latter case a problem dependent distance distRoot(u), used when u is a root. Our scheme also uses a problem dependent predicate P nodeImp(u), with specific properties, that indicates to u whether its current estimated distance to the root (variable d u ) can be improved (decreased). Then, a legitimate configuration is defined as follows.

Definition 1 (Legitimate configuration) A legitimate configuration of Scheme is a configuration where every process u is in a legitimate state, i.e., u satisfies ¬P nodeImp(u) and one of the following conditions:

1. P root(u); 2. there is a process satisfying canBeRoot in the connected component V u containing u, st u = C (for Correct), and u ∈ Children(parent u ); 3. there is no process satisfying canBeRoot in V u and st u = I (for Isolated).

In any given configuration, every process u satisfies exactly one of the following cases: (1) u is isolated, i.e. it has status I; (2) u is a normal root, i.e., P root(u) holds; (3) u points to some neighbor and the state of u is coherent w.r.t. the state of its parent, i.e., u ∈ Children(parent u ); (4) u is an abnormal root, i.e., P abnormalRoot(u) holds. In that latter case, we want to correct the state of u while avoiding the following situation: u leaves its abnormal tree T ; this removal creates some new abnormal trees, each of those being rooted at a previous child of u; and later u joins one of those (created) abnormal trees. (This issue is sometimes referred to as the count-to-infinity problem.) Hence, the idea is to freeze T , before removing any node from it. This is done as in a "Propagation of Information with Feedback": From an abnormal root, the status EB, for Error Broadcast, is broadcast down in the tree using rule R EB . Then, once the EB-wave reaches a leaf, the leaf initiates a convergecast EF-wave (Error Feedback) using rule R EF . Once the abnormal root gets status EF, the tree is frozen and can be safely deleted from its abnormal root toward its leaves. At this point, an abnormal root u can either become the root of a new normal tree or join another tree, via rule R R (u), depending on which option gives it the smaller distance, or u becomes isolated via rule R I (u) if ¬canBeRoot u and u has no neighbor with status C. In parallel, rules R U are executed to reduce the weight of the trees, if necessary, i.e., if P nodeImp(u) holds. A detailed analysis of our algorithm allows us to prove the following result.

Theorem 1 Any terminal configuration of Algorithm Scheme is legitimate, and vice versa. Moreover, Algorithm Scheme is silent self-stabilizing under the distributed unfair daemon, has a bounded move (and step) complexity, and stabilizes in at most 4n maxCC rounds from any configuration.

Roughly speaking, we define a GC-segment, for any connected component GC, as a part of execution between two removals of a non-frozen abnormal tree. A key property of our algorithm is that non-frozen abnormal trees are never created. Combined with other properties, this allows us to prove that there are at most n maxCC + 1 GC-segments. The sequence of rules executed by a process u of GC during a GC-segment belongs to the following language: (R I + ε)(R R + ε)(R U ) * (R EB + ε)(R EF + ε). This further leads to the two following key results.

Theorem 2 If the number of R U executions during a GC-segment by any process of GC is bounded by nb U, then the total number of moves (and steps) in any execution is bounded by (nb U + 4)(n maxCC + 1)n.

Theorem 3 When all weights are strictly positive integers bounded by W max , and ⊕ is the addition operator, the stabilization time of Scheme in moves (and steps) is at most (W max (n maxCC -1) 2 + 5)(n maxCC + 1)n.

Algorithm 1 :

 1 Algorithm Scheme, code for any process u Inputs • canBeRoot u : a boolean value; it is true if u can be a root • pname u : name of u, that belongs to IDs = N ∪ {⊥} Variables • st u ∈ {I,C, EB, EF}: the status of u • parent u ∈ {⊥} ∪ Lbl: a pointer to a neighbor or ⊥ • d u : the distance value associated to u Predicates

This study was partially supported by the ANR project DESCARTES: ANR-16-CE40-0023 and ANR project ESTATE: ANR-16-CE25-0009-03. A complete version of this work can be found in the technical report https://hal.archives-ouvertes.fr/hal-01667863.

Unconstrained and Shortest-Path Spanning Forest. Given an input set of processes rootSet, and assuming (strictly) positive integer weights for each edge, Algorithms Forest and SPF are the instantiations of Scheme with the parameters given in Algorithm 2.

Algorithm 2: Parameters for any process u in Algorithms Forest and SPF

Inputs:

(1) canBeRoot u is true if and only if u ∈ rootSet, (2) pname u is ⊥, and (3)

, and (4) distRoot(u) = 0.

Predicate:

Forest: P nodeImp(u) ≡ P updateRoot(u) SPF:

P nodeImp(u) ≡ P updateNode(u) ∨ P updateRoot(u)

Algorithm Forest (resp. SPF) computes (in a self-stabilizing manner) an unconstrained (resp. shortestpath) spanning forest in each connected component of G containing at least one process of rootSet. The forest consists of trees rooted at each process of rootSet. Moreover, in any component containing no process of rootSet, the processes eventually detect the absence of roots by taking the status I (Isolated).

By Theorem 2 (resp. Theorem 3), Algorithms Forest and SPF self-stabilize to a terminal legitimate configuration in at most O(n maxCC n) (resp. O(W max n maxCC 3 n)) moves, where W max is the largest edge weight.

Leader Election Algorithms. Assuming the network is identified (each node has a unique identifier), Algorithm LEM and LEM BFS are the instantiations of Scheme with the parameters given in Algorithm 3. (2) (id In each connected component, Algorithm LEM and LEM BFS elect the process u (i.e., P leader(u) holds) of smallest identifier and builds a tree rooted at u that spans the whole connected component. Algorithm LEM builds a tree of arbitrary topology; algorithm LEM BFS builds a breadth-first-search tree.

By Theorem 3, Algorithm LEM BFS, self-stabilizes to a terminal legitimate configuration in at most O(n maxCC 3 n) moves. By Theorem 2, Algorithm LEM, self-stabilizes to a terminal legitimate configuration in at most (2n maxCC + 4)(n maxCC + 1)n moves (i.e. O(n maxCC 2 n) moves) since during a GC-segment, a process can only execute R U to improve its ID.


Cédric Demonceaux
email: cedric.demonceaux@u-picardie.fr

Pascal Vasseur
email: pascal.vasseur@u-picardie.fr

Claude Pégard
email: claude.pegard@u-picardie.fr

Omnidirectional vision on UAV for attitude computation

Unmanned Aerial Vehicles (UAVs) are the subject of an increasing interest in many applications. Autonomy is one of the major advantages of these vehicles. It is then necessary to develop particular sensors in order to provide efficient navigation functions. In this paper, we propose a method for attitude computation catadioptric images. We first demonstrate the advantages of the catadioptric vision sensor for this application. In fact, the geometric properties of the sensor permit to compute easily the roll and pitch angles. The method consists in separating the sky from the earth in order to detect the horizon. We propose an adaptation of the Markov Random Fields for catadioptric images for this segmentation. The second step consists in estimating the parameters of the horizon line thanks to a robust estimation algorithm. We also present the angle estimation algorithm and finally, we show experimental results on synthetic and real images captured from an airplane.

I. INTRODUCTION

Unmanned Aerial Vehicles (UAV) have proved their usefulness in many applications. However, their autonomy requires a lot of abilities such as being able to evaluate their global position, their altitude or their attitude in order to control their stability. In this work, we propose to use a central catadioptric vision sensor in order to compute the attitude of a UAV. With this system, we are able to evaluate the roll (ρ) and pitch (ψ) angles without any additional inertial or rate sensors. The idea consists in using the particular geometric characteristics of the catadioptric sensor in order to compute precisely these angles. Generally, attitude computation by vision is based on the detection of the horizon in the image and on the estimation of the angle between the horizon and a horizontal reference line. In [START_REF] Ettinger | Vision-guided flight stability and control for micro air vehicles[END_REF], the authors use a perspective camera and they consider the horizon as a straight line. The roll angle is then given by the inverse tangent of the slope of the horizon line and the pitch angle is approximated by the percentage of sky in the image. Then, they are looking for the horizon line in the image which maximizes an optimization criterion which tends to separate the earth from the sky. In [START_REF] Todorovic | Sky/ground modeling for autonomous mav flight[END_REF], an improved version of the previous algorithm which better manages the variation of the appearance of the sky is presented. In this way, they propose to integrate a texture representation in order to improve the first model which only relies on color information. A statistical framework with prior models of the sky and the earth is also used for the adaptation of the algorithm to the variations of appearance. In spite of the interesting results obtained with these approaches, the use of a single perspective camera generates several drawbacks. First, we only obtain a partial view of the environment and important occlusions in the horizon can have a serious influence on the final result. Second, the horizon is visible only in a particular interval of roll and pitch values. If the UAV gets out of this interval, the final image is exclusively made of sky or earth and the horizon can not be detected. Third, with a perspective camera, it is only possible to compute the roll angle while the pitch is only approximated thanks to a hypothesis on the altitude of the UAV. In this work, we propose to use an omnidirectional visual sensor in order to compute the attitude of a UAV. This kind of sensor has already been used for the navigation of UAVs as in [START_REF] Hrabar | Omnidirectional vision for an autonomous helicopter[END_REF] and omnidirectional vision has proved its usefulness in a lot of robotic applications [START_REF] Benosman | Panoramic Vision: Sensors, Theory, Applications[END_REF]. Omnidirectional vision and more particularly catadioptric vision consists in associating a convex mirror with a projective camera whose optical axis is aligned with the axis of the mirror [START_REF] Benosman | Panoramic Vision: Sensors, Theory, Applications[END_REF]. The main advantage of these sensors is the acquisition of an omnidirectional image with a single shot. In our application of UAV attitude computation, omnidirectional vision presents the following advantages: first, a complete surrounding of the UAV can be captured and the horizon is totally visible. The possible occlusions will then have a lower impact on the estimation of the final results. Second, whatever the attitude of the UAV, the horizon is always present in the image, even partially, and the angles can always be computed. Third, we are able to compute the roll angle but also the pitch angle without any prior hypothesis, contrary to the applications including a perspective camera. However, catadioptric vision also presents some drawbacks. For example, a catadioptric image contains significant deformations due to the geometry of the mirror and to the sampling of the camera [START_REF] Daniilidis | Image processing in catadioptric planes: Spatiotemporal derivatives and optical flow computation[END_REF] and these deformations have important consequences for the image processing. So, direct application of classical operators can not provide satisfactory results. We then also show in this paper an adaptation of the Markov Random Fields (MRFs) which permits to treat the images while taking into account these deformations. We use this adaptation in order to detect the horizon in the catadioptric image. Once this horizon line is detected, we use the particular geometric characteristics of the catadioptric sensor in order to compute the attitude of the UAV.

In the rest of the paper, we present in Section 2 the model of image formation and how the horizon is projected in the catadioptric image. Section 3 is devoted to the adaptation of MRFs to the catadioptric images and to its implementation for the ground/sky segmentation. In Section 4, we develop the estimation of the parameters of the horizon and consequently of the roll and pitch angles. Experimental results and a discussion are proposed in Section 5. Finally, we conclude in Section 6 with a summary and perspectives.

II. IMAGE FORMATION AND HORIZON PROJECTION

A. Central Catadioptric Image Formation

Baker and Nayar classified catadioptric sensors into two categories depending on the number of viewpoints [START_REF] Baker | A theory of catadioptric image formation[END_REF]. Sensors with a single viewpoint, named central catadioptric sensors, permit a geometrically correct reconstruction of the perspective image from the original catadioptric image. This category is made of a parabolic mirror associated to an orthographic camera and hyperbolic, elliptic and plane mirrors with a perspective camera. The second category with several viewpoints has much less significant geometric properties and is made of the other possibilities of associations between mirrors and cameras. In this paper, we are only interested in central sensors, for which Geyer and Daniilidis have demonstrated the equivalence with a two-step projection via a unitary sphere centered on the focus of the mirror (the single viewpoint) [START_REF] Geyer | Catadioptric projective geometry[END_REF]. This two-step projection first consists in projecting a 3D point to the sphere from the center of the sphere. The next step consists in projecting the point on the sphere to the image plane from a point O p placed on the optical axis (Fig 1). The position of this point of projection O p and of the image plane are determined with the calibration of the sensor.

B. Projection from the Image to the Sphere

From the equivalence model developed in [START_REF] Geyer | Catadioptric projective geometry[END_REF] and showed in Figure 1, we have :

x s = γx w y s = γy w z s = γz w (1)
The equation of the unitary sphere is x 2 s + y 2 s + z 2 s = 1 and then gives :

γ = 1 x 2 w + y 2 w + z 2 w ( 2
)
The coordinates of point P i on the image plane are then obtained from the perspective projection of P s and parameters (ξ,ϕ) of the mirror :

xs ξ-zs = x ξ+ϕ ys ξ-zs = y ξ+ϕ z = -ϕ, (3)
where (x, y, z) are the coordinates of point P i expressed in the metric system and ξ and ϕ define the shape of the mirror (see [START_REF] Barreto | Issues on the geometry of central catadioptric image formation[END_REF] for further details on their signification).

       x = (ξ+ϕ)xw ξ √ x 2 w +y 2 w +z 2 w -zw y = (ξ+ϕ)yw ξ √ x 2 w +y 2 w +z 2 w -zw z = -ϕ (4)
In the image frame, we finally obtain :

u v = α u 0 u 0 0 α v v 0   x y 1   , (5)
where (u, v) are the coordinates of P i in pixels and (α u , α v , u 0 , v 0 ) are the intrinsic parameters of the camera. In order to perform the calibration with this model, we place the catadioptric system in a cube with a grid of points on each side. In this way, the points of the pattern are distributed over the whole catadioptric image. The pattern contains 144 points and we estimate six extrinsic parameters (3 rotations and 3 translations): the parameters ξ and ϕ of the mirror as well as the intrinsic parameters of the camera (α u , α v , u 0 , v 0 ). The estimation is performed by the minimization of the quadratic error between the selected points and those computed by the model. With this method, we are then able to calibrate any central catadioptric sensor without restriction about the shape of the mirror as in the method proposed in [START_REF] Ying | A theory of catadioptric image formation[END_REF].

C. Central Catadioptric Projection of the Horizon

As demonstrated in [START_REF] Ying | A theory of catadioptric image formation[END_REF], a 3D sphere projects on the equivalent sphere in a small circle, and then on the catadioptric image plane in an ellipse. Consequently, the attitude computation consists in looking for an ellipse in the omnidirectional image or a small circle on the equivalent sphere which corresponds to the horizon. The geometrical properties of the equivalent sphere allow to deduce the roll and pitch angles. Indeed, if we consider Figure 2, we can note that the normal of the projected horizon on the sphere, which is also confounded with the line passing through the center of the sphere of equivalence and through the center of the earth represents in fact the attitude of the UAV depending on the position of the optical axis. Then, the computation of the coordinates of the optical axis is sufficient in order to deduce the roll and pitch angles. From the previous considerations, the complete algorithm will then first consists in segmenting the catadioptric image in order to separate the sky from the ground and in extracting the points of the horizon. Next, we back project the points of the horizon on the sphere of equivalence thanks to the parameters obtained with the calibration. Finally, we estimate the best plane which passes through the points of horizon on the sphere and we deduce its normal and consequently the roll (ρ) and pitch (ψ) angles.

III. SKY/GROUND SEGMENTATION IN CATADIOPTRIC IMAGES

This section deals with the problem of horizon detection. To do this, we choose an MRF modeling in order to segment the omnidirectional image in two parts, one corresponding to the sky and the other one to the ground.

A. Limitation of Classical MRFs in Omnidirectional Images

Since the eighties and thanks to Besag [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF], MRFs have permitted to solve many problems in image processing such as image segmentation, image restoration, motion detection and so on. However, they become unsuitable if they are applied in the same way for catadioptric images. Indeed, MRFs use a local dependence between pixels from a predefined neighborhood, which has to be reconsidered because of the distortions of catadioptric images.

In the case of classical images, the neighboring systems are defined by the closest pixels (generally, neighboring of order 1 or 2). However, this kind of neighborhood is not suited to catadioptric images because of the distortions generated by the mirror. Indeed, a pixel at a distance d of pixel p does not have the same influence on the latter if p is placed either in the center of the image or in its periphery.

B. An Adapted Neighborhood

To find a neighboring more appropriate to an omnidirectional image, we propose to use the equivalence between the catadioptric projection and the sphere (Fig. 1).

In the model of equivalence [START_REF] Geyer | Catadioptric projective geometry[END_REF], the mapping function is equivalent to a projection of a 3D point P w to a point P s on the sphere, followed by a projection from a point on the optical axis to point P i on the image plane (Fig. 1). The center of the sphere is equal to the mirror focus and its radius is function of the latus rectum of the mirror. The position of the center of projection in the second projection depends on the shape and the dimensions of the mirror.

Let us pose P i an omnidirectional image point of polar coordinates (u, v) = (D cos(φ), D sin(φ)) in camera coordinate system which center corresponds to the mirror axis. The equivalent point P s on the sphere has then as spherical coordinates (1, θ, φ) in the coordinate system associated with the equivalent sphere of radius 1:

θ = arccos ξD 2 -(ξ + ϕ) (ξ + ϕ) 2 + D 2 (1 -ξ 2 ) D 2 + (ξ + ϕ) 2 .
(6) This change of space makes possible to overcome the distortions induced by the sensor. To create a spatial dependence between the points, it thus appears more natural to consider points P s instead of points P i by associating to these points a neighborhood defined on the equivalent sphere. Let Π the projection for which any site s (pixel of the omnidirectional image) associates its equivalent point P s in spherical coordinates on unitary sphere S 2 (Fig 1 ),

Π : S → S 2 s = (u, v) → (1, θ s , φ s ) (7)
Then we define the new neighborhood as follows (Fig 3 ):

∀s ∈ S, Π(s) = (1, θ s , φ s ) V s =    t ∈ S, t = s Π(t) = (1, θ t , φ t ) such as |θ t -θ s | ≤ 1 N and (|φ t -φ s | ≤ 1 M or |φ t -φ s | ≥ 2π -1 M )    , (8)
where N and M are two fixed constants which define the order of the neighborhood. Let us note that we do not carry out any sampling on the equivalent sphere. Indeed, the new neighborhood is defined only starting from the points of the sphere corresponding to pixels of the omnidirectional image.

We have shown in [START_REF] Demonceaux | Champs de markov pour le traitement d'images catadioptriques[END_REF] that this neighborhood is more appropriate for omnidirectional images than a classical neighborhood used for perspective images.

C. Markovian Formulation of Sky/Ground Segmentation

We want to divide the image into two groups, one which corresponds to the sky and the other one to the ground in omnidirectional image sequence I(t). To achieve this, we define a Markovian modeling as follows. Let us pose E(t) = {e s (t), s ∈ S} the label field where e s can take two values {0, 1} (0= site of the sky, 1 = site of the ground), O(t) = {o s (t), s ∈ S} is the observation field and where S is the set of pixels in the image. At each site s, observation o s is supplied by color component c(s) = (c 1 (s), c 2 (s), c 3 (s)) expressed in the space described in [START_REF] Swain | Color indexing[END_REF]:

c 1 = r -g, c 2 = 2b -r -g, c 3 = r + g + b,
with (r, g, b) the color space coordinates in the (red,green,blue) color space. The data-driven potential q at each site is defined by:

q(e s , o s ) = (c(s) -M es ) t Σ -1 es (c(s) -M es ) (9)
the two regions being modeled by a Gaussian model (M es , Σ es ). Then, penalization term v which favors the spatial homogeneity is :

v(e s , e r ) = µ(1 -δ(e s -e r )) (10)
where µ is a positive constant and δ is the Kronecker symbol. Let us note C sr = {c ∈ C|s ∈ c et r ∈ c}, the maximum a posteriori (MAP) criterion of our modelization is the minimum of:

U (e, o) = s∈S q(e s , o s ) + <s,r>∈C 1 card(C sr ) v(e s , e r ) (11)
where C are the cliques defined using neighborhood V (formula ( 8)). At time t = 0, the two Gaussian models defining the Sky and the Ground are evaluated using a disc at the periphery on the omnidirectional image for the sky and a disc at the image center for the ground. Then, the Gaussian models are estimated using the label field of the previous estimation e(t -1).

IV. HORIZON ESTIMATION AND ATTITUDE COMPUTATION

Once the horizon has been detected in the image, we want to compute the normal of the plane which contains the projection of the horizon on the sphere. This method then first consists in using the results of the calibration in order to project the points from the image to the sphere. Next, we propose to estimate the small circle parameters thanks to a robust M-estimator of Tukey [START_REF] Zhang | Parameter estimation techniques: A tutorial with application to conic fitting[END_REF] and finally we obtain the roll and pitch angles from the coordinates of the normal of the small circle.

The aim of this step consists in estimating the plane which passes through the points of the horizon on the sphere. Let us consider N horizon points projected on the sphere with coordinates (x i s , y i s , z i s ) with i = 1, . . . , N . In order to avoid the outlying points, we need to determine Θ = (A, B, C) T as the solution of :

Θ = arg min Θ i Γ(r i ) r i = Ax i s + By i s + C + z i s . ( 12
)
where Γ is the robust M-estimator of Tukey's biweight [START_REF] Huber | Robust Statistics[END_REF]. Solution Θ of ( 12) is computed by an Iteratively Reweighted Least Squares (IRLS):

Θ = min Θ i=1 w i (r i ) 2 , (13)
where

w i = 1 r i ∂Γ ∂x (r i ).
The normal of the horizon plane has then the coordinates (A, B, 1) and we can compute pitch (ψ) and roll (ρ) angles as follows :

ψ = A | A | × arccos 1 √ 1 + A 2 (14) ρ = -B | B | × arccos | cos(-ψ) -A sin(-ψ) | (cos(-ψ) -A sin(-ψ)) 2 + B 2 (15)
V. EXPERIMENTAL RESULTS

A. Horizon Detection

The results of the horizontal detection on three different sequences are presented on Figure 4. These images have been taken with our sensor from an altitude of 2 meters. In this figure, the white line corresponds to the limit between the sky and the ground. The minimization of equation( 11) is performed with the HCF algorithm [START_REF] Chou | The theory and practice of bayesian image labeling[END_REF]. We see that Markovian modeling permits to correctly delimit the sky and the ground, even in the presence of trees ( . In this case, the M-estimator plays an important role. Indeed, as long as the number of points which delimits this badly labelled zone is weak compared to the number of points which detect the horizon correctly, the M-estimator will not take into account these outliers.

B. Attitude Computation

Since it is difficult to obtain the ground truth for the attitude of a UAV synchronized with the correspondent image, we evaluate our algorithm with synthetic images. We then use a synthetic catadioptric image generator with the real intrinsic parameters of our catadioptric sensor. The altitude of the UAV is constant and equal to 500 meters. We can then easily compute the occluding contour of the Earth, and consequently its projection on the catadioptric image plane. 11,000 artificial images of the projection of the horizon were generated with different combinations of roll and pitch angles. In order to study the sensitivity of the algorithm to image noise, we add outliers to the list of points which constitute the projected horizon. The number of outliers varies from 0 to 100% of the number of horizon points and the positions of these outliers are randomly computed.

In Figure 5, the 3D plots show the mean error expressed in degrees for the roll and pitch angles for the different combinations of angles, noise and sampling. We can see that this error is approximately equal to 3 degrees when the number of outliers is low and increases to 5 degrees when the number of outliers is high. If we analyze our results more in depth, the main errors are obtained when the pitch and roll angles are close to 90 • or -90 • . If we consider only the interval equal to [-60 • , 60 • ] for both angles, the error becomes less than 1 degree. This effect is due to the projection of the horizon which becomes a piece of ellipse in the image. The estimation of the parameters of the great circle is then more delicate and some errors may occur.

In table I, we present the roll and pitch angles of Figure 5. For each one of these images, we do not have the ground truth attitude but we can estimate that the results are coherent with the presented images. Finally, in Figure 6, we propose some results obtained with the sensor mounted on an aerial platform. The red pixels correspond to the detected pixels of the horizon and in the bottom left corner, the estimated roll and pitch angles are presented. We can see that the evolution of the values is totally coherent with the movement perceived in the sequence. The complete sequence is available at the following address http://www.crea.u-picardie.fr/∼vasseur. Figure 7 presents the evolution of the roll and pitch angles during a sequence of 1000 images. We can note that for each image the angles are always computed and that there is no outlier in the estimated values. We can also see that the algorithm offers a good rate of repeatability since between successive images with a similar attitude, the angle values do not differ significantly.

VI. SUMMARY AND CONCLUSION

In this paper, we present an attitude sensor for UAVs based on a central catadioptric vision sensor. This sensor presents several advantages compared to a perspective camera such as robustness even in case of occlusions in the horizon, the

Fig. 1 .

 1 Fig. 1. Equivalence between the catadioptric projection and the two-step mapping via the sphere.

Fig. 2 .

 2 Fig. 2. Relation between the projections of the horizon and the roll (ρ) and pitch (ψ) angles.

Fig. 3 .

 3 Fig. 3. (a) Neighborhood at the periphery of the image, (b) Neighborhood in the center of the image.

  Fig 4(c) and Fig 4(d)). On the other hand, when the texture of the ground is similar to that of the sky, the first one is labelled as belonging to the sky (Ex: snow Fig 4(e) and Fig 4(f))

Fig. 4 .

 4 Fig. 4. Results of Sky/Ground Segmentation using the Markovian modeling with a neighborhood adapted for omnidirectional image, µ = 10.

Fig. 5 .

 5 Fig. 5. 3D plot of the attitude error in the different combinations (a) Roll error, (b) Pitch error.

Figure

  Figure Roll (ρ) Pitch (ψ) 5.(a) ρ = -5.5 • ψ = -3 • 5.(b) ρ = 2.3 • ψ = 3.5 • 5.(c) ρ = -3 • ψ = -9 • 5.(d) ρ = -2.9 • ψ = 5.2 • 5.(e) ρ = 0 • ψ = -4 • 5.(f) ρ = -4.2 • ψ = -1.6 •

TABLE I ROLL

 I AND PITCH ANGLES OFFIGURE 5

ACKNOWLEDGMENT

This work is supported by Agence Nationale de la Recherche -projet CAVIAR (ANR-05-BLAN-0291-01).

constant visibility of the horizon in the image and a real computation of the roll and pitch angles. The method for the attitude computation is divided in two main steps. First, we are looking for the horizon line in the catadioptric image plane. This detection is performed thanks to a markovian approach. However, because of the distortions in the omnidirectional image, a classic neighborhood can not be directly employed. We then propose a new neighboring system adapted to the geometry of the sensor in order to segment the image in two regions (sky/earth). Once the horizon line is detected, the second step consists in projecting this line onto the equivalent sphere in order to estimate the attitude angles. Thanks to the geometric properties of the equivalent sphere, the computation of the pitch and roll angles consists in finding a 3-space plane which intersects the sphere. For this, we use a robust estimator in order to discard the potential outliers detected during the horizon line extraction. Experimental results demonstrate the robustness of the horizon line detection and attitude estimation of the sensor (and consequently of the UAV). Synthetic results allow to verify the accuracy of the angle estimation with an error which is less than one degree for angles in the interval [-60