Luis Pedro Montejano
email: lpmontejano@gmail.com

Ignasi Sau
email: ignasi.sau@lirmm.fr

On the complexity of computing the k-restricted edge-connectivity of a graph

Keywords: Graph cut, k-restricted edge-connectivity, Good edge separation, Parameterized complexity, FPT-algorithm, Polynomial kernel

The k-restricted edge-connectivity of a graph G, denoted by λ k (G), is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least k vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing λ k (G). Very recently, in the parameterized complexity community the notion of good edge separation of a graph has been defined, which happens to be essentially the same as the k-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, in this article we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms.

Introduction

Motivation. The k-restricted edge-connectivity is a graph invariant that has been widely studied in the literature from a combinatorial point of view [START_REF] Balbuena | Extraconnectivity of graphs with large minimum degree and girth[END_REF][START_REF] Bonsma | Edge-cuts leaving components of order at least three[END_REF][START_REF] Fàbrega | Extraconnectivity of graphs with large girth[END_REF][START_REF] Holtkamp | k-restricted edge-connectivity in triangle-free graphs[END_REF][START_REF] Yuan | Sufficient conditions for λ k -optimality in triangle-free graphs[END_REF][START_REF] Zhang | A proof of an inequality concerning k-restricted edgeconnectivity[END_REF]. Since the classical edge-connectivity may not suffice to measure accurately how connected a graph is after deleting some edges, Esfahanian and Hakimi [START_REF] Esfahanian | On computing a conditional edge-connectivity of a graph[END_REF] proposed in 1988 the notion of restricted edge-connectivity. Given a graph G, a non-empty set S ⊆ E(G) is an edge-cut if G -S has at least two connected components. An edge-cut S is called a restricted edge-cut if there are no isolated vertices in G -S. The restricted edge-connectivity λ (G) is the minimum cardinality over all restricted edge-cuts S.

Inspired by the above definition, Fàbrega and Fiol [START_REF] Fàbrega | Extraconnectivity of graphs with large girth[END_REF] proposed in 1994 the notion of k-restricted edge-connectivity, where k is a positive integer, generalizing this notion. An edge-cut S is called a k-restricted edge-cut if every component of G -S has at least k vertices. Assuming that G has k-restricted edge-cuts, the k-restricted edge-connectivity of G, denoted by λ k (G), is defined as the minimum cardinality over all k-restricted edge-cuts of G, i.e., λ k (G) = min{|S| : S ⊆ E(G) is a k-restricted edge-cut}.

Note that for any graph G, λ 1 (G) is the size of a minimum edge-cut, and λ 2 (G) = λ (G). A connected graph G is called λ k -connected if λ k (G) exists. Let [X, Y ] denote the set of edges between two disjoint vertex sets X, Y ⊆ V (G), and let X denote the complement X = V (G) \ X of vertex set X. It is clear that for any k-restricted cut [X, X] of size λ k (G), the graph G -[X, X] has exactly two connected components.

Very recently, Chitnis et al. [START_REF] Chitnis | Designing FPT algorithms for cut problems using randomized contractions[END_REF] defined the notion of good edge separation for algorithmic purposes. For two positive integers k and , a partition (X, X) of the vertex set of a connected graph G is called a (k, )-good edge separation if |X|, |X| > k, |[X, X]| ≤ , and both G[X] and G[X] are connected. That is, it holds that λ k (G) ≤ if and only if G admits a (k -1, )-good edge separation. Thus both notions, which have been defined independently and for which there existed no connection so far, are essentially the same.

Good edge separations turned out to be very useful for designing parameterized algorithms for cut problems [START_REF] Chitnis | Designing FPT algorithms for cut problems using randomized contractions[END_REF], by using a technique known as recursive understanding, which basically consists in breaking up the input graph into highly connected pieces in which the considered problem can be efficiently solved. It should be mentioned that Kawarabayashi and Thorup [START_REF] Kawarabayashi | The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable[END_REF] had defined before a very similar notion for vertex-cuts and introduced the idea of recursive understanding. This technique has also been subsequently used in [START_REF] Cygan | Minimum bisection is fixed parameter tractable[END_REF][START_REF] Kim | Parameterized algorithms for minmax multiway cut and list digraph homomorphism[END_REF][START_REF] Rai | A parameterized algorithm for mixedcut[END_REF].

