Alexandre Skoda
email: alexandre.skoda@univ-paris1.fr

Complexity of inheritance of F-convexity for restricted games induced by minimum partitions

Keywords: communication networks, cooperative game, convex game, restricted game, partitions, supermodularity, graph, complexity AMS Classification: 91A12, 91A43, 90C27, 05C75, 68Q25

Let G = (N, E, w) be a weighted communication graph (with weight function w on E). For every subset A ⊆ N , we delete in the subset E(A) of edges with ends in A, all edges of minimum weight in E(A). Then the connected components of the corresponding induced subgraph constitute a partition of A that we call P min (A). For every game (N, v), we define the P min -restricted game (N, v) by v(A) = F ∈Pmin(A) v(F ) for all A ⊆ N . We prove that we can decide in polynomial time if there is inheritance of F-convexity from (N, v) to the P min -restricted game (N, v) where F-convexity is obtained by restricting convexity to connected subsets.

Introduction

We consider, on a given finite set N with |N | = n, a weighted communication structure, i.e., a weighted gragh G = (N, E, w) where w is a weight function defined on the set E of edges of G. For a given subset A of N , we denote by E(A) the set of edges in E with both endvertices in A, and by Σ(A) the subset of edges of minimum weight in E(A). Let G A be the graph induced by A, i.e., G A = (A, E(A)). Then GA = (A, E(A) \ Σ(A)) is the graph obtained by deleting the minimum weight edges in G A . In [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] we introduced the correspondence P min on N which associates to every subset A ⊆ N , the partition P min (A) of A into the connected components of GA . Then for every game (N, v) we defined the restricted game (N, v) associated with P min by:

(1)

v(A) = F ∈P min (A)
v(F ), for all A ⊆ N.

We more simply refer to this game as the P min -restricted game. v is the characteristic function of the game, v : 2 N → IR, A → v(A) and satisfies v(∅) = 0. Compared to the initial game (N, v), the restricted game (N, v) takes into account the combinatorial structure of the graph and the ability of players to cooperate in a given coalition and therefore differents aspects of cooperation restrictions. In particular, assuming that the edge weights reflect the degrees of relationships between players, P min (A) gives a partition of a coalition A into subgroups where players are in privileged relationships (with respect to the minimum relationship degree in A). Many other correspondences have been considered to define restricted games (see, e.g., [START_REF] Myerson | Graphs and cooperation in games[END_REF]; [START_REF] Algaba | A unified approach to restricted games[END_REF]; [START_REF] Bilbao | Cooperative games on combinatorial structures[END_REF][START_REF] Bilbao | Cooperative games under augmenting systems[END_REF]; [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]; [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF]; [START_REF] Grabisch | The core of games on ordered structures and graphs[END_REF]). For a given correspondence a classical problem is to study the inheritance of basic properties as superadditivity and convexity from the underlying game to the restricted game. Inheritance of convexity is of particular interest as it implies that good properties are inherited, for instance the non-emptyness of the core, and that the Shapley value is in the core. For the P min correspondence we proved in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF]) that we always have inheritance of superadditivity from (N, v) to (N, v). Let us observe that inheritance of convexity is a strong property. Hence it would be useful to consider weaker properties than convexity. Following alternative definitions of convexity in combinatorial optimization and game theory when restricted families of subsets are considered (not necessarily closed under union and intersection), see, e.g., [START_REF] Edmonds | A min-max relation for submodular functions on graphs[END_REF][START_REF] Faigle | Cores of games with restricted cooperation[END_REF][START_REF] Fujishige | Submodular Functions and Optimization[END_REF] we introduced in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF] the F-convexity by restricting convexity to the family F of connected subsets of G. In [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF], we have characterized inheritance of F-convexity for P min by five necessary and sufficient conditions on the edge-weights. Of course the study of inheritance of F-convexity is also a first key step to characterize inheritance of convexity in the general case.

We have also highlighted in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] a relation between Myerson's restricted game introduced in [START_REF] Myerson | Graphs and cooperation in games[END_REF] and the P min -restricted game.

Myerson's restricted game (N, v M ) is defined by v M (A) = F ∈P M (A) v(F ) for all A ⊆ N , where P M (A) is the set of connected components of G A .

We proved that inheritance of convexity for the Myerson's game is equivalent to inheritance of F-convexity for the P min -restricted game associated with a weighted graph with only two different weights. In the present paper we prove that inheritance of F-convexity can be checked in polynomial time for P min . Of course, directly testing inheritance of convexity (resp. F-convexity) for the P min -correspondence is highly non polynomial. We have to consider all convex games (N, v) and for each of them, we have to compute the P min -restricted game (N, v) and to verify the convexity (resp. F-convexity) of (N, v), i.e., for all subsets A, B ∈ 2 N (resp. for all subsets A, B such that A, B, and A ∩ B are connected), to verify that v(A ∪ B) + v(A ∩ B) ≥ v(A) + v(B). The characterization given in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] implies that we can verify inheritance of F-convexity by checking that some specific distributions of edge-weights are satisfied on all stars, paths, cycles, pans1 , and adjacent cycles of the graph G. Of course directly checking all these conditions would also lead to a non-polynomial algorithm as the number of paths and cycles can be exponential. We prove that we only have to take into account a polynomial number of specific paths and cycles and therefore we can decide in O(n 6 ) time whether there is inheritance of F-convexity. Moreover, to establish this result we have to more deeply analyze the relations between the star, path, cycle, pan and adjacent cycles conditions characterizing inheritance of the F-convexity. It is of independent interest as we prove that some of them are not completely independent of the others and we highlight their relations which for the sake of simplicity were only implicitely contained in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF]. In particular we observe that the cycle condition in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] splits into an intermediary cycle condition which is a consequence of the star and path conditions and a condition on chords of the cycles. Also a part of the pan condition is a consequence of star and path conditions. We prove that the cycle condition is a consequence of the star, path and adjacent cycles conditions. Hence inheritance of Fconvexity can be characterized by only four of the previous conditions: the star, path, pan, and adjacent cycles conditions.

Star condition can easily be checked in polynomial time. Checking the other conditions in polynomial time requires a deeper and careful analysis. In a first fundamental step, we prove that to verify path condition in polynomial time we only have to consider one minimum weight spanning tree T in G and to verify path condition for the paths joining the end vertices of T and to test intermediary cycle condition for the fundamental cycles of T . Then the main step, which is also the most difficult one, deals with the adjacent cycles condition which a priori involves any pair of adjacent cycles (C, C ′ ). A first contradiction to the adjacent cycle condition is the existence of two cycles C anc C

′ with two common adjacent edges e 1 and e 2 of non maximum weight. We prove that if there exist two such cycles then there also exist two specific cycles C and C′ with two common edges of non maximum weight which are associated with shortest paths in some particular subgraphs depending only on the pair (e 1 , e 2 ). As a result of their features such cycles C and C′ can be detected in polynomial time. A similar result holds for the second possible contradiction to the adjacent cycle condition which corresponds to the existence of two adjacent cycles C and C ′ with only one common non maximum weight edge e 1 . Hence, looking for C and C′ for any pair of adjacent edges (resp. for any edge) in G, we can detect any contradiction to the adjacent cycles condition. Therefore the adjacent cycles condition can be checked in polynomial time. Assuming that the star, path and adjacent cycles condition are satisfied, the cycle condition is necessarily satisfied. Finally using the cycle condition we establish a new condition equivalent to the pan condition that we can easily verify in polynomial time using an appropriate shortest path.

The article is organized as follows. In Section 2, we give preliminary definitions and results. In particular, we recall the definitions of convexity and F-convexity. In section 3, we recall necessary and sufficient conditions on graph edge-weights to have inheritance of F-convexity for the correspondence P min established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF]. Then section 4 is the main part of this article where we establish that inheritance of F-convexity for the P min -correspondence can be checked in polynomial time.

Preliminary definitions and results

Let N be a given set. We denote by 2 N the set of all subsets of

N . A game (N, v) is zero-normalized if v(i) = 0 for all i ∈ N . A game (N, v) is superadditive if, for all A, B ∈ 2 N such that A ∩ B = ∅, v(A ∪ B) ≥ v(A) + v(B).
For any given subset ∅ = S ⊆ N , the unanimity game (N, u S ) is defined by:

(2)

u S (A) = 1 if A ⊇ S, 0 otherwise.
We note that u S is superadditive for all S = ∅.

Let us consider a game (N, v). For arbitrary subsets A and B of N , we define the value:

∆v(A, B) := v(A ∪ B) + v(A ∩ B) -v(A) -v(B). A game (N, v) is convex if its characteristic function v is supermodular, i.e., ∆v(A, B) ≥ 0 for all A, B ∈ 2 N . We note that u S is supermodular for all S = ∅. Let F be a weakly union-closed family 2 of subsets of N such that ∅ / ∈ F. A game v on 2 N is said to be F-convex if ∆v(A, B) ≥ 0, for all A, B ∈ F such that A ∩ B ∈ F. If F = 2 N \ {∅} then F-convexity corresponds to convexity.
For a given graph G = (N, E), we say that a subset A ⊆ N is connected if the induced graph G A = (A, E(A)) is connected. In this paper F will be the family of connected subsets of N .

We recall the following theorems established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF].

Theorem 1. Let G = (N, E, w) be an arbitrary weighted graph, and P an arbitrary correspondence on N . The following claims are equivalent:

1) For all ∅ = S ⊆ N , u S is superadditive.

2) For all subsets A ⊆ B ⊆ N , P(A) is a refinement of the restriction of P(B) to A.

3) For all superadditive game (N, v) the P-restricted game (N, v) is superadditive.

Theorem 2. Let G = (N, E, w) be an arbitrary weighted graph, and P an arbitrary correspondence on N . If for each non-empty subset S ⊆ N , u S is superadditive, then the following claims are equivalent.

1) For all non-empty subset S ⊆ N , the game (N, u S ) is F-convex.

2) For all i ∈ N and for all A, B ∈ F, A ⊆ B ⊆ N \ {i} such that A ∪ {i} ∈ F, we have for all A ′ ∈ P(A ∪ {i}), P(A)

|A ′ = P(B) |A ′ .
Let G = (N, E, w) be a weighted graph. We set |N | = n and |E| = m. We assume that all weights are strictly positive and denote by w k or w ij the weight of an edge e k = {i, j} in E. The adjacency matrix A of G is an n × n matrix defined by:

a ij = w ij if {i, j} ∈ E, 0 otherwise.
In the next section we recall necessary and sufficient conditions on the weight vector w established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] for the inheritance of Fconvexity from the original communication game (N, v) to the P min -restricted game (N, v).

Necessary conditions on edge-weights

A star S k corresponds to a tree with one internal vertex and k leaves. We consider a star S 3 with vertices 1, 2, 3, 4 and edges e 1 = {1, 2}, e 2 = {1, 3} and e 3 = {1, 4}.

Star Condition. For every star of type S 3 of G, the edge-weights w 1 , w 2 , w 3 satisfy, after renumbering the edges if necessary:

w 1 ≤ w 2 = w 3 .
Proposition 3. Let G = (N, E, w) be a weighted graph. If for every unanimity game (N, u S ), the P min -restricted game (N, u S ) is F-convex, then the Star Condition is satisfied.

Path Condition. For every elementary path γ = (1, e 1 , 2, e 2 , 3, . . . , m, e m , m + 1) in G and for all i, j, k such that 1 ≤ i < j < k ≤ m, the edge-weights satisfy:

w j ≤ max(w i , w k ).

Proposition 4. Let G = (N, E, w) be a weighted graph. If for every unanimity game (N, u S ), the P min -restricted game (N, u S ) is F-convex, then the Path Condition is satisfied.

For a given cycle in G, C = {1, e 1 , 2, e 2 , . . . , m, e m , 1} with m ≥ 3, we denote by E(C) the set of edges {e 1 , e 2 , . . . , e m } of C and by Ê(C) the set composed of E(C) and of the chords of C in G.

Weak Cycle Condition.

For every simple cycle of G, C = {1, e 1 , 2, e 2 , . . . , m, e m , 1} with m ≥ 3, the edge-weights satisfy, after renumbering the edges if necessary:

(3)

w 1 ≤ w 2 ≤ w 3 = • • • = w m = M
where M = max e∈E(C) w(e).

Intermediary Cycle Condition.

1) Weak Cycle condition.

2) Moreover w(e) ≤ w 2 for all chord incident to 2, and w(e) ≤ M = max e∈ Ê(C) for all chord non incident to 2. Moreover:

• If w 1 ≤ w 2 < M then w(e) = M
for all e ∈ Ê(C) non-incident to 2. If e is a chord incident to 2 then w 1 ≤ w 2 = w(e) < M or w(e) < w 1 = w 2 < M .

• If w 1 < w 2 = M , then w(e) = M for all e ∈ Ê(C) \ {e 1 }.

Cycle Condition.

1) Weak Cycle condition.

2) Moreover w(e) = w 2 for all chord incident to 2, and w(e) = M for all e ∈ Ê(C) non incident to 2.

Proposition 5. Let G = (N, E, w) be a weighted graph.

1. If G satisfies the Path condition then the Weak Cycle condition is satisfied.

2. If G satisfies the Star and Path conditions then the Intermediary Cycle condition is satisfied.

3. If for every unanimity game (N, u S ), the P min -restricted game (N, u S ) is F-convex, then the Cycle Condition is satisfied.

Weak Pan Condition. For all connected subgraphs corresponding to the union of a simple cycle C = {e 1 , e 2 , . . . , e m } with m ≥ 3, and an elementary path P such that there is an edge e in P with w(e) ≤ min 1≤k≤m w k and |V (C) ∩ V (P )| = 1, the edge-weights satisfy:

(a) either

w 1 = w 2 = w 3 = • • • = w m = M , (b) or w 1 = w 2 < w 3 = • • • = w m = M ,
where M = max e∈ Ê(C) w(e). In this last case V (C) ∩ V (P ) = {2}.

Pan Condition.

1) Weak Pan condition.

2) If Claim (b) of the Weak Pan condition is satisfied and if moreover w(e) < w 1 then {1, 3} is a maximum weight chord of C.

Proposition 6. Let G = (N, E, w) be a weighted graph.

1) If G satisfies the Star, and Path conditions then the Weak Pan condition is satisfied.

2) If for every unanimity game (N, u S ), the P min -restricted game (N, u S ) is F-convex, then the Pan Condition is satisfied.

We recall the proof of Proposition 6 as we will need it to prove a new formulation of the Pan condition in Section 4.

Proof. 1) Let us consider C = {1, e 1 , 2, e 2 , 3, . . . , m, e m , 1}, and P = {j, e m+1 , m + 1, e m+2 , m + 2, . . . , e m+r , m + r} with j ∈ {1, . . . , m}, as represented in Figure 1. We can assume w.l.o.g. that e = e m+r (restricting P if necessary) and that w m+j > w m+r = w(e) for all 1 ≤ j ≤ r -1. Applying Claim 2 (4)

w 1 ≤ w 2 ≤ w 3 = • • • = w m = M .
Let us first assume 3 ≤ j ≤ m. Applying Proposition 4 to the path {2, e 1 , 1, e m , m, . . . , j + 1, e j , j, e m+1 , m + 1, . . . , m + r -1, e m+r , m + r}, we have w j ≤ max(w 1 , w(e)) = w 1 . Then ( 4) implies (a).

Let us now assume j ∈ {1, 2}. If r = 1 then w m+1 = w(e) ≤ w 1 . Otherwise, applying Proposition 4 to the path {e 1 , e m+1 . . . , e m+r }, we have w m+1 ≤ max(w 1 , w(e)) = w 1 . If j = 1, Proposition 3 applied to the star defined by {e 1 , e m , e m+1 }, implies w m+1 ≤ w 1 = w m . Hence (4) still implies (a). If j = 2, Proposition 3 applied to the star defined by {e 1 , e 2 , e m+1 }, implies ′ ) of adjacent simple cycles in G, we have:

w m+1 ≤ w 1 = w 2 . If w 1 = w 2 = M then (a) is satisfied. Otherwise we have w 1 = w 2 < M
w m+r < w 1 = w 2 < w 3 = • • • = w m = M . {{2}, {3, 4, . . . , i -1}, {i + 1, . . . , m, 1}}, P min (A ∪ {i}) = {A ∪ {i} \ {2},
(5) M = max e∈ Ê(C) w(e) = max e∈E(C) w(e) = max e∈E(C ′ ) w(e) = max e∈ Ê(C ′ )
w(e) = M ′ .

Proof. We first consider M = max e∈E(C) w(e) and M ′ = max e∈E(C ′ ) w(e).

Let us consider two adjacent cycles C and C ′ with M < M ′ . There is at least one edge e 1 common to C and C

′ . Then we have

w 1 ≤ M < M ′
and therefore e 1 is a non-maximum weight edge in C ′ . By Claim 1 of Proposition 5 the Weak Cycle condition is satisfied. It implies that there are at most two non-maximum weight edges in C ′ . Therefore there exists an edge e ′ 2 in C

′ adjacent to e 1 with w

′ 2 = M ′ . As M ′ > M , e ′ 2 is
have M = M = M ′ = M ′ . Adjacent Cycles Condition. For all pairs (C, C ′ ) of adjacent simple cycles in G such that: (a) V (C) \ V (C ′ ) = ∅ and V (C ′ ) \ V (C) = ∅, (
• w 1 = w 2 = w ′ 2 if |E(C)| ≥ 4 and |E(C ′ )| ≥ 4. • w 1 = w 2 ≥ w ′ 2 or w 1 = w ′ 2 ≥ w 2 if |E(C)| = 3 or |E(C ′ )| = 3. Proposition 8. Let G = (N, E, w) be a weighted graph. If for every una- nimity game (N, u S ) the P min -restricted game (N, u S ) is F-convex, then the Adjacent Cycles Condition is satisfied.
Finally the following characterization of inheritance of F-convexity was established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF].

Theorem 9. Let G = (N, E, w) be a weighted graph. For every superadditive and F-convex game (N, v), the P min -restricted game (N, v) is F-convex if and only if the Path, Star, Cycle, Pan, and Adjacent cycles conditions are satisfied.

Complexity of inheritance of F-convexity with P min

We now prove that to verify Star, Path, Cycle, Pan, and Adjacent Cycles conditions we only have to consider a polynomial number of paths, stars, pans and cycles. Therefore we can build a polynomial algorithm to decide for a given weighted graph if there is inheritance of F-convexity from underlying games to P min -restricted games. We assume that graphs are represented by their adjacency matrices. We now assume that the Star condition is satisfied by G.

Adding an edge to a spanning tree creates a unique cycle, called a fundamental cycle. Let T be a minimum weight spanning tree of G and γ = {1, e 1 , 2, e 2 , . . . , m, e m , m+1} be an elementary path of G. Let e j 1 , e j 2 , . . . , e j k , with 1 ≤ j 1 < j 2 < . . . < j k ≤ m, be the edges in E(γ) \ E(T ). For every e j l ∈ E(γ) \ E(T ), we denote by C l the fundamental cycle in G associated with T and e j l .

Remark 1. Of course two fundamental cycles associated with a spanning tree can be adjacent.

We suppose that G satisfies the Star condition and that every fundamental cycle associated with T satisfies the Weak Cycle condition. (Note that we only have to check for each fundamental cycle that there are at most two edges of non-maximum weight and that these edges are adjacent. And there are exactly mn + 1 fundamental cycles associated with T . ) For each fundamental cycle C l , we denote by M l its maximum edge weight. As T is a minimum weight spanning tree we have w j l = M l ≥ w(e) for all e ∈ E(C l ). Let γ l be the restriction of γ to C l and v l , v Note that γ ′ l contains at least one edge otherwise v l = v ′ l and γ is not an elementary path. We denote by γ l,l+1 the part of γ linking v

′ l to v l+1 . γ l,l+1 can be reduced to one vertex (if v ′ l = v l+1 ). We denote by γ 0,1 (resp. γ k,m+1 ) the part of γ linking 1 to v 1 (resp. v ′ k to m + 1). γ 0,1 (resp. γ k,m+1 ) can also be reduced to one vertex. Then γ = γ 0,1 ∪ γ ′ 1 ∪ γ 1,2 ∪ γ ′ 2 ∪ • • • ∪ γ k-1,k ∪ γ ′ k ∪ γ k,m+1 corresponds to a path in T linking 1 to m + 1. Let us observe that if two successive fundamental cycles C l , C l+1 are adjacent then γ l ′ ∪ γ l,l+1 ∪ γ ′ l+1
is not a simple path (γ l,l+1 is reduced to one vertex but γ ′ l and γ ′ l+1 have common edges). In this case we delete the common edges to get a simple path (in fact we get a unique elementary path in T ) as represented in Figures 4 and5. Keeping the same notations for simplicity, we now consider that γ is an elementary path in T linking 1 to m + 1. ′ is adjacent to e 1 as represented in Figure 15. Then as w(ẽ 2 ) < w(e ′ ), Star condition applied to {e ′ , e 1 , ẽ2 } implies w(e ′ ) = w 1 . Note that the situation is similar to Case 1 with l < k replacing ẽ1 by ẽ2 . Proof. Let γ = {1, e 1 , 2, e 2 , . . . , m, e m , m + 1} be a path of G. We have to prove that for every j, 2 ≤ j ≤ m -1, we have w j ≤ max(w 1 , w m ).

v ′ l v l v ′ l+1 e j l e j l+1 =v l+1 γ ′ l γ ′ l+1 C l+1 C l Figure 4: We replace γ l ′ ∪ γ l,l+1 ∪ γ ′ l+1 by (γ l ′ ∪ γ ′ l+1 ) \ (γ ′ l ∩ γ ′ l+1 ). v ′ l v l v ′ l+1 e j l e j l+1 =v l+1 γ ′ l γ ′ l+1 C l+1 C l
l v k v ′ k e j k em ẽ1 e ′ =m+1 γ k γ ′ k C k Figure 6: ẽ1 in γ ′ k . v l v k v ′ k e j k em ê e ′ ẽ1 =m+1 γ k γ ′ k γ ′ l C k C l
Let us consider e ∈ E(γ) \ E(T ) and C the fundamental cycle associated with T and e. Let M be the maximum edge weight in C. We necessarily have w(e) = M otherwise T is not a minimum weight spanning tree. We have to prove:

(6) M ≤ max(w 1 , w m ).

Let γ be the path in T related to γ linking 1 to m + 1 defined page 11. Lemma 12 implies that either M = w 1 or w m and then ( 6) is obviously satisfied or there exists ẽ ∈ E(γ) such that w(ẽ) = M . Let e ′ 1 (resp. e ′ m ) be the edge of γ incident to 1 (resp. m+1). Path condition applied to γ implies w(ẽ) ≤ max(w ′ 1 , w ′ m ). If e 1 (resp. e m ) is not an edge of T , then it forms a fundamental cycle containing e ′ 1 (resp. e ′ m ) as represented in Figure 16 and as T is a minimum weight spanning tree we have w

′ 1 ≤ w 1 (resp. w ′ m ≤ w m ). If e 1 (resp. e m ) is an edge of T , then Path condition applied to e 1 ∪ γ (resp. e m ∪ γ) implies w(ẽ) ≤ max(w 1 , w ′ m ) (resp. w(ẽ) ≤ max(w ′ 1 , w m )).
If both e 1 and e m are edges of T , then Path condition applied to e 1 ∪ γ ∪ e m implies w(ẽ) ≤ max(w 1 , w m ). Hence in every case, w(ẽ) ≤ max(w 1 , w m ) and therefore ( 6) is satisfied. As M is the maximum edge-weight in C, we get w(e) ≤ max(w 1 , w m ) for all e ∈ E(C). Therefore we also have w(e) ≤ max(w 1 , w m ) for all e in a fundamental cycle associated with T . Let e be a remaining edge in E(γ) ∩ E(T ). e is necessarily in γ (more precisely in one of the subpaths γ 0,1 , γ 1,2 , . . . , γ k,m+1 ) and therefore satisfies w(e) ≤ max(w 1 , w m ). Let us now analyze the complexity. Prim's algorithm provides a minimum weight spanning tree in time O(n 2 ). Then we verify Path condition for T . For each vertex v ∈ V , we build the arborescence in T rooted in v. It can be done using a breadth first search in O(n 2 ). During the search we can verify the Path condition. Indeed we only have to compare the weight of an edge added to the arborescence to the weight of its predecessor in the arborescence. If there is an increase of edge-weights followed by a decrease then it contradicts the Path condition (We can assign a label {+, -} to each vertex entering the arborescence, and therefore associated with the entering edge, corresponding to an increase or decrease, and we compare it to the label of the preceding node). Hence we can verify the Path condition on T in O(n 3 ) time.

For a given fundamental cycle associated with T , the Cycle condition can be verified in O(n) time. Indeed, as T contains at most n -1 edges, a fundamental cycle contains at most n edges. Then an edge of minimum weight can be found after at most n -1 comparisons. An edge of minimum weight among the n -1 remaining edges can be found using at most n -2 comparisons. Actually we only have to consider the two edges adjacent to the minimum weight edge previously found. Finally we only have to verify the equality of edge-weights for the remaining edges. It requires at most n -3 comparisons. There exists m -(n -1) edges in E \ E(T ) and therefore m -(n -1) fundamental cycles associated with T . Hence we can verify the Cycle condition for all fundamental cycles associated with T in O(nm).

Finally Path condition for G can be verified in O(n 2 + n 3 + nm) time and therefore in O(n 3 ) time (as m ≤ n(n-1)

2

).

We now prove that the Adjacent cycles condition can be verified in O(n 6 ) time. We first establish that we only need to verify the condition on specific cycles built with shortest paths.

= Ĉ. If V ( C) \ V (C ′ ) = ∅ we select a node i in V ( C) \ V (C ′ ). Otherwise we have V ( C) ⊆ V (C ′ ). V ( C) ⊂ V (C ′ ) would imply that C ′ has a chord of maximum weight M , a contradiction. Hence V ( C) = V (C ′ ) and in this case we have V ( C) \ V (C) = V (C ′ ) \ V (C) = ∅. Then we select a node i in V ( C) \ V (C) (we can interchange C and C ′ )
. By construction of i there exists a path in GN\{2,i} linking 1 to 3 (i.e., a path in C ′ or C). Therefore there exists a shortest path γ ′ in GN\{2,i} linking 1 to 3. Then the cycle C′ andγ ′ is a path strictly shorter than γ linking 1 to 3 in G, a contradiction. C and C′ have no maximum weight chord because γ and γ ′ are shortest path linking 1 and 3 in respectively G and GN\{2,i} . C has no chord. C and C′ satisfy conditions a to d, 2f and 2g.

= {2, e 1 , 1} ∪ γ ′ ∪ {3, e 2 , 2} is convenient. We have V ( C) \ V ( C′ ) = ∅ as i ∈ V ( C) \ V ( C′ ). If V ( C′ ) \ V ( C) = ∅ then V ( C′ ) ⊆ V ( C). V ( C′ ) = V ( C) is not possible as i ∈ V ( C) \ V ( C′ ). Then V ( C′ ) ⊂ V ( C)
If e 1 and e 2 are given, we can obtain a shortest path γ, if it exists, using a Breadth First Search algorithm in O(n 2 ) time. Then to decide if Ĉ has a chord or not, take O(n) time. Indeed Ĉ cannot have a maximum weight chord otherwise γ is not a shortest path, and any non maximum weight chord is incident to 2. Therefore we only have to check in G if there exists a neighbor of 2 in γ \ {1, 3}. In the worst case, we have to consider n -3 vertices. For a given node i ∈ γ \ {1, 3} checking the existence of {2, i} in the adjacency matrix is in O( 1) time. Therefore we can check the existence of a chord in O(n) time. If Ĉ is chordless then for a given i ∈ V (γ) we look for a shortest path γ ′ in GN\{2,i} linking 1 and 3 using the BFS algorithm in O(n 2 ) time. In the worst case we repeat this for all i ∈ V (γ). Hence in this case ( Ĉ without chord) we need O(n 3 ) time to decide if Claim 2 is satisfied. Case 2 Let us now assume that Ĉ has a chord ê. Then it is necessarily a non-maximum weight chord incident to 2 with w(ê) ≤ w 2 (by the Intermediary Cycle condition). We choose arbitrarily the end-vertex i of any chord ê0 = {2, i} of Ĉ. We select two other edges in Ê( Ĉ), ê1 = {2, k} and ê2 = {2, j}, with 3 ≤ j < i < k, which are as close as possible from ê0 , i.e., j is the maximum possible index for such an edge ê2 and k is the minimum possible index for such an edge ê1 . Hence if j = 3 (resp. k = 1) then ê2 = e 2 (resp. ê1 = e 1 ). We consider the cycle C = {k, ê1 , 2, ê2 , j, e j , j + 1, . . . , e i-1 , i, e i , . . . , e k-1 , k} as represented in Figure 18. By renumbering as follows, 1 = k, ẽ1 = ê1 , 2 = 2, ′ . We can assume w.l.o.g. that ẽ0 = {2, ĩ} is not a chord of C ′ . Let γ 1 (resp. γ 2 ) be the part of γ linking 1 and k (resp. 3 and j), γ 1 = {k, e k , k + 1, . . . , p, e p , 1} (resp. γ 2 = {3, e 3 , 4, . . . , j -1, e j-1 , j}) then γ 1 ∪ (C ′ \ {2}) ∪ γ 2 corresponds to a path linking k to j and therefore 1 to 3 in G \ {2, ĩ} as represented in Figure 19. Therefore there exists a shortest path γ ′ in G \ {2, ĩ} linking 1 to

3 3 2 ĩ 1 1 ẽ2 ẽ0 ẽ1 e 1 e 2 C ′ Figure 19: Path { 1, 1} ∪ (C ′ \ {2}) ∪ {3, 3}.
3. Then we can consider the cycles C and C′ = {2, ẽ1 , 1} ∪ γ ′ ∪ { 3, ẽ2 , 2} as represented in Figure 20. We can achieve the proof as in the first case. By construction C has only one non-maximum weight chord ẽ0 = {2, ĩ} which is not a chord of C′ ( ĩ / ∈ C′ ) and C and C′ have no maximum weight chords. C and C′ satisfy conditions a to d, 2f and 2g (replacing e 1 (resp. e 2 ) by ẽ1 (resp. ẽ2 )).

As in Case 1, we can obtain Ĉ, if it exists, using a Breadth First Search algorithm in O(n 2 ) time. Then to find a chord ẽ0 = {2, ĩ} of Ĉ, we need at most O(n) time. To select the edges ẽ1 = {2, k} and ẽ2 = {2, j}, we also need at most O(n) comparisons. To build the shortest path γ ′ in G \ {2, ĩ} using a Breadth First Search algorithm, we need O(n 2 ) time. Hence to verify Claim 2 when Ĉ has a chord, we need O(n 2 ) time. Note that if there exists a chord in C we do not need to check Claim 2g for all i ∈ V (γ) \ { 1, 3}. We check the condition only for the node i corresponding to the chord we have found.

We consider that the Adjacent cycles condition can be divided in two parts. The first part is the condition of non-existence of cycles with two common non-maximum weight edges. Then the second part is the condition on edge-weights for cycles with a unique common non-maximum weight edge.

Proposition 15. The first part of the Adjacent cycles condition can be verified in O(n 6 ) time.

Proof. We have to verify that for any pair of adjacent edges e 1 = {1, 2} and e 2 = {2, 3}, e 1 and e 2 are not common non-maximum weight edges of two adjacent cycles (i.e., Claim 1 of Lemma 14 is not satisfied). By Lemma 14 it is sufficient to prove that Claim 2 of Lemma 14 is not satisfied and it can be done in O(n 3 ) time. There are at most i∈V C 2 n = n 2 n-1 2 pairs of adjacent edges. Hence we need at most n 3 iterations of the procedure considered in Lemma 14 and therefore the first part of the Adjacent cycles condition can be verified in O(n 6 ) time. (g) C\{ẽ 1 } corresponds to a shortest path γ in G = (V, E\{ẽ 1 }, w |E\{ẽ 1 } ) linking 1 and 2 and for some i ∈ V (γ) \ {1, 2}, C′ \ {ẽ 1 } corresponds to a shortest path γ′ in GN\{i} linking 1 and 2. Let us observe that using the Intermediary Cycle condition we only need to verify that the edges in E(C) adjacent to e 1 have a weight strictly greater than w 1 . Indeed if it is satisfied then w(e) > w 1 for all e ∈ E(C) \ {e 1 }.

Remark 4. Let us note that by the Intermediary Cycle condition C, C

′ , C, C′ can have at most two non-maximum weight edges. If they all have two nonmaximum weight edges then e 1 and all these edges are adjacent (incident to 1 or 2).

Proof. Let us consider C = {1, e 1 , 2, e 2 , . . . , m, e m , 1}. Then γ = C \ {e 1 } = {2, e 2 , . . . , m, e m , 1} is a path linking 1 and 2 in G. Hence there is a shortest path γ = {2, ẽ2 , 3, ẽ3 , . . . , p, ẽp , 1} linking 1 and 2 in G. Then we can build the cycle C := {1, e 1 , 2, ẽ2 , 3, ẽ3 , . . . , p, ẽp , 1} adding the edge e 1 to the path γ. Either C = C, or C and C are adjacent. In this last case Lemma 7 implies max e∈E(C) w(e) = max e∈E( C) w(e). Hence e 1 is a non-maximum weight edge in C. Claim 1e implies w 2 > w 1 (resp. w m > w 1 ). If ẽ2 = e 2 (resp ẽp = e m ) then w(ẽ 2 ) = w 2 (resp. w(ẽ p ) = w m ). Otherwise Star condition applied to {e 1 , e 2 , ẽ2 } (resp. e 1 , e m , ẽp ) implies w(ẽ 2 ) = w 2 (resp. w(ẽ p ) = w m ). Then the Intermediary Cycle condition implies w 1 < w(ẽ 2 ) ≤ w(ẽ 3 ) = . . . = w(ẽ p ) = M with M = max e∈E( C) w(e), exchanging ẽ2 and ẽp if necessary.

The Intermediary Cycle condition also implies that for any chord e in C, we have w(e) ≤ w 2 if e is incident to 2 (in fact, as w 1 < w 2 , the Star condition applied to {e 1 , ẽ2 , e} implies w(e) = w 2 ) and w(e) = M otherwise. In any case e would contradict the optimality of γ. Hence C has no chord.

Let us assume

V ( C) ⊆ V (C) ∩ V (C ′ ). As V (C) \ V (C ′ ) = ∅ (resp. V (C ′ ) \ V (C) = ∅) we have V ( C) = V (C) (resp. V ( C) = V (C ′ )
). Then at least one edge ẽ of C is a chord of C. As C has no maximum weight chord, ẽ is a chord of non-maximum weight in C and then ẽ is also an edge in E( C) \ {e 1 } of non-maximum weight (by Lemma 7, as C and C are adjacent the maximum weight in C and C is M ). Following the Intermediary Cycle condition ẽ is the unique edge of C of non-maximum weight adjacent to e 1 as represented in Figure 22. By the same reasoning (interchanging C and

C

′ ), there exists an edge ẽ′ of C which is a chord of C ′ and ẽ′ is an edge of C of non-maximum weight.

ẽ′ necessarily corresponds to the unique edge of C of non-maximum weight adjacent to e 1 . Therefore ẽ = ẽ′ . Hence C and C

′ have a common chord, a contradiction.

Therefore we have either

V ( C) \ V (C) = ∅ or V ( C) \ V (C ′ ) = ∅.
In every case we can choose i ∈ V ( C) \ {1, 2} such that there exists a path γ in GN\{i} linking 1 and2

. γ = γ if i / ∈ V (C) or γ = C ′ \ {e 1 } = {2, e ′ 2 , 3 ′ , e ′ 3 , . . . , m ′ , e ′ m ′ , 1} if i / ∈ V (C ′ )
i ∈ V ( C) \ V ( C′ ) we have V ( C) \ V ( C′ ) = ∅.
We have already seen that max e∈E(C) w(e) = max e∈E( C) w(e) = max e∈E( C′ ) w(e), and that if C contains a second non-maximum weight edge then C and C′ also contain a second non-maximum weight edge of same weight. Therefore if V ( C′ ) ⊂ V ( C) then γ′ is a path linking 1 and 2 in G shorter that γ, a contradiction. Therefore we have V ( C′ ) \ V ( C) = ∅. C′ such that C \ {e 1 } corresponds to a shortest path γ linking 1 and 2 in G = (N, E \ {e 1 }, w |E\{e 1 } ) and for some i ∈ V (γ) \ {1, 2}, C′ \ {e 1 } corresponds to a shortest path in GN\{i} linking 1 and 2. Moreover we still have w(e) > w 1 for all e ∈ (E( C) ∪ E( C′ )) \ {e 1 }. Therefore for every edge e 1 ∈ E, we only have to verify that such a couple of adjacent cycles ( C, C′ ) cannot exist. Therefore we look for a shortest path γ linking 1 and 2 in G. If it exists then we look for a shortest path γ′ in GN\{i} with i ∈ V (γ) \ {1, 2}, linking 1 and 2. If such a path γ′ exists, we only have to verify that w(e) = w 1 for some edge e of γ or γ′ (in fact the Weak Cycle condition implies that such an edge is necessarily adjacent to e 1 ).

Note that by the Star and Weak Cycle conditions and Lemma 7, all elementary paths linking 1 and 2 in G have either all their edges of same weight M > w 1 or one edge incident to 1 or 2 with weight w 2 > w 1 and their remaining edges with weight M > w 2 . Therefore we can find a shortest path γ linking 1 and 2 in G using a BFS algorithm in O(n 2 ). Then we can also use a BFS algorithm to find a shortest path in GN\{i} with i ∈ γ. In the worst case we have to consider all nodes i ∈ γ. Therefore we can verify in O(n 3 ) time if e 1 satisfies the Weak Second Part of the Adjacent Cycles condition. Therefore the Weak Second Part of the Adjacent cycles condition can be verified in O(n 3 m) time. Therefore if w 1 < w 2 = M the Cycle condition is satisfied. If w 1 ≤ w 2 < M let us assume by contradiction that there exists a chord incident to 2 with w(e) < w 2 . Star condition applied to {e, e 1 , e 2 } implies w 1 = w 2 and that for any other chord e ′ incident to 2 we have w(e ′ ) = w 1 = w 2 . Hence we can assume that C has only one chord e incident to 2 replacing if necessary C by a smaller cycle using the chords of C incident to 2 which are as close as possible to e. We have e = {2, j} with 4 ≤ j ≤ m. We can consider two adjacent cycles C := {2, e, j, e j , . . . , m, e m , 1, e 1 , 2} and C′ := {2, e 2 , 3, e 3 , . . . , e j-1 , j, e, 2} as represented in Figure 24. Finally if w 1 = w 2 = M , let us also assume by contradiction that there exists a chord e in C with w(e) < w 2 = M . As w 1 = w 2 = M we can always assume e incident to 2 after renumbering if necessary and then we can establish the same contradiction as before.

= w 2 ≤ w 3 = • • • = w m = M . If w 1 = w 2 = M then Claim 1 is satisfied. Otherwise we have w 1 = w 2 < M . If {1, 3} is a chord of C then Claim 2 is satisfied. Otherwise {1, 3}
is not a chord of C and let us assume σ(E) < w 1 = w 2 . Then there exists e ∈ E \ E(C) such that w(e) < w 1 = w 2 . Note that the Cycle condition implies that a chord of C incident (resp. non incident) to 2 has weight w 2 (resp. M ). Therefore we actually have e ∈ E \ Ê(C). As G is connected there is a path P containing e (P can be restricted to e) such that |V (C) ∩ V (P )| = 1. Then as w(e) < w 1 = w 2 < M , Pan condition implies that V (C) ∩ V (P ) = {2} and that {1, 3} is a maximum weight chord of C, a contradiction. Therefore Claim 3 is satisfied.

Let us now consider a simple cycle C = {1, e 1 , 2, e 2 , . . . , m, e m , 1}, and an elementary path P such that there is an edge e ∈ P with w(e) ≤ min Theorem 22. Let G = (N, E, w) be an arbitrary weighted graph. Let us consider the correspondance P min . We can verify inheritance of F-convexity from (N, v) to (N, v) for all F-convex and superadditive game (N, v) in O(n 6 ) time.

Conclusion

We think that the method we have presented to prove that inheritance of Fconvexity is a polynomial problem, especially, the use of minimum spanning trees and shortest paths to select specific paths and cycles, can be useful for further developments. In particular it could be used to obtain polynomial algorithms to check inheritance of convexity for P min or of convexity or Fconvexity for other correspondences as for example the correspondence P G presented in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF] which associates to a subset its partition into relatively strongest components. Of course it is not certain that such algorithms do exist.