Very little is known about the complexity of computing the k-restricted edgeconnectivity of a graph, in spite of its extensive study in combinatorics. In this article we initiate a systematic analysis on this topic, with special emphasis on the parameterized complexity of the problem. In a nutshell, the main idea is to identify relevant parameters of the input of some problem, and study how the running time of an algorithm solving the problem depends on the chosen parameters. See [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for introductory textbooks to this area.

Our results. We consider the following two problems concerning the krestricted edge-connectivity of a graph.

Existential Restricted Edge-connectivity (EREC)

Instance: A graph G = (V, E) and a positive integer k. Question: Is G λ k -connected ?

Restricted Edge-connectivity (REC) Instance: A connected graph G = (V, E) and a positive integer k.

Output: λ k (G), or a correct report that G is not λ k -connected.
The latter problem can be seen as a generalization of computing a Minimum Cut in a graph, which is polynomial-time solvable [START_REF] Stoer | A simple min-cut algorithm[END_REF]. In Section 2 we prove that it is NP-hard, even restricted to λ k -connected graphs. In Section 3 we study the parameterized complexity of the REC problem. More precisely, given a connected graph G and two integers k and , we consider the problem of determining whether λ k (G) ≤ . Existing results concerning good edge separations imply that the problem is FPT when parameterized by k and . We prove that it is W[1]-hard when parameterized by k, and that it is FPT when parameterized by but unlikely to admit polynomial kernels. Moreover, we prove that the EREC problem is FPT when parameterized by k. Finally, in Section 4 we also consider the maximum degree ∆ of the input graph as a parameter, and we prove that the EREC problem remains NP-complete in graphs with ∆ ≤ 5, and that the REC problem is FPT when parameterized by k and ∆. Note that this implies, in particular, that the REC problem parameterized by k is FPT in graphs of bounded degree. Table 1. Summary of our results, where ∆ denotes the maximum degree of the input graph G, and NPc (resp. NPh) stands for NP-complete (resp. NP-hard).

k + k k + ∆ Is G NPc, even FPT FPT λ k -connected ? if ∆ ≤ 5 (Thm 4) (Thm 8) (Thm 7) NPh, even if G FPT W[1]-hard FPT (Thm 5) FPT λ k (G) ≤ ? is λ k -connected (
The symbol ' ' denotes that the problem is not defined for that parameter.

Further research. Some open questions are determining the existence of polynomial kernels for the REC problem with parameters k + or k + ∆, speeding-up the FPT algorithm of Theorem 5 (which is quite inefficient), improving the bound on the maximum degree in Theorem 7, and studying the (parameterized) complexity of the REC problem in planar graphs and other sparse graph classes.

Notation. We use standard graph-theoretic notation; see for instance [START_REF] Diestel | Graph Theory[END_REF]. For a graph G, let ∆(G) denote its maximum degree, and for a vertex v, its degree in G is denoted by

d G (v). If S ⊆ V (G), we define G -S = G[V (G) \ S],
and if S ⊆ E(G), we define G -S = (V (G), E(G) \ S). Unless stated otherwise, throughout the article n denotes the number of vertices of the input graph of the problem under consideration. We will always assume that the input graphs are connected.

Preliminary results

Clearly, any connected graph G is λ 1 -connected, and λ 1 (G) can be computed in polynomial time by a Minimum Cut algorithm (cf. [START_REF] Stoer | A simple min-cut algorithm[END_REF]). However, for k ≥ 2, there exist infinitely many connected graphs which are not λ k -connected, such as the graphs containing a cut vertex u such that every component of Gu has at most k -1 vertices (these graphs are called flowers in the literature [START_REF] Bonsma | Edge-cuts leaving components of order at least three[END_REF], and correspond exactly to stars when k = 2). Moreover, the EREC problem is hard. Indeed, given a graph G, if n is even and k = n/2, by [14, Theorem 2.2] it is NP-complete to determine whether G contains two vertex-disjoint connected subgraphs of order n/2 each. We can summarize this discussion as follows.

Remark 1. The EREC problem is NP-complete.

In Section 4 we will strengthen the above hardness result to the case where the maximum degree of the input graph is at most 5.

Note that Remark 1 implies that the REC problem problem is NP-hard. Furthermore, even if the input graph G is guaranteed to be λ k -connected, computing λ k (G) remains hard, as shown by the following theorem.

Theorem 1. The REC problem is NP-hard restricted to λ k -connected graphs.

Proof: We prove it for n even and k = n/2. The reduction is from the Minimum Bisection problem1 restricted to connected 3-regular graphs, which is known to be NP-hard [START_REF] Berman | Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION[END_REF]. Given a 3-regular connected graph G with even number of vertices as instance of Minimum Bisection, we construct from it an instance G of REC by adding two non-adjacent universal vertices v 1 and v 2 . Note that G is λ n/2 -connected, since any bipartition of V (G ) containing v 1 and v 2 in different parts induces two connected subgraphs.

We claim that v 1 and v 2 should necessarily belong to different connected subgraphs in any optimal solution in G . Indeed, let (

V 1 , V 2 ) be a bipartition of V (G) such that |[V 1 , V 2 ]| = λ n/2 (G ), and assume for contradiction that v 1 , v 2 ∈ V 1 . Since G is connected, there is a vertex u ∈ V 2 with at least one neighbor in V 1 \ {v 1 , v 2 }. Let V 1 := V 1 ∪ {u} \ {v 2 } and V 2 := V 2 ∪ {v 2 } \ {u}, and note that both G[V 1 ] and G[V 2 ] are connected. Since u has at least one neighbor in V 1 \ {v 1 , v 2 }, G is 3-regular,
and v 1 and v 2 are non-adjacent and adjacent to all other vertices of G , it can be checked that

|[V 1 , V 2 ]| ≤ |[V 1 , V 2 ]|-1 = λ n/2 (G )-1, contradicting the definition of λ n/2 (G ).
Therefore, solving the REC problem in G corresponds exactly to solving the Minimum Bisection problem in G, concluding the proof.

A parameterized analysis

The NP-hardness results of the previous section naturally lead to considering parameterized versions of the problem. In this section we consider the following three distinct parameterizations.

Parameterized Restricted Edge-connectivity (p-REC)

Instance: Question:

A connected graph G = (V, E)
λ k (G) ≤ ?
As mentioned in the introduction, determining whether λ k (G) ≤ corresponds exactly to determining whether G admits a (k -1, )-good edge separation. This latter problem has been recently shown to be solvable in time

2 O(min{k, } log(k+ )) • n 3 log n by Chitnis et al. [6, Lemma II.2].
Theorem 2 (Chitnis et al. [START_REF] Chitnis | Designing FPT algorithms for cut problems using randomized contractions[END_REF]). The p-REC problem is FPT when parameterized by both k and .

We would like to note that any improvement on the running time of the algorithm behind Theorem 2 would answer an open question raised in [START_REF] Cygan | Open problems from School on Parameterized Algorithms and Complexity[END_REF][START_REF] Cygan | Open problems from Update Meeting on Graph Separation Problems[END_REF], and would have direct consequences and improve the algorithms described in [START_REF] Chitnis | Designing FPT algorithms for cut problems using randomized contractions[END_REF][START_REF] Cygan | Minimum bisection is fixed parameter tractable[END_REF][START_REF] Kim | Parameterized algorithms for minmax multiway cut and list digraph homomorphism[END_REF].

As pointed out in [START_REF] Esfahanian | On computing a conditional edge-connectivity of a graph[END_REF][START_REF] Holtkamp | Connectivity in Graphs and Digraphs[END_REF], the p-REC problem can be solved in time O * (n 2k ). Roughly, the idea is to guess two sets of k vertices inducing a connected subgraph, contract them into two vertices s and t, and then call a polynomial-time Minimum Cut algorithm between s and t (cf. [START_REF] Stoer | A simple min-cut algorithm[END_REF]). In other words, it is in XP when parameterized by k. The following theorem shows that this is essentially the best algorithm we can hope for when the parameter is only k. Indeed, since the blow-up of the parameter in the reduction is linear, the fact that k-Clique cannot be solved in time f (k) • n o(k) unless an unlikely collapse occurs in parameterized complexity theory [START_REF] Chen | Strong computational lower bounds via parameterized complexity[END_REF] implies that the p-REC problem cannot be solved in time

f (k) • n o(k) either. Theorem 3. The p-REC problem is W[1]-hard when parameterized by k.
Proof: We reduce from k-Clique, which is known to be W[1]-hard [START_REF] Downey | Parameterized Complexity[END_REF]. The parameterized reduction is the same as the one given by Downey et al. in [START_REF] Downey | Cutting up is hard to do: the parameterized complexity of k-cut and related problems[END_REF]Theorem 2] to show the W[1]-hardness of the Cutting k Vertices from a Graph problem, only the analysis changes.

Let G = (V, E) be an n-vertex graph for which we wish to determine whether it has a k-clique. We construct a graph G as follows:

(1) We start with a clique C of size n 3 and n representative vertices corresponding bijectively with the vertices of G.

(2) Every representative vertex v is connected to

n 2 -d G (v) arbitrary vertices of C. (3) If uv ∈ E(G) then uv ∈ E(G ). n 2 -d v C = K n 3 (v) G G n representative vertices
≤ n/2. We claim that G has a k-clique if and only if G is a Yes-instance of p-REC. Suppose first that K ⊆ V (G) is a k-clique in G. Obviously, K is connected in G and has k vertices. On the other hand, G -K is also connected with at least n 3 -|K| > k vertices. Finally, it is straightforward to check that |[K, V (G )\K]| = kn 2 -2 k 2 = .
In the other direction, suppose G has a k-restricted edge-cut with at most edges, i.e., there exists

K ⊆ V (G ) such that G[K] and G -K are connected, |K| ≥ k, |V (G ) \ K| ≥ k, and |[K, V (G ) \ K]| ≤ . Two cases need to be distinguished. Case 1. C ∩ K = ∅. Then every vertex of K must be a representative vertex. Hence |[K, V (G ) \ K]| = |K|n 2 -2|E(G [K])| since every representative vertex has degree n 2 . As by hypothesis |[K, V (G ) \ K]| ≤ = kn 2 -2 k 2 , it follows that |E(G [K])| = k 2 , hence K must be a k-clique. Case 2. C ∩ K = ∅. Note that for every bipartition (C 1 , C 2 ) of C we have that |[C 1 , C 2 ]| ≥ n 3 -1 > . Now suppose C ∩ (V (G ) \ K) = ∅ and consider the bipartition C 1 = C ∩ K and C 2 = C ∩ (V (G ) \ K) of C. Then |[K, V (G ) \ K]| ≥ |[C 1 , C 2 ]| ≥ n 3 -1 > , a contradiction. Therefore, we have that C ∩(V (G )\K) = ∅. The proof concludes by applying Case 1 to V (G ) \ K instead of K.
In contrast to Theorem 3 above, we now prove that the EREC problem (which is NP-complete by Remark 1) is FPT when parameterized by k. The proof uses the technique of splitters introduced by Naor et al. [START_REF] Naor | Splitters and near-optimal derandomization[END_REF], which has also been recently used for designing parameterized algorithms in [START_REF] Chitnis | Designing FPT algorithms for cut problems using randomized contractions[END_REF][START_REF] Cygan | Minimum bisection is fixed parameter tractable[END_REF][START_REF] Kim | Parameterized algorithms for minmax multiway cut and list digraph homomorphism[END_REF]. Our main tool is the following lemma. • n log n the desired family F of subsets of vertices of G. Now, if such trees T 1 and T 2 exist, then necessarily there exists a set S ∈ F such that V (T 1 ) ⊆ S and V (T 2 ) ∩ S = ∅. Therefore, in order to determine whether G is λ k -connected or not, it suffices to check, for each set S ∈ F, whether both G[S] and G -S contain a connected component with at least k vertices. (Note that for each such set S ∈ F, this can be done in linear time.) Indeed, if such a set S exists, then clearly G is λ k -connected. Otherwise, by the property of the family F, G does not contain two disjoint trees T 1 and T 2 of size k each, and therefore G is not λ k -connected.

Concerning the parameterized complexity of the p-REC problem, in view of Theorems 2 and 3, it just remains to settle the case when the parameter is only. The following theorem provides an answer to this question. We will need the following result, which is a reformulation of [START_REF] Van Bevern | On the parameterized complexity of computing graph bisections[END_REF]Corollary 1].