Figure 1 :

 1 Figure 1: Pan formed by the union of C and P . of Proposition 5 to the cycle C, we have after renumbering the edges if

  Figure 2: w m+r < w 1 = w 2 < w 3 = • • • = w m = M .

  {2}}, and P min (B) = {B \ {m + r}, {m + r}} or P min (B) = {B} (this last case can occur if there exists an edge e ′ in G B with w(e ′ ) < w(e) or with m + r as an end-vertex and w(e ′ ) > w(e)). Therefore A ′ := A∪{i}\{2} ∈ P min (A∪{i}), but P min (B) |A ′ = {A \ {2}} = P min (A) |A ′ and it contradicts Theorem 2. Lemma 7. Let G = (N, E, w) be a weighted graph satisfying the Star and Path conditions. Then for all pairs (C, C

  not an edge of C. Let e 2 be the edge of C adjacent to e 1 and e ′ 2 . Then we have w 2 ≤ M < M ′ but it contradicts the Star condition applied to {e 1 , e 2 , e ′ 2 } (two edge-weights are strictly smaller than w ′ 2 ). Therefore M = M ′ . Finally by Claim 2 of Proposition 5 the Intermediary Cycle condition is satisfied and we

  b) C has at most one non-maximum weight chord, (c) C and C ′ have no maximum weight chord, (d) C and C ′ have no common chord, then C and C ′ cannot have two common non-maximum weight edges. Moreover C and C ′ have a unique common non-maximum weight edge e 1 if and only if there are non-maximum weight edges e 2 ∈ E(C) \ E(C ′ ) and e ′ 2 ∈ E(C ′ ) \ E(C) such that e 1 , e 2 , e ′ 2 are adjacent and:

′lFigure 3 :

 3 Figure 3: Paths γ l and γ ′ l in C l .

Figure 5 :

 5 Figure 5: We can have γ ′ l ⊂ γ ′ l+1 .

Figure 7 :

 7 Figure 7: ẽ1 in γ ′ l with l < k. in C l with 1 ≤ l ≤ k as represented in Figure 6 for l = k and Figure 7 for l < k. Note that if l < k then C l , C l+1 , . . . , C k-1 , C k are adjacent and by Lemma 11 we have M l = M k . If w(ẽ 1 ) = M k we take e = ẽ1 . Otherwise we have w(ẽ 1 ) < M k . Let ê be the edge in E(C l ) \ {ẽ 1 } incident to v ′ k . If l = k then ê = e m and we have w(ê) < M k . Otherwise we apply Star condition to {e m , ê, ẽ1 } and w(ê) < M k is still satisfied. Then the Weak Cycle condition applied to C l implies that there is an edge e ′ in E(C l ) adjacent to ẽ1 with w(e ′ ) = M k . If e ′ belongs to γ we take e = e ′ . Otherwise, if |E(γ)| ≥ 2 there is an edge ẽ2 in γ adjacent to e ′ and ẽ1 as represented in Figure 8. Star condition applied to {e ′ , ẽ1 , ẽ2 } implies w(ẽ 2 ) = M k and we take e = ẽ2 . Finally if |E(γ)| = 1 then v l = v 1 = 1. Hence either e ′ = e 1 and the result is satisfied or e ′ is adjacent to e 1 as represented in Figure 9. Then Star condition applied to {e 1 , e ′ , ẽ1 } implies w(e ′ ) = w 1 . Let us observe that we

Figure 9 :

 9 Figure 8: |E(γ)| ≥ 2.

  Figure 10: ẽ1 in γ k,m+1 . If l < k, we can assume that C l and C l+1 are not adjacent. Otherwise Lemma 11 implies M l = M l+1 and we can replace C l by C l+1 . If v ′ l = v l+1 , ẽ1 is the edge of γ l,l+1 incident to v ′ l as represented in Figure 11.

′

  Figure 11: v ′ l = v l+1 , ẽ1 in γ l,l+1 .

  Figure 13: ê in γ l , ẽ2 in γ ′ l .If w(ẽ 2 ) = M l , we take e = ẽ2 . Otherwise we have w(ẽ 2 ) < M l . If w(ê) = M l , Star condition applied to {ê, ẽ1 , ẽ2 } implies w(ẽ 1 ) = M l and we can take e = ẽ1 . If now w(ê) and w(ẽ 2 ) < M l , then the Weak Cycle condition applied to C l implies that there is an edge e′ in E(C l ) adjacent to ẽ2 with w(e ′ ) = M l . If e ′ belongs to γ we take e = e ′ . Otherwise, if |E(γ 1,l )| ≥ 2 there is an edge ẽ3 in γ adjacent to e ′ and ẽ2 as represented in Figure14. Star condition applied to {e ′ , ẽ2 , ẽ3 } implies w(ẽ 3 ) = M l and we take e = ẽ3 .Finally if |E(γ 1,l )| = 1 then v l = v 1 = 1.Then either e ′ = e 1 and the result is satisfied or e ′ is adjacent to e 1 as represented in Figure15. Then as w(ẽ 2 ) < w(e ′ ), Star condition applied to {e ′ , e 1 , ẽ2 } implies w(e ′ ) = w 1 . Note that the situation is similar to Case 1 with l < k replacing ẽ1 by ẽ2 .

Figure 14 :Figure 15 :

 1415 Figure 14: |E(γ 1,l )| ≥ 2, ẽ3 in γ adjacent to e ′ and ẽ2 .

Figure 16 :

 16 Figure 16: γ and γ, e 1 / ∈ E(T ), e m ∈ E(T ).

Lemma 14 .

 14 Let G = (N, E, w) be a weighted graph satisfying the Star and Path (and therefore Weak and Intermediary Cycle) conditions. Let e 1 = {1, 2} and e 2 = {2, 3} be two adjacent edges of G. Let us define Ẽ := {e ∈ E; w(e) > max(w 1 , w 2 )} and G := (N \ {2}, Ẽ, w | Ẽ ). Let γ be a shortest path in G, if it exists, linking 1 and 3. Let us consider the following claims: 1) There exist two simple cycles C and C ′ in G satisfying conditions a, b, c, d of the Adjacent Cycles condition, and such that: 16 Documents de travail du Centre d'Economie de la Sorbonne -2016.55 (e) e 1 and e 2 are two common non-maximum weight edges of C and C ′ . 2) There exist two simple cycles C and C′ satisfying conditions a, b, c, d of the Adjacent Cycles condition, and such that: (f ) C and C′ have two common non-maximum weight edges ẽ1 = { 1, 2}, ẽ2 = {2, 3}. (g) C \ {2} corresponds to a shortest path γ in G linking 1 and 3. γ is a subpath of γ and for some i ∈ V (γ) \ { 1, 3}, C′ \ {2} corresponds to a shortest path γ ′ in GN\{2,i} linking 1 and 3. Then Claim 1 implies Claim 2. Moreover for given adjacent edges e 1 and e 2 of G, Claim 2 can be verified in O(n 3 ) time. Remark 2. It can happen that γ = γ and then 1 = 1 and 3 = 3. Remark 3. Let us observe that |V (C)| ≥ 4 and |V (C ′ )| ≥ 4, otherwise by the Weak Cycle condition C or C ′ would have a maximum weight chord. Let us also observe that by the Weak Cycle condition and Lemma 7 page 8, all edges of γ and γ ′ have the same weight M .

  Figure 17: i ∈ γ = C \ {2} and i ∈ γ ′ = C′ \ {2}.

  , 3 = j, ẽĩ -1 = e i-1 , ĩ = i, ẽĩ = e i , . . ., ẽm = e k-1 , k = 1 we get C = { 1, ẽ1 , 2, ẽ2 , 3, . . . , ẽĩ -1 , ĩ, ẽĩ , . . . , ẽm , 1}. C has only one non-maximum weight chord ẽ0 = {2, ĩ} corresponding to ê0 = {2, i} and ẽ1 , ẽ2 are the two non-maximum weight edges of C. The restricted path γ = { 3, ẽ3 , . . . , ẽĩ -1 , ĩ, ẽĩ , . . . , ẽm , 1} is a shortest path linking 3 to 1 in G as γ is a shortest path linking 1 to 3 in G. As C and C′ have no common chord, ẽ0 = {2, ĩ} cannot be a common chord of C and C

  Figure 20: Adjacent cycles C and C′ .

  Lemma 16. Let G = (N, E, w) be a weighted graph satisfying the Star and Path (and therefore Intermediary Cycle) conditions. Let us assume that the first part of the Adjacent cycles condition is satisfied. Then the following Claims are equivalent: 1) There exist two simple cycles C and C ′ in G satisfying conditions a, b, c, d of the Adjacent Cycles condition, and such that: (e) C and C ′ have a unique common non-maximum weight edge e 1 = {1, 2} and w(e) > w 1 for all e ∈ (E(C) ∪ E(C ′ )) \ {e 1 }. 2) There exist two simple cycles C and C′ in G satisfying conditions a, b, c, d of the Adjacent Cycles condition, and such that: (f ) C and C′ have a unique common non-maximum weight edge ẽ1 = {1, 2} and w(e) > w 1 for all e ∈ (E( C) ∪ E( C′ )) \ {e 1 }.

  Figure 21: C = {1, ẽ1 , 2, ẽ2 , . . . , p, ẽp , 1} and C′ = {1, ẽ1 , 2, ẽ′ 2 , . . . , p ′ , ẽ′ p ′ , 1}.

  Figure 22: ẽ non-maximum weight chord (resp. edge) in C (resp. C).

  Figure 23: C ′ and C, with i / ∈ C ′ .

Proposition 18 .

 18 Let G = (N, E, w) be a weighted graph satisfying the Star and Path (and therefore Intermediary Cycle) conditions, and the Weak Second Part of the Adjacent Cycles condition. Then the Cycle condition is satisfied. Proof. Let us consider a cycle C = {1, e 1 , 2, e 2 , . . . , m, e m , 1}. The Intermediary Cycle condition implies that w 1 ≤ w 2 ≤ w 3 = • • • = w m = M after renumbering if necessary and that w(e) ≤ w 2 for all chord incident to 2 and w(e) ≤ M for all other chords. Moreover: • If w 1 ≤ w 2 < M then w(e) = M for all e ∈ E(C) non-incident to 2. If e is a chord incident to 2 then w 1 ≤ w 2 = w(e) < M or w(e) < w 1 = w 2 < M . • If w 1 < w 2 = M , then w(e) = M for all e ∈ E(C) \ {e 1 }.

  Figure 24: w(e) < w 1 = w 2 . e is a unique common edge to C and C′ such that w(e) < w 1 = w 2 ≤ M . If C (resp. C′ ) has a chord then we can replace C (resp. C′ ) by a smaller cycle. Therefore we can suppose that C and C′ have no chords. Then w(e) < w 1 = w 2 contradicts the Weak Second Part of the Adjacent Cycles condition. Therefore any edge incident to 2 has weight w 2 .Finally if w 1 = w 2 = M , let us also assume by contradiction that there exists a chord e in C with w(e) < w 2 = M . As w 1 = w 2 = M we can always assume e incident to 2 after renumbering if necessary and then we can establish the same contradiction as before.

  Assuming now that the Star, Path, and Cycle conditions are satisfied we give a new formulation of the Pan condition. Then we will analyze its complexity. Lemma 19. Let G = (N, E, w) be a connected weighted graph satisfying the Star, Path, and Cycle conditions. The Pan condition is satisfied if and only if for all simple cycle C = {1, e 1 , 2, e 2 , . . . , m, e m , 1}, with w 1 = w 2 ≤ w 3 = • • • = w m = M = max e∈ Ê(C) w(e), one of the following claim is satisfied: 1) w 1 = w 2 = M . 2) w 1 = w 2 < M and {1, 3} is a chord of C. 24 Documents de travail du Centre d'Economie de la Sorbonne -2016.55 3) σ(E) = w 1 = w 2 < M , where σ(E) = min e∈E w(e). Proof. Let us first assume that the Pan condition is satisfied. Let us consider a simple cycle C = {1, e 1 , 2, e 2 , . . . , m, e m , 1}, with w 1

  1≤k≤m w k and |V (C) ∩ V (P )| = 1. The Cycle condition implies w 1 ≤ w 2 ≤ w 3 = • • • = w m = M after renumbering if necessary. Moreover the Path and Star conditions imply w 1 = w 2 ≤ M and if w 1 = w 2 < M then V (C) ∩ V (P ) = {2} (as the Weak Pan condition is satisfied by Proposition 6). If C satisfies Claim 1 then the Pan condition is trivially satisfied. If C satisfies Claim 2 then {1, 3} is a chord of C and as w 1 = w 2 < M we have V (C) ∩ V (P ) = {2}. Moreover the (Intermediary) Cycle condition implies that {1, 3} is a maximum weight chord. Therefore the Pan condition is satisfied. Finally if C satisfies Claim 3, we also have V (C) ∩ V (P ) = {2} and as σ(E) = w 1 , we necessarily have w(e) = w 1 . Therefore the Pan condition is still satisfied. Proposition 20. Let G = (N, E, w) be a connected weighted graph satisfying the Star, Path conditions and the Cycle condition (or the Weak Second Part of the Adjacent Cycles condition). Then Pan condition can be verified in O(n 5 ) time. Proof. Let C = {1, e 1 , 2, e 2 , . . . , m, e m , 1} be a simple cycle of G. The Cycle condition implies w 1 ≤ w 2 ≤ w 3 = • • • = w m = M = max e∈E(C) w(e), after renumbering if necessary. Let γ be a shortest path linking 1 and 3 in G N \{2} and let C be the simple cycle formed by e 1 , e 2 and γ. If C = C then Lemma 7 implies that max e∈E( C) = M . Lemma 19 implies that Pan condition for C is equivalent to Pan condition for C. Then if w 1 = w 2 < M either the chord {1, 3} exists (i.e. γ = {1, {1, 3}, 3} and C = {1, e 1 , 2, e 2 , 3, {1, 3}, 1}) otherwise w 1 = w 2 = σ(E). Hence to verify the Pan condition we just need to consider any pair of adjacent edges e 1 = {1, 2} and e 2 = {2, 3} with w 1 = w 2 . Let us consider the graph G = (N, Ẽ, w | Ẽ ) with Ẽ = {e ∈ E; w(e) ≥ w 1 }. Then we look for a shortest path γ linking 1 to 3 in the graph GN\{2} using a BFS algorithm in O(n 2 ) time. If γ exists and if γ has at least two edges, we consider the simple cycle C = {1, e 1 , 2, e 2 , 3} ∪ γ. Note that as γ is a shortest path linking 1 and 3, {1, 3} cannot be a chord of C. Then applying Lemma 19 to C we only need to verify that either w 1 = w 2 = w 3 or w 1 = w 2 = σ(E). σ(E) can be computed in O(m) time. We have at most i∈V C 2 n = n 2 n-1 2 pairs e 1 , e 2 to take into account. Therefore the Pan condition can be verified in O(n 5 ). Proposition 21. Let G = (N, E, w) be a weighted graph satisfying the Weak Second Part of the Adjacent Cycles and the Pan conditions. Then the Second part of the Adjacent Cycles condition is satisfied. Proof. Let e 1 be a unique non-maximum weight edge common to two simple cycles (C, C ′ ) in G satisfying the conditions a, b, c, d of the Adjacent Cycles condition. The Weak Second Part of the Adjacent Cycles condition implies that there are non-maximum weight edges e 2 ∈ E(C)\{e 1 } and e ′ 2 ∈ E(C ′ )\ {e 1 } such that e 1 , e 2 , e ′ 2 are adjacent and w 1 = w 2 ≥ w ′ 2 or w 1 = w ′ 2 ≥ w 2 . If |E(C)| = 3 or |E(C ′ )| = 3 then the second part of the Adjacent Cycles condition is satisfied. If |E(C)| ≥ 4 and |E(C ′ )| ≥ 4, let us assume w 1 = w 2 > w ′ 2 (resp. w 1 = w ′ 2 > w 2 ). By assumption C (resp. C ′ ) have no maximum weight chord therefore the Pan condition applied to C and e ′ 2 (resp. C ′ and e 2 ) implies w 1 = w 2 = max e∈E(C) w(e) (resp. w 1 = w ′ 2 = max e∈E(C ′ ) w(e)), a contradiction. Therefore w 1 = w 2 = w ′ 2 and the second part of the Adjacent Cycles condition is satisfied.

A pan graph is a graph obtained by joining a cycle to a vertex by an edge.

Documents de travail du Centre d'Economie de la Sorbonne -2016.55

F is weakly union-closed if A ∪ B ∈ F for all A, B ∈ F such that A ∩ B = ∅ (Faigleet al., 2010). Weakly union-closed families were introduced and analysed in Algaba (1998);[START_REF] Algaba | The position value for union stable systems[END_REF] and called union stable systems. 4 Documents de travail du Centre d'Economie de la Sorbonne -2016.55

Acknowledgments

The support of the French National Research Agency, through DynaMITE project (Reference: ANR-13-BSH1-0010-01), is gratefully acknowledged.


Hector Garcia De Marina

Yuri A Kapitanyuk

Murat Bronz

Gautier Hattenberger

Ming Cao

Guidance algorithm for smooth trajectory tracking of a fixed wing UAV flying in wind flows

This paper presents an algorithm for solving the problem of tracking smooth curves by a fixed wing unmanned aerial vehicle travelling with a constant airspeed and under a constant wind disturbance. The algorithm is based on the idea of following a guiding vector field which is constructed from the implicit function that describes the desired (possibly timevarying) trajectory. The output of the algorithm can be directly expressed in terms of the bank angle of the UAV in order to achieve coordinated turns. Furthermore, the algorithm can be tuned offline such that physical constrain of the UAV, e.g. the maximum bank angle, will not be violated in a neighborhood of the desired trajectory. We provide the corresponding theoretical convergence analysis and performance results from actual flights.

I. INTRODUCTION

The usage of unmanned aerial vehicles (UAVs) in tasks such as monitoring missions, surveillance or patrolling has found broad applications. In order to accomplish this set of missions successfully, it is very often required to track or follow a predetermined path with high accuracy. For example, one can help the aerial mapping of a geographical area of interest if it is guaranteed that the vehicle will fly over a prescribed trajectory, i.e. if the path-following control problem is solved. There is no unique approach for addressing this problem for fixed wing UAVs as it has been surveyed in [START_REF] Sujit | Unmanned aerial vehicle path following: A survey and analysis of algorithms for fixed-wing unmanned aerial vehicless[END_REF]. For example, most popular open-source UAV autopilots (such as Ardupilot [START_REF]Uav open-source project[END_REF], Pixhawk [START_REF] Pixhawk | [END_REF] and Paparazzi [START_REF] Paparazzi | [END_REF]) use algorithms that are based on one of the following ideas: Tracking a time-varying reference point [START_REF] Micaelli | Trajectory tracking for unicycle-type and two-steering-wheels mobile robots[END_REF], [START_REF] Soetanto | Adaptive, non-singular path-following control of dynamic wheeled robots[END_REF] (also known as carrot-chasing or rabbit-chasing); tracking a vector field [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF], [START_REF] Frew | Lyapunov guidance vector fields for unmanned aircraft applications[END_REF]; or minimizing some error signals involving the Euclidean distance to the desired path and other variables [START_REF] Ratnoo | Adaptive optimal path following for high wind flights[END_REF]. These algorithms have been shown to be reliable and easy to implement in limited hardware resources; however, they have several limitations. Firstly, they are limited by the necessity of measuring the actual distance between the UAV and the given trajectory. In practice, this confines the usage of such algorithms for straight lines and circles mostly [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF], [START_REF] Frew | Lyapunov guidance vector fields for unmanned aircraft applications[END_REF], [START_REF] Ratnoo | Adaptive optimal path following for high wind flights[END_REF]. Secondly, the models using these algorithms do not take into account the wind. An integral action can be considered in order to compensate such a disturbance for following a straight line. However, this approach usually fails for generic This work at ENAC has been supported by the Skycanner project (STAE foundation). 1 Hector Garcia de Marina, Murat Bronz and Gautier Hattenberger are with the University of Toulouse, Ecole nationale de l'aviation civile (ENAC), 31000 Toulouse, France hgdemarina@ieee.org. 2 Yuri Kapitanyiuk and Ming Cao are with the ENTEG institute at the University of Groningen, the Neherlands.

{i.kapitanyuk,m.cao}@rug.nl. trajectories, even circles, since when the UAV is following such a path, the wind velocity vector is not fixed with respect to the body frame. Techniques such as the estimation of the sideslip angle are effective, but the recent results in [START_REF] Fossen | Line-of-sight path following for dubins paths with adaptive sideslip compensation of drift forces[END_REF] are confined to Dubin's path, i.e. straight lines and circles. Thirdly, one can design a generic trajectory matching the physical constraints of the vehicle, e.g. maximum heading rate that determines the bank angle. However, the output from most of the above mentioned algorithms is a heading to be followed by the UAV. This setting point is forwarded usually to another controller in a cascaded fashion, therefore making it difficult to assert that the physical constraints of the UAV are satisfied when the vehicle is not on the desired path.