Lemma 2 (van Bevern et al. [START_REF] Van Bevern | On the parameterized complexity of computing graph bisections[END_REF]). Given a graph G on n vertices and an integer , determining whether λ n/2 (G) ≤ can be solved in time f ( ) • n 11 for some explicit function f depending only on .

Theorem 5. The p-REC problem is FPT when parameterized by .

Proof: If k ≤ , we solve the problem using the FPT algorithm given by Theorem 2 with parameter k + ≤ 2 . Otherwise, in the case where k > , we proceed to Turing-reduce the problem to the particular case where k = n/2 , which is FPTwith parameter by Lemma 2 above, as follows. For each vertex v of the n-vertex input graph G, and for each integer p with 0 ≤ p ≤ n -2k, let G p v be the graph obtained from G by adding a clique K p on p vertices and all the edges between vertex v and the vertices in K p .

Claim. It holds that λ k (G) ≤ if and only if there exist a vertex v ∈ V (G) and an integer p with 0

≤ p ≤ n -2k such that λ n+p 2 (G p v ) ≤ . Proof: Assume first that λ k (G) ≤ . Let (X, X) be a partition of V (G) achieving λ k (G)
, where we assume without loss of generality that X ≥ X, let p = |X| -|X|, and let v be any vertex in X. Then p ≤ (nk)k = n -2k and by construction it holds that λ n+p

2 (G p v ) ≤ λ k (G) ≤ . Conversely, suppose that there exist a vertex v ∈ V (G) and an integer p with 0 ≤ p ≤ n -2k such that λ n+p 2 (G p v ) ≤ . Let (X, X) be a partition of V (G p v ) achieving λ n+p 2 (G p v )
, and assume without loss of generality that v ∈ X. We claim that the clique K p is entirely contained in X. Indeed, suppose for contradiction that K p ∩ X = ∅, and let K

= K p ∩ X. Since G p v [X] is connected and v ∈ X, necessarily X = K. We distinguish two cases. If p < k, then |X| = |K| ≤ p -1 ≤ k -2 ≤ n/2 -2 < n+p 2
, contradicting the definition of λ n+p 2 (G p v ). Otherwise, if p ≥ k, then we use that the number of edges in [X, X] is at least the minimum cut of the clique of size p+1 induced by K p ∪{v}, which is equal to

p. That is, |[X, X]| ≥ p ≥ k > , contradicting the hypothesis that (X, X) is a partition of V (G p v ) achieving λ n+p 2 (G p v )
≤ . We now claim that the partition of V (G) given by (X, X \ K p ) defines a k-restricted edge-cut of G with at most edges, concluding the proof. First note that both G[X] and G[X \ K p ] are connected, since both G p v [X] and G p v [X] are connected by hypothesis, and the removal of K p from G p v [X] clearly preserves connectivity. On the other hand, we have that

|X| ≥ n+p 2 ≥ n 2 ≥ k and |X \ K p | = |X| -p ≥ n+p 2 -p ≥ n-p-1 2 ≥ n-(n-2k)-1 2 = k -1
2 , and since both |X \ K p | and k are integers, the latter inequality implies that

|X \ K p | ≥ k. Finally, since K p ⊆ X, it holds that |[X, X \ K p ]| = |[X, X]| ≤ .
Note that the above claim yields the theorem, as it implies that the problem of deciding whether λ k (G) ≤ can be solved by invoking O(n 2 ) times the FPT algorithm given by Lemma 2.

To complement Theorem 5, in the next theorem we prove that the p-REC problem does not admit polynomial kernels when parameterized by , unless coNP ⊆ NP/poly. Theorem 6. Unless coNP ⊆ NP/poly, the p-REC problem does not admit polynomial kernels when parameterized by .

Proof:

The proof is strongly inspired by the one given by van Bevern et al. [START_REF] Van Bevern | On the parameterized complexity of computing graph bisections[END_REF]Theorem 3] to prove that the Minimum Bisection problem does not admit polynomial kernels, which in turn resembles the proof given by Garey et al. [START_REF] Garey | Some simplified NP-complete graph problems[END_REF] to prove the NP-hardness of Minimum Bisection. The main difference with respect to the proof given in [START_REF] Van Bevern | On the parameterized complexity of computing graph bisections[END_REF] is that we need to make the appropriate modifications to guarantee that both parts left out by the edge-cut are connected, which is not an issue in the Minimum Bisection problem.

We will first rule out the existence of polynomial kernels for the generalization of p-REC where the edges have non-negative integer weights, and the objective is to decide whether the input graph can be partitioned into two connected subgraphs with at least k vertices each by removing a set of edges whose total weight does not exceed . We call this problem Edge-Weighted p-REC. Then it will just remain to get rid of the edge weights. This is done at the end of the proof of the theorem.

As shown by Bodlaender et al. [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF], in order to prove that Edge-Weighted p-REC does not admit polynomial kernels when parameterized by (assuming that coNP ⊆ NP/poly), it is sufficient to define a cross composition from an NPhard problem to Edge-Weighted p-REC. In our case, the NP-hard problem is Maximum Cut (see [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]), which is defined as follows. Given a graph G = (V, E) and an integer p, one has to decide whether V can be partitioned into two sets A and B such that there are at least p edges with an endpoint in A and an endpoint in B.

A cross composition from Maximum Cut to Edge-Weighted p-REC parameterized by consists of a polynomial-time algorithm that, given t instances (G 1 , p 1 ), . . . , (G t , p t ) of Maximum Cut, constructs an instance (G * , k, ) of Edge-Weighted p-REC such that (G * , k, ) is a Yes-instance if and only if one of the t instances of Maximum Cut is a Yes-instance, and such that is polynomially bounded as a function of max 1≤i≤t |V (G i )|. Similarly to [START_REF] Van Bevern | On the parameterized complexity of computing graph bisections[END_REF], we may safely assume that for each 1 ≤ i ≤ t we have |V (G i )| =: n and p i =: p (by the arguments given in [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF]), that 1 ≤ p ≤ n 2 (as if p = 0 all instances are Yes-instances, and if p > n 2 all instances are No-instances), and that t is odd (otherwise, we can add a No-instance consisting of an edgeless graph on n vertices).

Given (G 1 , p), . . . , (G t , p), we create G * as follows; see Fig. 2 for an illustration. Let w 1 := 5n 2 and w 2 := 5. For each graph G i = (V i , E i ) add to G * the vertices in V i and a clique V i with |V i | = n vertices whose edges have weight w 1 . Add an edge of weight w 1 between each vertex in V i and each vertex in V i . For each pair of vertices u, v ∈ V i , add the edge {u, v} to G * with weight w 1w 2 if {u, v} ∈ E i , and with weight w 1 otherwise. Let s 1 i , s 2 i be two arbitrary distinct vertices in V i , which we call link vertices. For 1 ≤ i ≤ t -1, add two edges with weight 1 between s 1 i and s 1 i+1 and between s 2 i and s 2 i+1 , and two edges with weight 1 between s 1 t and s 1 1 and between s 2 t and s 2 1 . This completes the construction of G * . These 2t edges among distinct V i 's are called chain edges (cf. the thicker edges in Fig. 2). Finally, we set k := |V (G * )|/2 and := w 1 n 2w 2 p + 4. Note that k is not polynomially bounded in terms of n, but this is not a problem since the parameter we consider is , which is bounded by 5n 4 . This construction can be clearly performed in polynomial time in t • n. We claim that (G * , k, ) is a Yes-instance of Edge-Weighted p-REC if and only if there exists i ∈ {1, . . . , t} such that (G i , p) is a Yes-instance of Maximum Cut. 2. Illustration of the graph G * in the proof of Theorem 6. Now we construct another solution A B of Edge-Weighted p-REC in G * where the a i + a j vertices are cut in only one of V i ∪ V i and V j ∪ V j , say V i ∪ V i (note that this is possible since a i + a j ≤ 2n). In order to do so, as far as there exists such a pair a i , a j , we proceed as follows. If a i + a j = 2n, then V i ∪ V i is entirely contained in A or B . Otherwise, if a i + a j < 2n, then we choose (V i ∪ V i ) ∩ A such that it contains exactly one of s 1 i and s 2 i . At the end of this procedure, exactly one graph G i is cut. Finally, we arrange the other G 's, with = i, consecutively into A and B . That is, we put the vertices of i+ t/2 =i+1 V ∪V into A , and the vertices of i and s 2 i . Let i, j be two indices for which the above procedure has been applied. Taking into account that each V i has four incident chain edges, the total weight of the edges cut in G * [V i ∪ V i ] and G * [V j ∪ V j ] by the new solution is at most

w1 w1 w1 w1 V 1 V 1 V 2 V 2 V i V i V t V t w1 w1 w1 1 1 1 1 -w2 s 1 1 s 2 1 s 1 2 s 2 2 s 2 i s 1 i s 1 t s 2 t Fig.
w 1 (a i + a j )(2n -a i -a j ) + 8 = 2nw 1 (a i + a j ) -w 1 (a 2
i + a 2 j ) -2w 1 a i a j + 8. That is, the weight of the cut defined by A B minus the weight of the cut defined by A B is at least

-2w 2 (p -1) + 2w 1 a i a j -8 = 2(w 1 a i a j -w 2 (p -1) -4) ≥ 2(w 1 -w 2 (n 2 -1) -4) > 0,
where we have used that a i , a j ≥ 1, p ≤ n 2 , w 1 = 5n 2 , and w 2 = 5. In other words, A B defines a cut of strictly smaller weight, contradicting the definition of A B.

To conclude the proof of the theorem, it just remains to deal with the edge weights. As in [START_REF] Van Bevern | On the parameterized complexity of computing graph bisections[END_REF], we show how to convert the instance (G * , k, ) of Edge-Weighted p-REC that we just constructed into an equivalent instance of p-REC such that the resulting parameter remains polynomial in n. Given (G * , k, ), we define ( Ĝ, k, ) as the instance of p-REC, where Ĝ is an unweighted graph obtained from G * as follows. We replace each vertex v of G * with a clique C v of size w 1 + + 1, and for each edge {u, v} of G * with weight w, we add w pairwise disjoint edges between the cliques C u and C v . Since no cut of size at most in Ĝ can separate a clique C v introduced for a vertex v, it follows that (G * , k, ) is a Yes-instance of Edge-Weighted p-REC if and only if ( Ĝ, k, ) is a Yes-instance of p-REC. Finally, it is clear that the desired cut size is still polynomial in n.

Considering the maximum degree as a parameter

Towards understanding the parameterized complexity of the REC problem, one may wonder whether considering the maximum degree of the input graph as an extra parameter turns the problem easier (this is a classical approach in parameterized complexity, see for instance [START_REF] Marx | Parameterized graph separation problems[END_REF][START_REF] Marx | Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)[END_REF]). We first prove that, from a classical complexity point of view, bounding the degree of the input graph does not turn the problem easier. Before stating the hardness result, we need the define the 3-Dimensional Matching problem, 3DM for short.

An It is known that 3DM is NP-complete even if each element of W appears in 2 or 3 triples only [START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF][START_REF] Dyer | Planar 3DM is NP-complete[END_REF]. In [14, Theorem 2.2] it is proved that partitioning a graph G into two connected subgraphs of equal size is NP-hard, using a reduction from 3DM. It is worth noting that the graph constructed in the NP-hardness reduction contains only two vertices of degree greater than five. In Theorem 7 we appropriately modify the reduction of [14, Theorem 2.2] so that the constructed graph has maximum degree at most 5. Next, we show that for k = n/2, G is Yes-instance of the REC problem if and only if T contains a matching covering W .

One direction is easy. Suppose first that T contains a matching M covering W . Let S = {a} ∪ P a ∪ T a ∪ (T \ M ). It is straightforward to check that |S| = n/2 and that G[S], G[V \ S] are both connected.