The work presented in this paper is an extension of the algorithm given in [START_REF] Kapitanyuk | A guiding vector field algorithm for path following control of nonholonomic mobile robots[END_REF]. More precisely, the theoretical contribution of our work includes the technique of dealing with wind disturbance when following a generic sufficiently smooth 2D path, whereas the practical contributions lie in the adaptation and integration of the algorithm to an actual fixed wing UAV. In particular, the presented algorithm is based on the idea of following a vector field [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF], [START_REF] Frew | Lyapunov guidance vector fields for unmanned aircraft applications[END_REF] that converges smoothly to the desired path, where the convergence is global if certain conditions are satisfied. Instead of considering the Euclidean distance, the notion of error is given by the implicit equation of the desired trajectory, making the tracking task much easier to be implemented. Furthermore, this approach makes possible and easy to deal with the problem of tracking time-varying trajectories or to define a 3D trajectory as the intersection of two surfaces [START_REF] Wang | Geometric path following control in a moving frame[END_REF]. This last feature is desirable for certain physical problems. For example, for the sampling of the atmosphere by UAVs [START_REF] Renzaglia | Monitoring the evolution of clouds with uavs[END_REF] one can model the boundary of certain kind of travelling clouds by a 3D slowly changing paraboloid travelling parallel to the ground. The desired trajectory for studying the surroundings of such a cloud can be given by the intersection of a plane with this paraboloid.

Note that the guidance vector field is not a novel concept at all and work based on it covering generic trajectories has been presented [START_REF] Goncalves | Vector fields for robot navigation along time-varying curves in -dimensions[END_REF]. However, the authors in [START_REF] Goncalves | Vector fields for robot navigation along time-varying curves in -dimensions[END_REF] have only considered vehicles that can be modeled by full actuated mass points. This kind of model is not suitable for actual fixed wings, where in an optimal or trimmed flight the air-speed must be constant. In our work, we can consider that the UAV is flying with a constant air-speed, where our algorithm provides the desired heading-rate for the vehicle. If we consider 2D ground parallel trajectories, then the heading rate can be directly translated to a coordinated turn, i.e. a bank angle that makes the UAV to turn without inducing any acceleration in the lateral axis of the vehicle. These turns are desirable because they assist the attitude estimators [START_REF] De Marina | Uav attitude estimation using unscented kalman filter and triad[END_REF], [START_REF] Condomines | Pi-invariant unscented kalman filter for sensor fusion[END_REF] based on the readings of accelerometers, by making easier the observation of the gravity acceleration vector.

The paper is organized as follows. The path following problem under a constant disturbance is set up in Section II. We provide a solution to the problem based on the vector field in Section III derived from a Lyapunov stability analysis. We explain the implementation of the algorithm in an actual fixed-wing UAV and present its performance from actual flights in Section IV. We finally end the paper with some conclusions in Section V.

The presented algorithm in this paper has been implemented in the popular open-source autopilot system Paparazzi [START_REF] Paparazzi | [END_REF] and it is ready to be used by the general public. Therefore both source code and logs (that can be easily replayed in the Paparazzi system) from the experiments in this paper are available online at the Paparazzi website.

II. PROBLEM DEFINITION

We consider for the fixed wing UAV the following holonomic model in 2D

ṗ = sm(ψ) + w ψ = u, (1)
where p ∈ R 2 is the position of the UAV with respect to some inertial navigation frame O N , s ∈ R + is a constant that can be considered as the airspeed, m = cos(ψ) sin(ψ)

T with ψ ∈ (-π, π] being the attitude yaw angle, w ∈ R 2 is a constant1 with respect to O N representing the wind and u is the control action that will make the UAV to turn. Here, the UAV is underactuated. We also notice that the course heading χ ∈ (-π, π], i.e. the direction the velocity vector ṗ is pointing at, in general is different from the yaw angle ψ because of the wind.

Although a fixed wing can fly backwards in O N , i.e. the course heading and the yaw angle differ by π radians, for the sake of simplicity in the analysis we consider the following realistic assumption.

Assumption 2.1: The constant airspeed s is greater than the Euclidean norm of the wind vector w, i.e. s > ||w||.

In fact, it is quite straightforward to realize that this assumption is necessary if one wants to reach a generic desired path from almost every initial position.

Consider the desired path P ∈ R 2 described by the following implicit equation

P := {p : ϕ(p) = 0}, (2)
where we assume that the function ϕ : R 2 → R belongs to the C 2 space and it is regular in a neighborhood of P, i.e.

∇ϕ(p) = 0, p ∈ N P , (3)
where

N P := {p : |ϕ(p)| ≤ c * } for a constant c * ∈ R + .
The plane R 2 can be covered by the following disjoint sets ϕ(p) = c ∈ R, where each level set is defined for a value of c, in particular the zero level set ϕ(p) = 0 corresponds uniquely to the desired path P. Therefore we can employ these level sets for the notion of error distance between the UAV and P, namely

e(p) := ϕ(p) ∈ R. (4)
Note that the error is signed and it differs from the notion of Euclidean distance.

The main goal is to design a control action u(p, ṗ, ψ) such that e(t) → 0 as t → ∞ and because of (1) along with Assumption 2.1 the UAV will travel over P with ṗ(t) = 0, ∀t ≥ 0. As we will see, the control action requires to have available the following states from the UAV, its position and velocity with respect to O N , for example from a GPS signal and its yaw angle also with respect to O N , which can be obtained from a well calibrated compass in areas far away from the Earth's poles.

III. GUIDANCE LAW DESIGN AND ANALYSIS

Let us first introduce some notation. We define by n(p) := ∇ϕ(p) the normal vector to the curve corresponding to the level set ϕ(p) and the tangent vector τ at the same point p is given by the rotation

τ (p) = En(p), E = 0 1 -1 0 .
Note that E will determine in what direction P will be tracked.

The guidance controller is constructed in two steps. The first one is about constructing a guidance vector field such that once the UAV is tracking it, the vehicle will converge to P. The second step deals with the task of steering the UAV in order to converge to such a guiding vector field.

A. Vector field design

The main idea to construct a guiding vector field pointing at P is based on decreasing the norm of (4). Consider the following Lyapunov function

V 1 (p) = 1 2 ||e(p)|| 2 , (5)
whose time derivative along (1) is given by

dV 1 dt = en T ṗ. (6)
Consider the following desired velocity vector

ṗd (p) := τ (p) -k e e(p)n(p), (7)
where k e ∈ R + is a gain that will tune how aggressive the vector field is. It is clear that

en T ṗd = en T τ -e 2 k e ||n|| 2 = -e 2 k e ||n|| 2 ≤ 0, (8)
is decreasing if and only if e = 0 for p ∈ N P . Note that since τ is perpendicular to n, once the UAV is over P then the vehicle will track the direction given by only τ , i.e. the tangent to the desired path. Therefore we define [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF] as the guidance vector field to be followed. In particular, the UAV has to track the orientation of the unit vector of (7), i.e. the desired course heading χ d (p). Remark 3.1: It is clear now the role of Assumption 2.1. If s < ||w|| then the projection of ṗ over the wind direction cannot be negative, therefore making impossible to track the guidance vector field [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF] in general.

Let us define x := x ||x|| for x ∈ R n . Now we are going to calculate what the desired course heading rate χd ( ṗ, p) is once the UAV is tracking correctly the guidance vector field given in [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF], i.e. what the course heading rate is such that the set G := { ṗ : p = pd } is invariant.

The time derivative of the unit vector defining the desired heading is given by

d pd dt = (I -pd pT d ) pd || ṗd || = ( pT d E) T ( pT d E) pd || ṗd || = -E pd pT d E pd || ṗd || , ( 9
)
where I is the identity matrix with the appropriate dimensions and from [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF] we derive

pd = d dt (E -k e e)n = (E -k e e)H(ϕ(p)) ṗ -k e n T ṗn, (10)
where H(•) is the Hessian operator, establishing then the condition of ϕ(p) being C 2 . Physically it means that the UAV in order to track P needs to know how the curvature of the desired trajectory evolves. Now we derive the expression of the desired heading rate χd once ṗ ∈ G. Since || pd || 2 = 1, we have that

1 2 d|| pd || 2 dt = pT d d pd dt = 0, (11)
hence the infinitesimal rotation of pd can be described by

d pd dt = -χd E pd , (12)
which is perpendicular to pd and the angular speed is determined by χd . Working out further [START_REF] Wang | Geometric path following control in a moving frame[END_REF] we identify that

E T d pd dt = -χd pd pT d E T d pd dt = -χd χd = d pd dt T E pd , (13)
therefore by tracking back (10), ( 9) and ( 7) for the angular velocity [START_REF] Renzaglia | Monitoring the evolution of clouds with uavs[END_REF] we notice that the desired course heading rate χd in order to keep G invariant can be computed by only sensing the ground velocity ṗ and position p of the UAV. We summarize such observations into the following Lemma.

Lemma 3.2: The set G := { ṗ : p = pd }, with ṗd being the guidance vector field in [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF], is invariant for the following course heading rate

χ(p, ṗ) = -E pd pT d E (E -k e e) H(ϕ(p)) ṗ -k e n T ṗn T E ṗd || ṗd || 2 , (14)
that only depends on ṗ and p. Proof: By direct inspection of ( 14) it is clear that it only depends on ṗ and p. Consider that p ∈ G with ṗd as in [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF]. Then in order to keep G invariant we have to satisfy the right hand side of (9) for the time derivative of p. The angular velocity ( 14) is the substitution of ( 10) and ( 9) into [START_REF] Renzaglia | Monitoring the evolution of clouds with uavs[END_REF], which determines the course heading rate χ in order to keep G invariant.

Remark 3.3: Notice that the yaw rate ψ and the course heading rate χ are different concepts and quantities. However, according to (1) by actuating over the yaw, we are also actuating over the course heading. The aim of the next section is to show how to design u in (1) such that the UAV is following the appropriated course heading rate.

B. Converging to the guidance vector field

Now we are going to present how to make the UAV to converge to the guidance vector field defined in [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF]. The ground velocity ṗ can be trivially decomposed as ṗ = || ṗ|| p. Now consider the following Lyapunov function

V 2 (η) = 1 -pT pd , (15)
where η ∈ (-π, π] is the angle between the two unit vectors p and pd . It is clear that V 2 (η) = 0 ⇐⇒ η = 0, i.e. the ground velocity of the UAV is aligned with the vector field. Now we are ready for our main result. Theorem 3.4: Consider a desired trajectory P as in (2) such that ϕ(p) is C 2 and satisfies [START_REF] Pixhawk | [END_REF]. Assume that the UAV is modeled by (1) under Assumption 2.1 and the vehicle can measure its ground velocity ṗ, position p and yaw angle ψ with respect to some navigation frame O N . Then the control action

u( ṗ, p, ψ) = ψ = || ṗ|| s cos β χd ( ṗ, p) + k d pT E pd , (16)
where β = arccos pT m(ψ) is the sideslip angle, k d ∈ R + determines how fast the UAV converges to the guidance vector field and χd is given in Lemma 3.2, made to (at least locally) converge the UAV asymptotically to travel over P for all the initial conditions p(0) ∈ N c ⊂ N P , where N c is as N P in (3) but with a constant 0 ≤ c < c * . Proof: We need to show that the unit velocity vector p of the UAV converges asymptotically to the unit velocity vector pd given by the vector field [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF], i.e. χ(p, ṗ, ψ)χ d (p, ṗ, ψ) → 0 as t → ∞. Consider that p(0) ∈ N c and take the time derivative of the Lyapunov function ( 15)

dV 2 dt = -pT d d dt p -pT d dt pd . ( 17
)
We now work out the first time derivative term at the right hand side of ( 17) since the second term has been calculated at [START_REF] Wang | Geometric path following control in a moving frame[END_REF].

d dt p = - 1 || ṗ|| E pp T E d dt ṗ = - s || ṗ|| E pp T E d dt m(ψ) = s || ṗ|| E pp T E ψEm(ψ) = - s ψ || ṗ|| pT m(ψ) E p. ( 18
)
We now substitute ( 18) and ( 12) into ( 17) and we arrive at

dV 2 dt = s ψ || ṗ|| pT m(ψ) pT d E p -χd pT d E p = s ψ || ṗ|| cos β -χd pT d E p, (19)
therefore by choosing

u( ṗ, p, ψ) = ψ = || ṗ|| s cos β χd + k d pT E pd , (20)
we have that

dV 2 dt = -k d ( pT E pd ) 2 ≤ 0, (21)
which is non-increasing in the (compact) set N P . The constant k d has to be big enough such that the UAV does not leave the set N P once the vehicle starts in N c , i.e. we need to align the UAV with the vector field as soon as possible in order to satisfy (3) for all t ≥ 0. The (worst case) calculation of k d is a strictly geometrical and kinematic task that depends on s, w, ψ, c and c * . Because of (21), the condition (3) and Assumption (2.1), by invoking the LaSalle's invariance principle, we conclude that χ (p(t), ṗ(t), ψ(t))χ d (p(t), ṗ(t), ψ(t)) → 0, or equivalently p(t) → G, as t → ∞, implying that p(t) → P as t → ∞ with the UAV travelling over the desired trajectory P with ṗ(t) = 0, ∀t. Remark 3.5: Note that for some trajectories, such as straight lines, we have that N P = R 2 , and therefore the convergence in Theorem 3.4 is global. For other trajectories where the set of critical points ∇φ(p) = 0 is bounded and does not intercept P, e.g. the center of an ellipse, a more precise condition for k d can be given in order to be more specific about N P and N c [START_REF] Kapitanyuk | A guiding vector field algorithm for path following control of nonholonomic mobile robots[END_REF].

Remark 3.6: We also note that if the yaw angle ψ is not accessible or a reliable measurement, e.g. if the UAV is close to the Earth's poles, one can replace it by measuring the sideslip angle β and still employing the results from Theorem 3.4.

Remark 3.7: One can check that a non-constant positive airspeed s(t), but satisfying Assumption 2.1, will not change the convergence results in Theorem 3.4. In fact the condition of having a constant wind w can also be relaxed by just considering that s(t) > sup{||w(t)||}, ∀t ≥ 0.

IV. IMPLEMENTATION AND FLIGHT PERFORMANCE

In this Section we are going to discuss several practical issues in order to implement the guidance vector field [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF] to an actual fixed wing in the opensource project Paparazzi [START_REF] Paparazzi | [END_REF]. We conclude the section by showing the performance of actual flights employing the results in Theorem 3.4.

A. Gain tuning

We are going to show that the gains k e in the guidance vector field [START_REF] Nelson | Vector field path following for miniature air vehicles[END_REF] and k d in the control action ( 16) can be designed in order to satisfy the physical constraint given by the maximum bank angle φ * of the UAV.

If we consider that the flight path angle is zero, i.e. the UAV is keeping its altitude, and s >> ||w||, i.e. we have a small sideslip β, the yaw rate ψ can be well approximated by the following expression [START_REF] Stevens | Aircraft Control and Simulation: Dynamics, Controls Design, and Autonomous Systems[END_REF]

ψ = g tan φ cos θ s , ( 22
)
where g is the gravity acceleration and φ and θ are the roll and pitch attitude angles, respectively, of the UAV. The expression ( 22) is also known as the condition for a coordinated turn. In such a case the UAV does not experience any acceleration in its lateral body axes. This is desirable since many of the attitude estimation algorithms employed in projects like Paparazzi, such as [START_REF] De Marina | Uav attitude estimation using unscented kalman filter and triad[END_REF], [START_REF] Condomines | Pi-invariant unscented kalman filter for sensor fusion[END_REF], are based on the observation of gravity. We also consider that in a trimmed flight, the pitch angle θ remains constant and usually is close to zero. From (22) it is clear that we have to satisfy

|φ * | ≤ arctan s u( ṗ, p, ψ) g cos θ . ( 23
)
If one is interested in visiting a certain area with the UAV, then it should restrict the desired trajectory P such that (23) is satisfied under the worst case condition for || ṗ|| (determined by the expected wind speed) in ( 16) with η = 0.

Our algorithm covers the popular splines [START_REF] Gill | Spline path following for redundant mechanical systems[END_REF] for trajectory generation in order to satisfy constraints such as (23). The worst condition determined by k d is given when p and pd are perpendicular, so it is straightforward to calculate such a contribution in (23) having in mind that it should be sufficiently big (in the transient of the UAV converging to the guidance vector field) according to Theorem 3.4 for keeping p(t) ∈ N P . Finally, k e directly influences how smooth (compromised by how fast) the convergence of the guidance vector field to P is and it can be chosen arbitrarily small. Therefore, one can calculate beforehand the values of k e and k d such that (23) is satisfied in N P .

B. Experimental platform

We have tested the performance of Theorem 3.4 in our fixed wing UAV shown in Figure 1 called Jumper. It is about 450grams of weight, 70cm of wingspan, actuated by two elevons and one motor. The electronics include a battery that allows about 30 minutes of flight at the nominal flight, which corresponds to about an airspeed of s = 11m/s. The vehicle has a high maneuverability and we have set in the autopilot Although there is a logging system on board, the vehicle counts with a serial radio link in order to monitor its status from the ground. The algorithm in Theorem 3.4 has been programmed as a (guidance) module in Paparazzi and it can be combined or integrated easily with other modules in the system. In particular, we have set the periodic frequency of the guidance vector field module to 60Hz. The source code can be checked online at the Paparazzi repository, where the implementation of the guidance algorithm is independent of the trajectory. This allows other users to specify their own trajectories by only defining the implicit ϕ(p), ∇ϕ(p) and H(ϕ(p)) in C-code. In addition, Paparazzi allows easily to change parameters on flight, and different values for k e and k d can be set on-the-fly from the ground station.

C. Flight experiments

The flights have been taken place at the aero model club of Eole at Muret, close to the city of Toulouse in France. We tried the flights on the 18th of August, 2016 between the 14:00 and 18:00 hours local time. The wind according to the weather service of MeteoFrance was about 5m/s blowing from the East with gusts of about 10m/s. Therefore Jumper satisfies Assumption 2.1.

As a benchmark we consider different ellipses as desired P, namely

ϕ(p) = (p x -h x ) cos α -(p y -h y ) sin α a 2 + (p x -h x ) sin α + (p y -h y ) cos α b 2 -1, (24)
where h = h x h y T is the center of the ellipse with respect to O N , α is the rotation angle of the ellipse with respect to the horizontal axis of O N and a and b are the lengths of the ellipse's axis. Note that only for p = h we have that ∇ϕ(p) = 0, therefore (24) satisfies (3) for some c * > 0.

The autopilot allows to have a fully automated flight, from the take-off until the landing. We show in Figure 2 one of the tested ellipses corresponding to a = 50, b = 75 meters and α = -15 degrees, together with the described Jumper's trajectory. We have designed k e = 0.4 and k d = 1 such that φ (without wind) is less than 40 degrees for c * ≤ 6 in N P . We describe the experiment in more detail in Figures 234.

V. CONCLUSIONS

This paper has presented an algorithm for making fixed wing UAVs following smooth trajectories under the presence of wind. The guidance strategy is based on tracking a vector field generated from the implicit form of the desired trajectory. The simplicity of this algorithm allows its implementation in small embedded systems as the Apogee autopilot. The algorithm has been implemented in Paparazzi Fig. 2: Screenshot of the Paparazzi's ground control station. From the flight log we have drawn on top several positions of the UAV (blue triangles). The yaw ψ is represented by the orientation of the triangle and the black arrows stand for the course heading. The desired ellipse has been marked with a black dashed line. We have marked the last position of the UAV, after two turns to the ellipse, in red color. The vector field is represented in white color and the blue line is the actual trajectory. The wind is about 5m/s (almost 50% of the airspeed of the UAV), blowing to the East. as an independent module and does not depend on the desired trajectory, allowing other users to employ the algorithm by just codifying the implicit equation of the trajectory, along with its gradient and Hessian.

We are currently extending and testing the results of this paper for formation flying control by employing the different level sets of a desired trajectory as an input for consensus algorithms and combining the recent findings in [START_REF] De Marina | Distributed rotational and translational maneuvering of rigid formations and their applications[END_REF], [START_REF] Garcia De Marina | Controlling rigid formations of mobile agents under inconsistent measurements[END_REF] for controlling rigid formations.

Fig. 1 :

 1 Fig. 1: UAV Jumper at the aero model club of Eole at Muret (Toulouse) before the experiment's flight in a pre-storm day.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Adimensional error signal for (24). Note that this signal is different from the notion of Euclidean distance. One meter of distance to the ellipse might correspond to different values of e. For example, when the UAV is crossing the major or the minor ellipse's axis, i.e. a+1 a = b+1 b .

For the sake of simplicity we consider that w is constant, but we will see after the main result that this requirement can be indeed relaxed.