Conversely, suppose that G can be partitioned into 2 connected subgraphs G[S], G[V \S] with |S| = n/2. We can assume that a ∈ S, and then it follows that

  Thm 2, (Thm 3) No poly kernels (Thm 8

and two integers k and . Parameter 1 :

 1 The integers k and . Parameter 2: The integer k. Parameter 3: The integer .

Fig. 1 .

 1 Fig. 1. Illustration of the graph G in the proof of Theorem 3.

Lemma 1 (

 1 Chitnis et al.[START_REF] Chitnis | Designing FPT algorithms for cut problems using randomized contractions[END_REF]). There exists an algorithm that given a set U of size n and two integers a, b ∈ [0, n], outputs in time 2 O(min{a,b}•log(a+b)) • n log n a set F ⊆ 2 U with |F| = 2 O(min{a,b}•log(a+b)) • log n such that for every two sets A, B ⊆ U , where A ∩ B = ∅, |A| ≤ a, and |B| ≤ b, there exists a set S ∈ F with A ⊆ S and B ∩ S = ∅. Theorem 4. The EREC problem is FPT when parameterized by k. More precisely, it can be solved by an algorithm running in time 2 O(k log k) • n 2 log n.Proof: We use the easy property that G is λ k -connected if and only if G contains two vertex-disjoint trees T 1 and T 2 such that |V (T 1 )| ≥ k and |V (T 2 )| ≥ k. In order to apply Lemma 1, we take U = V (G) and a = b = k, obtaining in time kO(k)

i- 1 =i+ t/ 2 V

 12 ∪V into B , where the indices are counted cyclically from 1 to t. The connectivity of both G * [A ] and G * [B ] is guaranteed by the chain edges and the choice of the selector vertices s 1

Fig. 3 .

 3 Fig. 3. Representation of an instance of 3DM.

Theorem 7 .Fig. 4 .

 74 Fig. 4. Construction of the graph G in the proof of Theorem 7, with ∆(G) = 5.

Table 1

 1 below summarizes the results of this article.

	Problem	Classical	Parameterized complexity with parameter
		complexity

Given a graph G with even number of vertices, the Minimum Bisection problem consists in partitioning V (G) into two equally-sized parts minimizing the number of edges with one endpoint in each part.

Acknowledgement. We would like to thank the anonymous referees for helpful remarks that improved the presentation of the manuscript. We are particularly grateful for the ideas to prove Theorem 5, a result that we had left as an open question in the conference version of this article.

Assume first that there exists i ∈ {1, . . . , t} such that (G i , p) is a Yesinstance of Maximum Cut. Assume without loss of generality that i = 1, and let V 1 = A B such that there are at least p edges in E 1 between A and B. We proceed to partition V (G * ) into two equally-sized sets A and B such that both G * [A ] and G * [B ] are connected, and such that the total weight of the edges in G * with one endpoint in A and one endpoint in B is at most . The set

1 and s 2 1 (this is possible since 1 ≤ |B| ≤ n -1), and

which is in turn connected to V t since B contains exactly one of the link vertices s 1 1 and s 2 1 . Finally, let us show that the total weight of the edges between A and B is at most . Note first that two chain edges incident to V 1 and two chain edges incident to V t/2 belong to the cut defined by A and B , and no other chain edge belongs to the cut. Beside the chain edges, only edges in the graph

at least p of the edges of weight w 1w 2 belong to the cut. Therefore, the total weight of the cut is at most w 1 n 2w 2 p + 4 = .

Conversely, assume that for all i ∈ {1, . . . , t}, (G i , p) is a No-instance of Maximum Cut, and we want to prove that (G * , k, ) is a No-instance of Edge-Weighted p-REC. Let A B be a partition of V (G * ) such that |A| = |B| and both G * [A] and G * [B] are connected, and such that the weight of the edges between A and B is minimized among all such partitions. For 1 ≤ i ≤ t, we let

Cut, any bipartition of V i cuts at most p-1 edges. Therefore, the total weight of the edges between (V i ∪V i )∩A and

Since t is odd, necessarily at least one of the graphs G i is cut by A B. Assume first that exactly one graph G i is cut by A B. Since |A| = |B|, we have that a i = n, so the value of the cut is at least

We claim that there is always exactly one graph G i cut by A B. Assume for contradiction that it is not the case, that is, that there are two strictly positive values a i , a j for some i = j. By symmetry between A and B, we may assume that a i +a j ≤ 2n. The total weight of the edges cut in

Hence |M | = m and M must be a matching covering W .

In order to understand to which extent the vertices of high degree make the complexity of computing the restricted edge-connectivity of a graph hard, we also consider the maximum degree of the input graph as a parameter for the p-REC problem.

Theorem 8. The p-REC problem is FPT when parameterized by k and the maximum degree ∆ of the input graph.

Proof: The algorithm is based on a simple exhaustive search. We use the property that, for any graph G and any two integers k, , λ k (G) ≤ if and only if G contains two vertex-disjoint trees T 1 and T 2 with |V (T 1 )| ≥ k and |V (T 2 )| ≥ k, such that there exists an edge set S in G with |S| ≤ such that in G -S the trees T 1 and T 2 belong to different connected components. Hence, we just have to determine whether these trees exist in G or not. For doing so, for every pair of distinct vertices v 1 and v 2 of G, we exhaustively consider all trees T 1 and T 2 with k vertices containing v 1 and v 2 , respectively. Note that the number of such trees is at most ∆ 2k . For every pair of vertex-disjoint trees T 1 and T 2 , we proceed as follows. We contract tree T 1 (resp. T 2 ) to a single vertex t 1 (resp. t 2 ), keeping edge multiplicities, and then we run in the resulting graph a polynomial-time Minimum Cut algorithm between t 1 and t 2 (cf. [START_REF] Stoer | A simple min-cut algorithm[END_REF]). If the size of the returned edge-cut is at most , then T 1 and T 2 are the desired trees. Otherwise, we continue searching. It is clear that the overall running time of this algorithm is O(∆ 2k • n O (1) ).


Ugo Boscain

Mario Sigalotti

Introduction to controllability of non-linear systems

We present some basic facts about the controllability of nonlinear finite dimensional systems. We introduce the concepts of Lie bracket and of Lie algebra generated by a family of vector fields. We then prove the Krener theorem on local accessibility and the Chow-Rashevskii theorem on controllability of symmetric systems. We then introduce the theory of compatible vector fields and we apply it to study control-affine systems with a recurrent drift or satisfying the strong Lie bracket generating assumption. We conclude with a general discussion about the orbit theorem by Sussmann and Nagano.

In this note we present some classical techniques to study the controllability of nonlinear systems. The discussion is kept as elementary as possible. Classical textbooks are [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF][START_REF] Jean | Control of nonholonomic systems: from sub-Riemannian geometry to motion planning[END_REF][START_REF] Jurdjevic | Geometric control theory[END_REF].

Consider the nonlinear control system ẋ = F (x, u(t)).

(1)

Here x ∈ R n is the state of the system and u(•) : [0, ∞[→ U ⊂ R m is the control. We assume that F is a smooth1 function of its arguments and that u(•) is regular enough in such a way that equation [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF] with the initial condition x(0) = x 0 ∈ R n has local existence and uniqueness of solutions. For instance we can assume that u(•) is a L 1 loc or a L ∞ loc function of the time. However, as it will be clear later, all conditions for controllability that we will get are actually sufficient conditions that are valid in the smaller class of piecewise constant controls.

Remark 1. For simplicity of notation in the following we also assume that for every u(•) a solution of (1) exists in [0, ∞[. However this hypothesis is not necessary for the validity of the theorems that we are going to prove. Remark 2. In the discussion presented here we assume x ∈ R n . However almost nothing changes if we assume that x belongs to a smooth connected manifold M and that solutions of (1) exists in [0, ∞[. To extend the theory to smooth connected manifolds, if some non-trivial modification is necessary, we explicitly state it in the text.

Denote by x(t; x 0 , u(•)) the solution at time t of (1) starting from x 0 at t = 0 and corresponding to a control function u(•). We recall the definitions of the reachable (or attainable) sets starting from x 0 :

• the reachable set from x 0 at time τ ≥ 0 is

A(τ, x 0 ) = {x 1 ∈ R n | ∃ u(•) : [0, τ ] → U, x(τ ; x 0 , u(•)) = x 1 };
• the reachable set from x 0 within time τ ≥ 0 is A(≤ τ, x 0 ) = ∪ t∈[0,τ ] A(t, x 0 );

• the reachable set from x 0 is A(x 0 ) = ∪ t∈[0,+∞[ A(t, x 0 ). Given the control system [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF], the purpose of the controllability theory is to characterize when these sets coincide with the entire state space. Definition 3. The system (1) is said to be

• controllable if for every x 0 ∈ R n , A(x 0 ) = R n ;
• small-time controllable if for every x 0 ∈ R n and τ > 0, we have A(≤ τ, x 0 ) = R n ;

• small-time locally controllable at x 0 if x 0 belongs to the interior of A(≤ τ, x 0 ) for every τ > 0.

1 Control systems as families of vector fields

In the following it will be useful to think to the system (1) as a family of vector fields2 parameterized by u ∈ U (i.e., by constant controls). In other words we will often consider instead of the control system (1), the family of vector fields

F = {F (•, v) | v ∈ U}.
All vector fields of the family F are considered smooth and complete, i.e., for every F ∈ F , x 0 ∈ R n , the equation ẋ = F (x) with initial condition x(0) = x 0 admits a solution in ]-∞, ∞[.

Vec(R n ) and its Lie algebra

Let Vec(R n ) be the vector space of all smooth vector fields in R n . Given a compete vector field f ∈Vec(R n ), let us indicate by e tf its flow, i.e., the map that with x 0 associates the solution at time t to the Cauchy problem

ẋ = f (x) x(0) = x 0 . (2)
Although e tf is not an exponential in the usual sense, this notation is useful thanks to the following properties that are a direct consequence of existence and uniqueness of solutions of (2) and of their differentiability w.r.t. x 0 :

• for every t, s ∈ R, e (t+s)f = e tf • e sf ;

• for every t ∈ R, e tf is a diffeomorphism. In particular, it is invertible and we have (e tf ) -1 = e -tf ;

• for every t ∈ R, d dt e tf (x) = f (e tf x). In particular, d dt t=0 e tf (x) = f (x). A crucial object in studying the controllability of (1) is the Lie algebra generated by the vector fields of the corresponding family F . Let us first define the Lie bracket between two vector fields f and g, as the vector field defined by

[f, g](x) = Dg(x)f (x) -Df (x)g(x). (3)
Here, given a vector field f = (f 1 , . . . , f n ) T , Df is the matrix of partial derivatives of the components of f , i.e.,

Df =    ∂ 1 f 1 . . . ∂ n f 1 . . . . . . . . . ∂ 1 f n . . . ∂ n f n    .
One immediately verifies the following properties of the Lie bracket:

• bilinearity: for every λ 1 , λ 2 ∈ R, [f, λ 1 g 1 + λ 2 g 2 ] = λ 1 [f, g 1 ] + λ 2 [f, g 2 ], [λ 1 f 1 + λ 2 f 2 , g] = λ 1 [f 1 , g] + λ 2 [f 2 , g]; • antisymmetry: [g, f ] = -[f, g]; • Jacobi identity: [f, [g, h]] + [h, [f, g]] + [g, [h, f ]] = 0.
A vector space V endowed with an operation V × V → V that is bilinear, antisymmetric and satisfying the Jacoby identity is said to be a Lie algebra.

It follows that (Vec(R n ), [•, •]) is a Lie algebra.
Remark 4. As a consequence of the antisymmetry of the Lie bracket, we have [f, f ] = 0. Notice moreover that the value of [f, g] at a point x does not depend only on the values of f and g at x, but also on their first order expansion at x. However, if at x 0 we have f (x 0 ) = g(x 0 ) = 0, it follows from the definition that [f, g](x 0 ) = 0.

Example 5. Given two linear vector fields Ax and Bx, where A, B ∈ R n×n , we have that

[Ax, Bx] = BAx -ABx = -[A, B]x.
The following lemma clarifies the geometric meaning of the Lie bracket: [f, g] is a measure of the lack of commutation of the flows associated with f and g. We refer to Figure 1.

e tf x x + t 2 [f, g](x) + o(t 2 )
e tg e -tf e -tg Lemma 6. For every

x ∈ R n , e -tg • e -tf • e tg • e tf (x) = x + t 2 [f, g](x) + O(t 3 ), ( 4
)
for t that tends to zero.

Proof. It is enough to compute for each flow the Taylor expansion at order 3. We have

e tf (x) = x + tf (x) + t 2 2 Df (x)f (x) + O(t 3 ), and
e tg • e tf (x) = x + t f (x) + g(x) + t 2 2 Df (x)f (x) + t 2 Dg(x)f (x) + t 2 2 Dg(x)g(x) + O(t 3 ).
Then

e -tf • e tg • e tf (x) = x + tg(x) + [f, g](x)t 2 + t 2 2 Dg(x)g(x) + O(t 3 ).
At the next step the result follows.

Remark 7. The previous lemma says in particular that if [f, g](x) ∈ Vect(f (x), g(x)), then it is possible, by alternating between the dynamics of f and g, to attain points that cannot be reached with the flow of linear combinations of f and g. This is the starting idea behind the conditions for controllability that we are going to study in this note. Notice however that in order to generate the Lie bracket [f, g], one needs to be able to use, beside f and g, also -f and -g, otherwise one is much more constrained in the possible movements. As a consequence, it will be easier to prove controllability results for symmetric systems (i.e., systems for which if f ∈ F then -f ∈ F ). See Section 3.

An important corollary of the previous lemma is the following.

Corollary 8. The flows e tf and e tg (corresponding to the vector fields f and g) commute for every t ∈ R if and only if their Lie bracket [f, g](x) = 0 for every x ∈ R n .

Proof. The fact that commutation of the flows implies that the Lie bracket vanishes follows immediately from (4). Concerning the converse implication, let us consider the curve

γ(s) = e -√ sg • e -√ sf • e √ sg • e √ sf (x).
By Lemma 6, we have that γ is differentiable at each time s and

dγ ds = [f, g](γ(s)).
If [f, g] is identically equal to zero, γ turns out to be solution of

dγ ds = 0, γ(0) = 0.
It follows γ(s) = 0 for every s and e

√ sg • e √ sf = e √ sg • e √ sf . Setting t = √ s the result follows.
Remark 9. In a differentiable manifold, Definition 3 and formula (4) make sense only in coordinates. An intrinsic definition of Lie bracket is

[f, g](x) = d ds s=0 e -√ sg • e -√ sf • e √ sg • e √ sf (x).
Definition 10. Let F be a family of vector fields. We call Lie(F ) the smallest sub-algebra of Vec(R n ) containing F . Namely, Lie(F ) is the span of all vector fields of F and of their iterated Lie brackets of any order:

Lie(F ) = span{f 1 , [f 1 , f 2 ], [f 1 , [f 2 , f 3 ]], [f 1 , [f 2 , [f 3 , f 4 ]]], . . . | f 1 , f 2 , . . . ∈ F }.
Definition 11. We say that the family F is Lie bracket generating at a point

x if the dimen- sion of Lie x (F ) := {f (x) | f ∈ Lie(F )} is equal to n.
We say that the family F is Lie bracket generating if this condition is verified for every x ∈ R n .

Remark 12. Notice that in general Lie(F ) is an infinite-dimensional space, while Lie x (F ) is a subspace of R n .

Exercise 1. Let F = {f 1 , . . . , f m } and let A be an invertible m × m matrix. Define

f ′ i = j A ij f j and F ′ = {f ′ 1 , . . . , f ′ m }.
Prove that F is Lie bracket generating if and only if F ′ is.

Affine control systems

An affine control system is a system of the form

ẋ = f 0 (x) + m i=1 u i (t)f i (x), (5)
where

f 0 , f 1 , . . . , f m belong to Vec(R n ) and u(•) = (u 1 (•), . . . , u m (•)) : [0, ∞[→ U ⊂ R m is the control.
In an affine control system it is also assumed that U contains a neighborhood of the origin in R m . The vector fields f 0 is called the drift.

Exercise 2. Let F be the family of vector fields associated with (5).

• Prove that if {f 0 , f 1 , . . . , f m } is Lie bracket generating then also F is.

• Prove that if {f 1 , . . . , f m } is Lie bracket generating then also F is.

x 0 admissible non admissible

x 0 x 0 x 0 Figure 2: admissible and non-admissible reachable sets when the system is Lie bracket generating at x 0 .

The Krener Theorem: local accessibility

The fact that a control system is Lie bracket generating does not permit in general to conclude that it is controllable. Consider for instance the control system on the plane

ẋ1 ẋ2 = 1 0 + u(t) 0 1 , where u(•) : [0, ∞[→ [-1, 1]
. It is Lie bracket generating (since the corresponding family F contains the vector fields {(1, 1), (1, -1)}, however starting from the origin one cannot reach any point whose first coordinate is negative. This is essentially due to the fact that the family F contains two vector fields but not their opposite (cf. Remark 7). The Lie bracket generating condition permits to say that a system is locally accessible in the following sense.

Theorem 13 (Krener). If F is Lie bracket generating at x 0 , then for every τ > 0, x 0 belongs to the closure of the interior of A(≤ τ, x 0 ).

The conclusion of the Krener Theorem can be equivalently reformulated in the following way:

• for every τ > 0, the set A(≤ τ, x 0 ) has nonempty interior,

• x 0 is a density point of such an interior. Krener's theorem says in particular that the trajectories starting from a point at which the system is Lie bracket generating can reach (in an arbitrarily small time) a set having nonempty interior. Figure 2 shows what one can expect/non-expect from A(≤ τ, x 0 ), τ > 0.

Proof of Theorem 13. First notice that if F is Lie bracket generating at a point, then the same property holds true in a neighborhood of that point. (If n vector fields are linearly independent at a point, then they are linearly independent in a neighborhood of that point.)

There exists f ∈ F such that f (x 0 ) = 0, otherwise Lie x 0 (F ) = {0}. If n = 1 the conclusion follows.

If n > 1 and all vector fields of F are tangent to the curve t → e tf (x 0 ), 0 < t < ε, then from Lemma 6 it follows that Lie e tf (x 0 ) (F ) is also tangent to that curve and hence its dimension is less than 2. This contradicts the Lie bracket generating assumption. As a consequence, there exist g ∈ F and 0 < t < ε such that f and g are linearly independent in a neighborhood of x 1 = e tf (x 0 ) (see Figure 3). Hence (t, s) → e sg • e tf (x 0 ), 0 < s < ε ′ , tε ′ < t < t + ε ′ has as image a surface of dimension 2. If n = 2 the conlcusion follows.

Otherwise we iterate the same argument and we conclude by recurrence on n.

Remark 14. Notice that for this proof we have only used piecewise constant controls.

Remark 15. From the proof of the Krener theorem it follows that A(≤ τ, x 0 ), τ > 0, contains an open set Ω having x 0 in its closure whose points can be reached by trajectories of the type e tnf in • . . . • e t 1 f i 1 x 0 where t 1 , . . . , t n > 0 and f i 1 , . . . , f in ∈ F , i.e., by trajectories corresponding to piecewise constant controls made by n pieces. Notice that the vector fields f i 1 , . . . , f in could be repeated. For instance if F = {f 1 , f 2 } is a Lie bracket generating family and we are in dimension 3, we could have for instance

f i 1 = f 1 , f i 2 = f 2 , f i 3 = f 1 .
3 Symmetric systems Definition 16. A family of vector fields F is said to be symmetric if f ∈ F implies -f ∈ F .

When the family F is Lie bracket generating and symmetric one obtain that the system is controllable. This is the conclusion of the celebrated Chow-Rashevskii theorem.

Theorem 17 (Chow-Rashevskii). If F is Lie bracket generating and symmetric, then for every x 0 ∈ R n we have A(x 0 ) = R n . Proof. Step 1. Fix x 0 ∈ R n and let us show that A(x 0 ) contains a neighborhood of x 0 . Since F is Lie bracket generating, A(x 0 ) contains a nonempty open set Ω whose points can be reached by trajectories corresponding to piecewise controls made by n pieces. Fix t 1 , . . . , t n > 0 and

f i 1 , . . . , f in ∈ F such that x0 := e tnf in • . . . • e t 1 f i 1 x 0 ∈ Ω. Since F is symmetric, -f i 1 , . . . , -f in ∈ F and we have that e -t 1 f i 1 • . . . • e -tnf in (A(x 0 )) ⊂ A(x 0 ).
In particular A(x 0 ) contains the set

V = e -t 1 f i 1 • . . . • e -tnf in (Ω).

Now, since Ω is open and e

-t 1 f i 1 • . . . • e -tnf in is a diffeomorphism, we have that V is open. Moreover V contains x 0 since x0 ∈ Ω and e -t 1 f i 1 • . . . • e -tnf in x0 = x 0 .
It follows that, for every x 0 , A(x 0 ) contains a neighborhood of x 0 .

Step 2. Let us show that A(x 0 ) is open. If x 1 ∈ A(x 0 ), then A(x 1 ) ⊂ A(x 0 ). It follows that int(A(x 1 )) ⊂ int(A(x 0 )). But from Step 1 we have that x 1 ∈ int(A(x 1 )). Hence x 1 ∈ int(A(x 0 )).

Step 3. From the fact that F is symmetric, it follows that x 1 ∈ A(x 0 ) if and only if x 0 ∈ A(x 1 ). Let us consider the equivalence classes R n / ∼ where ∼ is the equivalence relation

x 1 ∼ x 0 if and only if x 1 ∈ A(x 0 ).
Such equivalence classes are open and disjoint. Since R n is connected, it follows that there is only one class. Hence, for every x 0 we have A(x 0 ) = R n .

Remark 18. Notice that in Step 1 of the proof of Chow-Rashevskii theorem, since the times can be rendered arbitrarily small, we have proved that the system is small-time locally controllable in a neighborhood of every point x 0 . Also, we have proved that every point of a neighborhood of x 0 can be reached with trajectories made by 2n pieces.

Remark 19. Notice that the Chow-Rashevskii theorem can be used in more general situations than those fixed by the hypotheses stated here. For instance

• to get controllability it is sufficient that the family F contains a symmetric family of Lie bracket generating vector fields;

• if one can prove that F is symmetric and Lie bracket generating in a connected open set U of R n then one get the system is controllable in U.

Compatible vector fields

When a family of vector fields is Lie bracket generating but is not symmetric, in general it is not easy to understand if the system is controllable or not. A technique to study the controllability is the one of compatible vector fields.

Definition 20. A vector field g is said to be compatible with the family F if defining F = F ∪ {g} we have the following: For every x 0 ∈ R n , the reachable set Â(x 0 ) of F is contained in the closure of A(x 0 ).

The main result of the theory of compatible vector fields is the following.

Theorem 21. If F is a Lie bracket generating family of vector fields, g is compatible with F and F ∪ {g} is controllable, then F is controllable as well.

This theorem should be used in the following way: one looks for a vector field g that added to the family F do not change the closure of the reachable set and such that it is easy to prove the controllability of the family F ∪ {g}.

The main ingredient to prove Theorem 21 is the following corollary of the Krener theorem.

Corollary 22. If F is Lie bracket generating and A(x 0 ) is dense in R n for some x 0 , then A(x 0 ) = R n .

x 0

A -(x 1 )

x 1

x A(x 0 ) Proof. Let x 1 ∈ R n and consider the system

ẋ = -F (x, u(t)), x ∈ R n , u(•) : [0, ∞[→ U ⊂ R m , (6)
which is obtained from (1) by reversing the time. Let F -be the family of vector fields associated with (6). Since F is Lie bracket generating, then F -is Lie bracket generating as well.

Let A -(x 1 ) be the reachable set for (6) starting from x 1 . Thanks to Krener's theorem, A -(x 1 ) contains a nonempty open set. In particular it has nonempty intersection with A(x 0 ) (being A(x 0 ) dense). See Figure 4.

This means that x 1 ∈ A(x 0 ). Indeed from x 0 one can reach a point x ∈ A(x 0 ) ∩ A -(x 1 ) (since x ∈ A(x 0 )) and from x one can reach x 1 (since x is reachable from x 1 for the system with reverted time).

Being x 1 arbitrary we have that A(x 0 ) = R n .

Proof of Theorem 21. Let A(x 0 ) be the reachable set from x 0 associated with F and Â(x 0 ) be the reachable set from x 0 associated with F ∪ {g}. For every x 0 ∈ R n we have R n = Â(x 0 ) ⊂ Ā(x 0 ). Hence A(x 0 ) is dense. Since the system is Lie bracket generating, from Corollary 22 the conclusion follows.

Next we present some important applications of the technique based on compatible vector fields.

Affine systems with recurrent drift

In this section we apply the theory of compatible vector fields to affine control systems (cf. Section 1.2) that are Lie bracket generating and having a drift f 0 which is weakly recurrent 3 .

Definition 24 (Weakly recurrent vector field). A vector field f is said to be weakly recurrent if for every point x 0 ∈ R n , every neighborhood V of x 0 and every time t > 0, there exist x0 ∈ V and t * > t such that e t * f (x 0 ) ∈ V . Notice that if the trajectories of f are periodic (possibly with period depending on the trajectory), then f is recurrent.

Lemma 25. Let F be a Lie bracket generating family of vector fields and f ∈ F . If f is weakly recurrent then -f is compatible with F .

Proof. We have to prove that for every x 0 and for every t > 0, e -tf x 0 can be obtained as limit of points belonging to the reachable set A(x 0 ).

By Krener theorem (thanks to the fact that F is Lie-bracket generating), there exists an arbitrarily small open set W ⊂ A(x 0 ) such that x 0 ∈ W .

Now since e -tf is a diffeomorphism this implies that e -tf x 0 ∈ e -tf W . Since f is weakly recurrent, there exists t * > t such that

e t * f e -tf W ∩ e -tf W = ∅,
or equivalently e (t * -t)f W ∩ e -tf W = ∅.

But since t *t > 0 and W ⊂ A(x 0 ) we have that e (t * -t)f W ⊂ A(x 0 ). It follows that

A(x 0 ) ∩ e -tf W = ∅.
Hence in any neighborhood of e -tf x 0 there are points of A(x 0 ). In other words e -tf x 0 ∈ A(x 0 ).

3 the term weakly recurrent comes from the fact that our definition is a bit more general than the classical definition of recurrent vector field: Definition 23 (Recurrent vector field). A vector field f is said to be recurrent if for every point x 0 ∈ R n , every neighborhood V of x 0 and every time t > 0, there exists t * > t such that e t * f (x 0 ) ∈ V .

integral curve of $f$ W e -tf W e -tf x 0 e t * f e -tf W ⊂ A(x 0 )

x 0 As a consequence of the previous lemma we have the following.

Corollary 26. Consider the control system

ẋ = f 0 (x) + m i=1 u i (t)f i (x), (u 1 (•), . . . , u m (•)) : [0, ∞[→ U ⊂ R m . ( 7
)
Assume that (i) 0 belongs to the interior of U, (ii) the control system (7) is Lie bracket generating, (iii) f 0 is weakly recurrent. Then the system is controllable.

Proof. Notice that f 0 ∈ F since 0 belongs to U. Lemma 25 states the equivalence between the controllability of (7) and that of

ẋ = m i=0 u i (t)f i (x), (u 0 (•), . . . , u m (•)) : [0, ∞[→ {-1, 1} × U.
The controllability of this system follows from the Chow-Rashevskii theorem since {-1, 1}×U contains a symmetric set (Remark 19).

Example (on a manifold). Consider the control system on the sphere

S 2 = {x ∈ R 3 | x 2 1 + x 2 2 + x 2 3 = 1} given by ẋ = f 0 (x) + uf 1 (x), u(•) : [0, ∞[→ (-1, 1), x ∈ S 2 ,
where

f 0 (x) =   -x 2 x 1 0   , f 1 (x) =   0 -x 3 x 2   .
The flows of f 0 and f 1 are rotations around the axes (0, 0, 1) T and (1, 0, 0) T , respectively. This system is controllable since

• the Lie bracket between f 0 and f 1 is given by

[f 0 , f 1 ](x) =   -x 3 0 x 1   ,
and hence the system is Lie bracket generating (for every x ∈ S 2 , dim(span{f 0 , f 1 , f 2 }(x) = 2);

• the trajectories of f 0 are periodic and hence f 0 is recurrent.

Affine systems with non-recurrent drift

When the drift is not recurrent one can still obtain that the system is controllable if the controls are unbounded and if it is not necessary to use the drift to get a Lie algebra of full dimension at every point. More precisely we have the following.

Proposition 27 (Strong bracket generating). Consider the control system

ẋ = f 0 (x) + m i=1 u i f i (x), (u 1 (•), . . . , u m (•)) : [0, ∞[→ R m . (8)
If {f 1 , . . . , f m } is Lie bracket generating then (8) is controllable.

Remark 28. For an affine control system as (8), the condition that {f 1 , . . . , f m } is Lie bracket generating is called the strong bracket generating condition.

Proof. First notice that as a consequence of Exercise 2, being {f 1 , . . . , f m } Lie bracket generating, then (8) is Lie bracket generating as well. Let F be the family of vector fields associated with (8). In the following we are going to prove that for every (v 1 , . . . , v m ) ∈ R m the vector field m i=1 v i f i is compatible with F . Once this is done, the controllability of (8) follows, since the family F ∪ { m i=1 v i f i , v i ∈ R, i = 1, . . . , m} contains a symmetric and Lie bracket generating sub-family (Remark 19).

To show that m i=1 v i f i is compatible with F for every v 1 , . . . , v m ∈ R, remark that

m i=1 v i f i = lim n→∞ 1 n f 0 + m i=1 (nv i )f i (9)
and that 1 n (f 0 + m i=1 (nv i )f i ) is compatible with F since a trajectory of (8) corresponding to controls ũi (•), i = 1, . . . , m, is a time-reparameterisation of a trajectory of

ẋ = 1 n f 0 (x) + m i=1 u i f i (x)
corresponding to controls nũ i (•), i = 1, . . . , m.

The thesis follows from the fact that if a vector field is the uniform limit on all compacts of a sequence of compatible vector fields, then it is compatible as well (from the continuity of solutions of ODEs with respect to the vector field).

Theorem 34 (Orbit theorem). For every x 0 ∈ R n , the set O(x 0 ) has the structure of an immersed sub-manifold of R n . In particular it has the same dimension at every point. Moreover if x ∈ O(x 0 ) then Lie x (F ) ⊆ T x O(x 0 ). The two spaces Lie x (F ) and T x O(x 0 ) coincide if one of the following two conditions is verified:

• every element of F is an analytic vector field;

• the dimension of Lie x (F ) is constant with respect to x ∈ O(x 0 ).

From the fact that Lie x (F ) ⊆ T x O(x 0 ) it follows that every element of F is tangent to O(x 0 ). As a consequence we have the following.

Lemma 35. For every x 0 ∈ R n we have that A(x 0 ) ⊂ O(x 0 ). This result wouldn't be so obvious without the orbit theorem since A(x 0 ) is the set of points that one can reach using L ∞ controls (and not only piecewise constant ones).

The following corollary gives some consequence of the Orbit theorem on the controllability of nonlinear systems.

Corollary 36. If F is not Lie bracket generating and either every vector field of F is analytic or the dimension of Lie x (F ) is constant with respect to x ∈ O(x 0 ), then F is not controllable.

Figure 1 :

 1 Figure 1: geometric meaning of the Lie bracket.

x 0 x 1 e tf x 0 e sg x 1 Figure 3 :

 1013 Figure 3: Proof of Krener Theorem

Figure 4 :

 4 Figure 4: Proof of Corollary 22

in this note by smooth we mean C ∞

In an autonomous differential equation ẋ = f (x), usually f it is called a vector field, since it is a map that with every position x associates a velocity vector f (x).

Acknowledgements: This work was supported by the ERC POC project ARTIV1 contract number 727283, by the ANR project "SRGI" ANR-15-CE40-0018, by the ANR project "Quaco" ANR-17-CE40-0007-01 and by a public grant as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH (in a joint call with Programme Gaspard Monge en Optimisation et Recherche Opérationnelle).

Convexification

A very useful criterium is the one that states that a convex combination of vector fields of F is compatible with F . It formalize the intuition that if one commutes quickly between the dynamics of two vector fields, and one stays the same time on each dynamics, then the corresponding trajectory is close the trajectory of f +g 2 starting from the same point. Lemma 29. For every λ 1 , . . . , λ k ≥ 0 and f 1 , . . . , f k ∈ F , the vector field

The proof of this Lemma is quite technical and it is based on the Gronwall inequality. See [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF] for details.

From this lemma one can gets some useful corollaries of Theorem 17, Corollary 26, and Proposition 32.

Corollary 30. If F is Lie bracket generating and its convex hull in the space Vec(R n ) is symmetric, then for every

Corollary 31. Consider the control system

Assume that (i) 0 belongs to the interior of the convex hull of U, (ii) the control system (10) is Lie bracket generating, (iii) f 0 is weakly recurrent. Then the system is controllable.

Corollary 32. Consider the control system

If the convex hull of U is R m and if {f 1 , . . . , f m } is Lie bracket generating then (11) is controllable.

Orbits and necessary conditions for controllability

We have seen in the previous sections several sufficient conditions for the controllability of a nonlinear system. In this section we discuss some necessary conditions that are consequence of a very deep theorem of geometric nature, the so-called orbit theorem. This theorem permits to conclude that, beside pathological cases, Lie x (F ) measures precisely the dimension of the set of directions that can be used starting from a point. We define the orbit of the family F starting from a point x 0 ∈ R n as the set

Remark 33. O(x 0 ) can be interpreted as the reachable set, starting from x 0 , of the family -F ∪ F , using only piecewise constant controls.

We have the following result