Professor Mohamed Didi-Biha

Professor Evripidis BAMPIS Eric Angel

Pro- Fessor Sourour

Doctor Lucas Letocart

Eric Gourdin

Professor Walid José Neto

Sim Drida

Mazen Al Maarabani

Farouk Aissanou

Khlifa Tomy

Fayeçal Bessayah

Makhlouf Hadji

Mohamed-Haykel Zayani

Mrs Thanks

M A Valérie

Keywords: Graph partitioning, Complexity theory, Optimization, Approximation algorithms, Vertex separators, Polyhedral approach, Polynomial-time algorithms, Integer programming [90] . . . . . . . . . . . . .

Given a vertex-weighted undirected graph G = (V, E, w) and a positive integer k, we consider the k-separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to k. If k = 1 we get the classical vertex cover problem. The case k = 2 is equivalent to computing the dissociation number of a graph (in the case of unit weights). We prove that this problem can be solved in polynomial time for some graph classes including bounded treewidth, mK 2 -free, (G 1 , G 2 , G 3 , P 6 )free, interval-filament, asteroidal triple-free, weakly chordal, interval and circulararc graphs. Different formulations are presented and compared. Polyhedral results with respect to the convex hull of the incidence vectors of k-separators are reported.

Numerical results are reported and approximation algorithms are also presented.

Résumé

Soit G un graphe non orienté dont les sommets sont pondérés. Nous cherchons à calculer un sous-ensemble de sommets de poids minimal dont la suppression nous donne un graphe où la taille de chaque composante connexe est inférieure ou égale à un entier positif donné k. Ce problème est denommé Problème de k-Séparateur et le sous-ensemble recherché, k-Séparateur. Le problème de k-Séparateur a de nombreuses applications. Si les poids des sommets sont tous égaux à 1, la taille d'un k-séparateur peut être utilisée pour évaluer la robustesse d'un graphe ou d'un réseau. On peut citer d'autres applications du problème de k-Séparateur tel que : partitionnement de graphe et décompositions de matrice de contraintes etc ...

List of Figures

General Context

Given a vertex-weighted undirected graph G = (V, E, w), the minimum vertex cover problem consists in computing a minimum-weight set of vertices S ⊂ V such that V \ S is a stable set. A minimum-weight vertex cover can then be exhibited if one can find a maximum-weight stable set. While the problem can be solved in polynomial time in some cases (bipartite graphs, perfect graphs, etc.), it is known to be generally NP-hard (see, e.g., [4,[START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]). Many valid inequalities are known for the vertex cover problem and the stable set problem. A 2-approximation algorithm for the vertex cover problem is given by a simple greedy algorithm (see, e.g., [4]).

Let k be a positive number, we consider the following natural generalization of the vertex cover problem. We want to compute a minimum-weight subset of vertices S whose removal leads to a graph where the size of each connected component is less than or equal to k. Let us call such as set a k-separator. If k = 1 we get 1.1. General Context the classical vertex cover problem. The case k = 2 is equivalent to compute the dissociation number of a graph (in the case of unit weights) [START_REF] Yannakakis | Node-deletion problems on bipartite graphs[END_REF]. This problem is NP-hard even if the graph is bipartite.

The k-separator problem has many applications. If vertex weights are equal to 1, the size of a minimum k-separator can be used to assess the robustness of a graph or a network. Intuitively, a graph for which the size of the minimum kseparator is large, is more robust. Unlike the classical robustness measure given by the connectivity, the new one seems to avoid the underestimate of robustness when there are only some local weaknesses in the graph. Consider for example a graph containing a complete subgraph and a vertex connected to exactly one vertex of the subgraph. Then the vertex-connectivity of this graph is 1 while the graph seems to be robust everywhere except in the neighborhood of one vertex. The size of a minimum k-separator of this graph is |V | -1k.

The minimum k-separator problem has some other network applications. A classical problem consists in partitioning a graph/network into different subgraphs with respect to different criteria. For example, in the context of social networks, many approaches are proposed to detect communities. By solving a minimum k-separator problem, we get different connected components that may represent communities.

The k-separator vertices represent people making connections between communities.

The k-separator problem can then be seen as a special partitioning/clustering graph problem.

Computing a k-separator can also be useful to build algorithms based on divideand-conquer approaches. In some cases, a problem defined on a graph can be decomposed into many subproblems on smaller subgraphs obtained by the deletion of a k-separator (see, .e.g., [START_REF] Shmoys | Cut problems and their application to divide-and-conquer[END_REF]).

The k-separator problem is closely related to the vertex-separator problem where we aim to remove a minimum-weight set of vertices such that every connected component in the remaining graph has a size less than α|V | (for a fixed α < 1). A polyhedral study of this problem is proposed in [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] (see also the references therein).

When the vertex-separator problem is considered, the graph is generally partitioned into 3 subgraphs: the separator, and two subgraphs each of size less than α|V |. The philosophy is different in the case of the k-separator where the graph is partitioned into many components each one having a size less than k.

The k-separator problem was considered in one published paper [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] where it was Chapter 1. Introduction presented as a problem of disconnecting graphs by removing vertices. An extended formulation is proposed in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] with some polyhedral results. Some other applications were also mentioned in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. This includes a constraint matrix decomposition where each row A i of a matrix A is represented by a vertex v i and two vertices v i and v j are adjacent if there is at least one column h with nonzero coefficients in the corresponding two rows (a ih = 0 and a jh = 0). The problem is to assign as many rows as possible to the so-called blocks such that no more than k rows are assigned to the same block, and rows assigned to different blocks are not connected (i.e., there is no any column h such that a ih a jh = 0 if A i and A j are in different blocks) [START_REF] Borndörfer | Decomposing matrices into blocks[END_REF]. This matrix decomposition may help the solution process of linear or integer programs where the constraint matrix is defined by A.

Another application is related to the field of group technology (see [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] for details).

Notation

Given an undirected graph G = (V, E) and a vertex subset U ⊂ V , the complement of U in G, i.e. the vertex set V \ U is denoted U . The set of vertices (resp. edges)

of the graph G may also be denoted by V (G) (resp. E(G)). An edge e ∈ E with endnodes u and v is denoted by (u, v). For a vertex-weighted undirected graph G = (V, E, w), w v denotes the weight of the vertex v ∈ V .

Given a vertex subset S ⊂ V , the set of vertices in S that are adjacent to at least one vertex in S is denoted N (S). N S (k) denotes the set of neighbors of a vertex k in subset S. Given two subsets of vertices A and B, A and B are adjacent if either

A ∩ B = ∅ or N (A) ∩ B = ∅.
Given a subset of vertices S ⊂ V , χ (S) ∈ {0, 1} n denotes the incidence vector of S, with n = |V |. The convex hull of all the incidence vectors of k-separators in the graph G is indicated by S k (G). We also use G(S) to refer to the subgraph of G that is induced by a subset of vertices S ⊂ V .

The order of a graph indicates its number of vertices. K n denotes a complete graph with order n. Given some integer m, mK 2 denotes a matching with m edges.

If p and q ≤ p are two positive integer, then

p q = p! q!(p-q)!
If the graph G does not contain an induced subgraph isomorphic to some given graph H, then we say that G is H-free.

Thesis plan

If G is a simple path with vertex set {v 1 , . . . , v n } and edge set {(v i , v i+1 ) : i = 1, . . . , n -1}, then the notation [v i , v j ] (resp. ]v i , v j [, [v i , v j [, ]v i , v j ]) with i < j, i, j ∈ {1, . . . , n} stands for the vertex set {v i , v i+1 , . . . , v j } (resp. {v i+1 , . . . , v j-1 }, {v i , v i+1 , . . . , v j-1 }, {v i+1 , . . . , v j }). The set of all the simple paths joining i and j will be denoted P ij . Given a simple path p joining i and j, x(p) stands for the sum of the x v values over all vertices belonging to p (including i and j). Let N denote the set of natural numbers.

Thesis plan

This thesis is organized as follows:

1. In chapter 2, we present the state of the art, precisely related works and the used technics.

2. In chapter 3, some cases where the problem can be solved in polynomial time are shown.

3. In chapter 4, we describe integer programming formulations of the k-separator problem. The linear relaxations of these formulations are also compared when this is possible. 4. A polyhedral study of the convex hull of the incidence vectors of k-separators is proposed in chapter 5.

5. Some numerical experiments follow in chapter 6.

6. In chapter 7, we present some approximation algorithms.

7. The final chapter of this thesis concludes our work. We summarize our contributions and present some perspectives and possible future directions to extend our work.

Chapter 2

Related work

Introduction

Combinatorial optimization is a well-known field of applied mathematics, combining techniques from combinatorics, linear programming, and the theory of algorithms, to solve optimization problems over discrete structures [START_REF] Pulleyblank | Combinatorial optimization[END_REF]. One of the most studied problems in combinatorial optimization is the vertex cover problem [START_REF] Cook | The complexity of theorem proving procedures[END_REF]. For a decade there has been an increasing interest to generalize this issue to another one [START_REF] Gambardella | Metaheuristics in stochastic combinatorial optimization : a survey[END_REF]. This chapter provides some state of art techniques used to solve some classical optimization problems that have a relation with the k-separator problem [START_REF] Neto | The k-separator problem[END_REF][START_REF] Neto | The k -separator problem: polyhedra, complexity and approximation results[END_REF].

It demonstrates also some related works to our thesis main problem, i.e. k-separator problem. This chapter is organized as follows : In section 2.2 we introduce many classical combinatorial optimization problems close to the k-separator problem [START_REF] Neto | The k -separator problem: polyhedra, complexity and approximation results[END_REF].

In section 2.3 we mention the techniques used in this thesis. For the sake of clarity we present disconnecting graphs and vertex separator problems in section 2.4 after we have shown the polyhedral method in 2.3.4. Finally, in section 2.5 we conclude this chapter.

2.2 Related problems to k-separator problem

Vertex Cover problem

Given a graph G, we search a minimum size set of vertices such that, for every edge, at least one of the endpoints that belongs to this set. In the weighted version of vertex cover, each vertex has a weight. We are looking for the minimum total weight set of vertices with the property given earlier [START_REF] Karakostas | A better approximation ratio for the vertex cover problem[END_REF]. In other words, given G(V, E)

with weights w i ≥ 0 for all vertices i ∈ V , we must select a minimum weight vertex cover. Observe that a vertex cover is a k-separator for k = 1.

Chapter 2. Related work

Stable Set problem

A stable (or independent) set problem deals with a set of vertices where no two of them are adjacent. In other words, each edge in the graph has at most one endpoint in this set (or a set of pairwise nonadjacent nodes). If the graph is weighted, we aim to compute a maximum-weight stable set. Notice that the complementary of such a maximum stable set is a minimum-weight vertex cover.

Maximal Clique problem

A clique is a complete subgraph, i.e. all nodes are connected to each other. A maximal clique is a biggest one. The maximal clique problem is aimed at computing a maximal clique in a given graph. When the graph is weighted, a maximum-weight clique is obviously a maximum stable set in the complementary graph.

Hitting Set problem

Given a set A = {a 1 , . . . , a n }, a collection B 1 , B 2 , . . . , B m of subsets of A. A hitting set is defined as a set

H ⊂ A, if H ∩ B i = ∅ for 1 ≤ i ≤ m.
We can observe that a vertex cover is a hitting set with each subset reduced to an edge.

As mentioned above, the k-separator problem is a natural generalization of the vertex cover problem. However, there are other possible extensions of the vertex cover problem. Two of them are described below.

Set Cover problem

Given a set of elements E = {e 1 , e 2 , . . . , e n } and a set of m subsets of E, S = {S 1 , S 2 , . . . , S m }, the set cover problem is to find a minimum size collection C of sets from S such that C covers all elements in E (i.e., such that S i ∈C S i = E).

In the weighted version, a weight w j is associated to each subset S j and we aim to compute a minimum weight collection covering E. If E is the set of edges of a weighted graph, and S v is the set of edges incident to vertex v, then we get the classical vertex cover problem.

Capacitated Vertex Cover problem

Let G = (V, E) be an undirected graph, V = {1, 2, ..., n} be a vertex set and E be an edge set. Let w v denote the weight of vertex v and k v denote its capacity.

As defined in [START_REF] Khuller | Capacitated vertex covering with applications[END_REF] a capacitated vertex cover is a function x : V → N such that there exists an orientation of the edges of G in which the number of edges directed into vertex v ∈ V is at most x v k v . These edges are said to be covered by v. The weight of cover is v∈V x v w v . The minimum capacitated vertex cover problem wants to compute the minimum capacitated vertex cover. The main idea of [START_REF] Khuller | Capacitated vertex covering with applications[END_REF] is to use a rounding technique to improve approximation algorithms for this problem.

It can be seen that if k v = |V | -1 for every v ∈ V , the problem is reduced to the minimum weight vertex cover. The problem is NP-hard since it generalizes a NP-hard problem.

In section 2.2.7 we draw a relationship between dissociation set and k-separator problems.

Dissociation Set problem

When weights are unitary and k = 2, the k-separator problem is equivalent to compute the dissociation number of the graph [START_REF] Yannakakis | Node-deletion problems on bipartite graphs[END_REF]. A subset of vertices in a graph G is called a dissociation set if it induces a subgraph so that each vertex has degree at most 1, and the dissociation number is the size of a largest dissociation set.

A dissociation set D is maximal if they are not containing in any another dissociation set in G [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. An example of maximal dissociation set is shown in figure 2.1 as a set of encircled vertices. A minimum maximal dissociation number is defined by

diss -(G) = min{|D| : D ∈ DS(G)} [90]
And a maximum dissociation number is given by

diss + (G) = max{|D| : D ∈ DS(G)} [90]
where

DS(G) = {S ⊂ V : S is a maximal dissociation set in G}
A maximum dissociation set is a dissociation set that contains diss + (G) nodes and the minimum maximal dissociation set is a maximal dissociation set that contains diss -(G) vertices [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. In figure 2 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] maximal dissociation set problem [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. The first problem is a maximum dissociation set problem (M DS), it can be announced as follows : given a graph G and an integer k, does these exist a dissociation set D in G such that |D| ≥ k (i.e., diss + (G) ≥ k ) [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] ? This problem has been introduced for the first time by Yannakakis in [START_REF] Yannakakis | Node-deletion problems on bipartite graphs[END_REF].

The second problem is minimum maximal dissociation set with the same input as M DS, it is resumed to the question : Is there a maximal dissociation set D in G such that |D| ≤ k (i.e., diss -(G) ≤ k) [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] ? The M DS is close to maximum independent set (M IS) and maximum induced matching (M IM ) problems. The maximum cardinality of a stable (independent) set of G, let α(G) be this number , is called the independent number. The maximum cardinality of an induced matching of G is called the induced matching number, and it is denoted by Σ(G). The decision maximum independent set problem is defined by : given a graph G and an integer k, is α ≥ k ?, and the decision problem of maximum induced matching is described by : given a graph G and an integer k, is Σ(G) ≥ k ?

Graph classes/Problems M DS M IM M IS Planar graphs NP-c [11] NP-c [16] NP-c [

Related problems to k-separator problem

The following inequalities hold for any graph G: α(G) ≤ diss + (G) and 2Σ(G) ≤ diss + (G) [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. We have also in the reference [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] for any positive integer r :

diss + (H r -α(H r )) = r, diss + (H r ) = 4r and α(H r ) = 3r
, where H r is the graph formed by identifying one vertex from r copies of cycle C 7 . For the graph K 1,r+2 , we have :

diss + (K 1,r+2 ) -2Σ(K 1,r+2 ) = r, diss + (K 1,r+2 ) = r + 2 and Σ(K 1,r+2 ) = 1 [90].
Before presenting these results, let's us recall some definitions. [START_REF] Lozin | On computing the dissociation number and the induced matching number of bipartite graphs[END_REF] (see figure 2.3 ) and it is a bipartite graph. Note that C 4 and K 2,2 are isomorphic graphs.

Planar graphs

A graph is planar if it is isomorphic to a plane graph [START_REF] Diestel | Graph theory[END_REF]. In other words, If a graph can be drawn without edges crossing except at endpoints. See figure 2.4 for an example of planar graph. the M DS problem is NP-complete for line graphs [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. We have this result by a polynomial time reduction from a variant of partition into isomorphic subgraphs problem [START_REF] Rotics | Finding maximum induced matchings in subclasses of claw-free and p5-free graphs, and in graphs with matching and induced matching of equal maximum size[END_REF]. A partition into isomorphic subgraphs problem is defined by : given graphs G and H with |V (G)| = q|V (H)| where q is a positive integer, the problem can be posed as follow: does there exist a partition q i=1 V i of V (G) such that G(V i ), ∀i = 1, . . . , q, contains a subgraph isomorphic to H ? Theorem 2.1 shows the complexity of M DS problem in the case of line graphs Theorem 2.1 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] Maximum dissociation set is a NP-complete problem for line graphs.

The proof of the theorem 2.1 uses the lemma 2.1.

Lemma 2.1 [START_REF] Yu | Approximability results for the maximum and minimum maximal induced matching problems[END_REF] Partition into subgraphs isomorphic to P 3 is an NP-complete problem for planar bipartite graphs of a maximum vertex degree of 4 in which every vertex of degree 4 is a cut-vertex.

Let α w (G) denote the weight of a maximum weight independent set of G in the case of maximum weight independent set problem. The idea presented in [START_REF] Rautenbach | Some results on graphs without long induced paths[END_REF] and also used in chapter 3 consists in a construction of an extended graph G * from the graph G such that the M DS problem in G becomes equivalent to maximum weight independent set problem in G * . The transformation is described as follow : given a graph G(V, E), let G * (V * , E * ) be a graph defined by :

• V * = V ∪ E • (u * , v * ) ∈ E * , if : 1. u * , v * ∈ V and (u * , v * ) ∈ E 2. u * ∈ V , v * = (x, y) ∈ E and N G (u * ) ∩ {x, y} = ∅ 3. u * = (x, y) ∈ E, v * = (z, t) ∈ E and N G (x) ∩ {z, t} = ∅
Lozin et al. [START_REF] Rautenbach | Some results on graphs without long induced paths[END_REF] have shown that the following lemma 2.2 holds. Lemma 2.2 [START_REF] Rautenbach | Some results on graphs without long induced paths[END_REF] An independent set of maximum weight in G * corresponds to a maximum dissociation set in G. In particular, α w (G * ) = diss + (G).

By the same construction as the one presented above [START_REF] Rautenbach | Some results on graphs without long induced paths[END_REF] we have this important theorem 2.2.

Theorem 2.2 [90] The graph G * of a graph G is chair-free if and only if G is (G 1 , G2, G 3 ) -f ree (for G 1 , G 2 and G 3 graphs see section 3.5)
The following theorem 2.3 proved in the reference [START_REF] Milanic | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF] by using the method of modular decomposition [START_REF] Spinrad | Graph classes: A survey[END_REF] is needed to prove theorem 2.4.

Theorem 2.3 [START_REF] Milanic | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF] The maximum weight independent set problem can be solved in polynomial time in the class of chair-free graphs.

Lemma 2.1 and theorems 2.2 and 2.3 imply the theorem 2.4 Theorem 2.4 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] The maximum dissociation set problem can be solved in polynomial time in the class of (G 1 , G 2 , G 3 )-free graphs.

Another result is given by theorem 2.5 for the mK 2 -free graphs (see section 3.4 for detail).

Theorem 2.5 [90] Let m ≥ 2 be an integer. The graph G * of a graph G is mK 2 - free if and only if G is mK 2 -free.
For some classes of graphs, the complexity of finding the maximum dissociation number can be specified [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. The theorem 2.6 concerns the case of graphs containing a Hamiltonian path.

Theorem 2.6 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] Let G be a graph with n vertices and containing a Hamiltonian path. Then

diss + (L(G)) = 2n 3 .
Theorem 2.7 is focused on the weakly chordal graphs.

Related problems to k-separator problem

Theorem 2.7 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] Minimum maximal dissociation set is NP-complete for weakly chordal graphs.

In order to give an inapproximability result related to the problem of computing the dissociation number Orlovich et all. in [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] start with the lemma 2.3.

Lemma 2.3 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] For each instance (C,X) of 3-SAT with a set C of m clauses and a set X of n variables and for each integer t, there exists a bipartite graph G on 3n+2tn(n+m) vertices such that the following property holds for the minimum maximal dissociation number :

diss -G    ≤ 2n, if C is satisfiable > 2nt, if C is not satisfiable
By using the result of lemma 2.3 we find in [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] the following theorem 2.8 in the case of bipartite graphs for the minimum maximal dissociation set problem.

Theorem 2.8 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] Assuming that P = N P , minimum maximal dissociation set for bipartite graphs cannot be approximated in polynomial time within a factor of p 1-ε for any constant ε > 0, where p denotes the number of vertices in the input graph.

And then [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] gives also an inapproximate result (theorem 2.9) for the maximum dissociation set problem.

Theorem 2.9 [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] Assuming that P = N P , maximum dissociation set cannot be approximated in polynomial time within a factor of p

1 2-ε for any constant ε > 0,
where p is the number of vertices in the input graph.

Thus, computing the dissociation number is NP-hard if the graph is bipartite [START_REF] Yannakakis | Node-deletion problems on bipartite graphs[END_REF].

The NP-hardness still holds for K 1,4 -free bipartite graphs [START_REF] Lozin | On computing the dissociation number and the induced matching number of bipartite graphs[END_REF], C 4 -free bipartite graphs with a maximum vertex degree of 3 [START_REF] Lozin | On computing the dissociation number and the induced matching number of bipartite graphs[END_REF], planar graphs with a maximum vertex degree of 4 [START_REF] Yannakakis | The complexity of restricted spanning tree problems[END_REF], and line graphs [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. Several cases where the dissociation problem can be solved in polynomial time have been shown in the literature: chordal and weakly chordal graphs, asteroidal triple-free graphs [START_REF] Hell | Independent packings in structured graphs[END_REF], (P k , K 1,n )-free graphs (for any positive numbers k and n) [START_REF] Rautenbach | Some results on graphs without long induced paths[END_REF] and (G 1 , G 2 , G 3 )-free graphs [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]. The graphs mentioned here are defined in the cited references and are also recalled in chapter 3.

Chapter 2. Related work

Used methods and techniques

This section is organized as follows : In 2.3.1 we introduce the primal-dual method with application on minimum-weight vertex cover. In 2.3.2 we present the rounding approach. In 2.3.3 we present that the greedy approach can be beneficial to our case. Finally, in 2.3.4 we show the polyhedral approach and an application on the stable set problem.

The primal-dual method

The primal-dual method is one of the oldest techniques used by many researchers, where a good overview methods can be found in [START_REF] Williamson | The primal-dual method for approximation algorithms[END_REF]. It was proposed by Dantzig, Ford and Fulkerson for the first time [START_REF] Ford | A primal-dual algorithm for linear programs[END_REF]. D. Williamson gives in [START_REF] David | The primal-dual method for approximation algorithms[END_REF] a good survey for some NP-hard problems where he used the primal-dual method. First, we will define what a primal-dual method is, and then we will apply it to the minimum weight vertex cover problem. Consider a general linear program (LP) formulation [START_REF] Ford | A primal-dual algorithm for linear programs[END_REF]:

LP 2.1        min cx Ax ≥ b x ≥ 0 Its DUAL is LP 2.2        max yb yA ≤ c y ≥ 0
And Complementary Slackness Conditions (CS)

   PRIMAL: x i > 0 ⇒ j y j a ji = c i DUAL: y j > 0 ⇒ i a ij x i = b j
The idea to solve (LP) is: If x and y are optimal for the primal and the dual respectively, then they satisfy cx = yb and also they satisfy PCS (Primal CS) and DCS (Dual CS).

We now present how the primal-dual method can be applied to the hitting set problem in order to give us an approximation algorithm. Given a ground set of elements E, nonnegative costs C e , ∀e ∈ E, and subsets T 1 , . . . , T p ⊂ E, we want to find a minimum-cost subset A ⊂ E so that A has a nonempty intersection with each subset T i . Such subset is called a hitting set, A, for subsets T i for i ∈ {1, . . . , p}. In [START_REF] David | The primal-dual method for approximation algorithms[END_REF] we find an algorithm to select a set A, see algorithm 2.

Algorithm 2 is based on idea of reverse deletion (i.e., in the reverse of the order Algorithm 2 Algorithm to Select a subset A [START_REF] David | The primal-dual method for approximation algorithms[END_REF]

y ← 0. A1 ← ∅. l ← 1 (l is a counter). while A l is not feasible do Choose a subset V l of violated sets Increase y k uniformly for all T k ∈ V l until ∃e l / ∈ A l such that i:e l ∈T i yi = Ce l . A l ← A l ∪ {e l }. l ← l+1. A ′ ← A l-1 for j ← l-1 down to 1 do if A ′ -{ej} is still feasible then A ′ ← A ′ -{ej}

end if end for end while

Return A ′ in which the elements of A were added) of not needed elements in a given feasible solution A. In other words, once a feasible solution A has been obtained, we should examine the elements of A and delete any that are not needed for a feasible solution [START_REF] David | The primal-dual method for approximation algorithms[END_REF]. Let A l be the set of elements in A at the beginning of the l th iteration, let e l be the element added in the l th iteration, and let A ′ be the final set returned by the algorithm 2 [START_REF] David | The primal-dual method for approximation algorithms[END_REF]. We start by an empty set A 1 . Then we loop until we find a feasible solution. In each iteration l, we choose a subset of violated subset V l , a set

T k is violated if T k ∩ A l = ∅,
IP 2.3              min i∈V w i x i
Subject to :

x i + x j ≥ 1 ∀(i, j) ∈ E x i ∈ {0, 1} ∀i ∈ V
For the linear relaxation "x i ∈ {0, 1}" is replaced by

x i ∈ [0, 1].
The dual program is :

LP 2.4              max (i,j)∈E y (i,j) (1)
Subject to :

k:(i,k)∈E y (i,k) ≤ w i ∀i ∈ V y (i,j) ≥ 0 ∀(i, j) ∈ E
The primal-dual algorithm begins with the dual feasible solution in which all y variables are set to 0, and a primal infeasible solution in which all x variables are set to 0. If there exists some uncovered edge (i,j) for which x i + x j = 0, we increase its corresponding dual variable y (i,j) as much as possible and maintaining dual feasibility, so that the dual constraint (1) becomes tight, i.e.

k:(i,k)∈E y (i,k) = w i ⇒ x i = 1 or k:(j,k)∈E y (j,k) = w j ⇒ x j = 1
Eventually we achieve a primal feasible solution x such that

i∈V w i x i = i∈V ( k:(i,k)∈E y (i,k) )x i . Define S = i∈V ( k:(i,k)∈E y (i,k) )x i .
Because for each edge (i, j) ∈ E, we have two features y (i,j) x i and y (j,i) x j in the summation, and since y (i,j) = y (j,i) , we obtain : S = (i,j)∈E (x i + x j )y (i,j)

Hence :

S = i∈V ( k:(i,k)∈E y (i,k) )x i = (i,j)∈E (x i + x j )y (i,j) ≤ 2 (i,j)∈E y (i,j)
because x i + x j ≤ 2, so we obtain :

Used methods and techniques

i∈V w i x i ≤ 2 (i,j)∈E y (i,j) (2)
Thus, the inequality (2) cited above shows that the algorithm is a 2-approximation algorithm. In this thesis, we will develop in chapter 7 the basic idea cited above into a primal-dual algorithm for a generic problem, by using a hitting set concept.

The Rounding Approach

Is easy to formulate many combinatorial optimization problems as integer linear programs (ILPs). The usual technique consists to solve the linear relaxation of the ILP and then rounding the solution to an integer one. Below we will present an application of the rounding approach on a problem related to vertex cover problem.

An IP formulation (IP 2.5) for capacitated vertex cover problem 2.2.6 is as follows [START_REF] Khuller | Capacitated vertex covering with applications[END_REF] :

IP 2.5                              Minimize v w v x v
Subject to :

y eu + y ev ≥ 1 e = {u, v} ∈ E k v x v -e∈δ(v) y ev ≥ 0 v ∈ V x v ≥ y ev v ∈ e ∈ E y ev ∈ {0, 1} v ∈ e ∈ E x v ∈ N v ∈ V where : δ(v) is a subset of edges incident to v, d(v) = |δ(v)| is a degree of v, x{i, j}
means that the edge is oriented from i to j and y ev = 1 denotes that the edge e ∈ E is covered by vertex v.

The reference [START_REF] Parthasarathy | Dependent rounding in bipartite graphs[END_REF] presents the following algorithm 3:

We can easily obtain this theorem 2.10 :

Theorem 2.10 [36] If α = 2
3 then the algorithm 3 is a 3-approximation.

In the bounded version introduced by Chuzhy and Noar [START_REF] Chuzhoy | Covering problems with hard capacities[END_REF] where there is a bound [START_REF] Parthasarathy | Dependent rounding in bipartite graphs[END_REF] Solve the above LP (relaxation of IP 2.5)to obtain a optimal fractional solution. Pick a value α uniformly at random in the interval [ Suppose that OP T LP = OP T v LP + OP T e LP where : OP T v LP : denotes the optimum fractional cost of chosen vertices. and OP T e LP : denotes the optimum assignment cost of edges. In [START_REF] Parthasarathy | Dependent rounding and its applications to approximation algorithms[END_REF] we found this theorem 2.11 : Theorem 2.11 [START_REF] Parthasarathy | Dependent rounding and its applications to approximation algorithms[END_REF] Algorithm Threshold and Round finds a solution x * , y * such that the expected weight of vertices is at most 2OP T v LP and the expected assignment cost is at most (4 -2 √ 2)OP T e LP . Thus this gives a 2-approximation for the problem with vertex weights and assignment costs (since the total cost is at most 2OP T LP ).

The Greedy Method

To solve an optimization problem we can use greedy method. This approach consists into a construction of a solution throught different stages. At each stage we make a decision that is locally optimal according to some greedy criterion. Moreover, once a decision is made, it is never revoked. The greedy method does not always lead to an optimal solution but there are a few optimization problems that can be solved exactly by the greedy method. Algorithm 4 below describes how to make a solution by a greedy method.

Used methods and techniques Algorithm 4 Greedy Algorithm

Require: I Set of elements . Ensure: S Initialized with ∅. while S is not complete do Select the best element x of I. Put x in S. Remove x from I.

end while

And now we will detail one application of this approach. A greedy algorithm consists in selecting of one set at a time that contains most elements among the uncovered ones. In [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF][START_REF] Lovàsz | On the ratio of optimal integral and fractional covers[END_REF] it was proved that the greedy algorithm is a H(d)approximation algorithm for the unweighed set cover problem, with

H(d) = d i=1 1 i
and d is the size of the largest set.

Chvátal [START_REF] Hochbaum | Approximating covering and packing problems: Set cover, vertex cover, independent set and related problems[END_REF] extends this algorithm to the weighed set cover problem and proves that this algorithm is still a H(d)-approximation algorithm.

Algorithm 5 The Greedy Algorithm [CHVÁTAL] [34]

Step 1:

Set C G = ∅; S 1 j = Sj, j ∈ J; I = {1, ..., m}; k = 0Ṡ tep 2: Set k ← k + 1.Select a set Sj λ , such that w j λ |S λ j λ | = minj∈J w j |S λ j λ | . Set C G = C G ∪ {j λ } and S k+1 j = S k j \S k j λ , j ∈ J, I ← I\S k j λ . Step 3: if I = ∅ then
Stop and output cover C G . else Go to Step 2.

end if

The basic idea of algorithm 5 is to select a set which covers a maximum number of elements not already covered by applying a criterion on weights in each iteration. The weight condition is

w j λ |S λ j λ | = min j∈J w j |S λ j | .
The greedy algorithm is thus an O(log(n))-approximation algorithm. A natural extension of the greedy method to the k-separator problem is proposed in chapter 7.

Polyhedral Approach

The polyhedral approach had been introduced by Edmonds in 1965 [START_REF] Edmonds | Maximum matching and a polyhedron with 0, 1 vertices[END_REF]. Combined with branch-and-bound [START_REF] Rinaldi | A branch-and-cut algorithm for the resolution of largescale symmetric traveling salesman problems[END_REF] or branch-and-cut, it is on one of the most powerful methods to solve NP-hard combinatorial optimization problems. The objective of this method is to reduce an integer program to a linear program by generating a description of the convex hull of feasible solutions, Conv(X), where X is the set of solutions. For NP-hard problems, it is difficult to obtain a complete description for Conv(X). If the inequalities define facets of Conv(X), these inequalities are needed for the description of Conv(X).

In practice, we need to generate efficient methods (exact or heuristic) to separate these inequalities.

It is important to introduce the notion of cutting plane and separation method.

Given the following integer program :

max {cx : x ∈ X ⊂ R n } Let denote it by IP 0 .
The separation problem associated with IP 0 is the problem defined by: given

x ′ ∈ R n , is x ′ ∈ Conv(X)?
If not, find an inequality πx ≤ π 0 satisfied by all points in X, but violated by the point x ′ [START_REF] Wolsey | Integer programming[END_REF].

Let F be a family of valid inequalities πx ≤ π 0 , (π, π 0 ) ∈ F for X.

we can use the algorithm below [START_REF] Wolsey | Integer programming[END_REF] for the cutting-plan and separation for IP 0 , that generates "useful" inequalities from F .

Algorithm 6 Cutting Plane Algorithm [START_REF] Wolsey | Integer programming[END_REF] Initialization : Set t = 0 and P 0 = P . Iteration t: Solve the linear program :max {cx : x ∈ P t } Let x t be an optimal solution. if x t ∈ Z n then Stop and x t is an optimal solution for IP. else

x t ∈ Z n solve the separation problem for x t and the family F . end if if an inequality (π t , π t 0 ) ∈ F is found with π t x t > π t 0 then Set P t+1 = P t ∩ {x : π t x ≤ π t 0 }, and augment t. else

Stop. end if

If the algorithm finishes without finding a solution for IP, the linear relaxation is improved by adding a violated valid inequality. In practice, it is better to add many violated cuts in each step, and not necessary just one at time. In this paragraph we will analyze some inequalities related to the stable (independent) set polytope.

Remember that the stable set problem is related to the k-separator problem. The stable set polytope P G is the convex hull of the characteristic vectors of stable sets of the graph G.

Used methods and techniques

P G = Conv{x ∈ {0, 1} V : {v ∈ V : x v = 1} is a stable of G }
In [START_REF]On certain polytopes associated with graphs[END_REF][START_REF] Mahjoub | On the stable set polytope of series-parallel graph[END_REF] we find some well-known valid inequalities for P G :

• x v ≥ 0 for v ∈ V :Trivial Inequalities. • v∈C x v ≤ k
where C is the vertex set of a cycle of length 2k + 1 : Cycle Inequalities.

• v∈S x v ≤ 1 where S induces a clique : Clique Inequalities.

We describe below the approach to solve the separation problem for the class consisting of the cycle inequalities.

Given x * ∈ R |V | , we define edge-weights as follows :

w * e = 1 2 (1 -x * u -x * v ), ∀e = (u, v) ∈ E. Suppose C = (v 1 , v 2 , . . . , v 2k+1 ) is an odd cycle in G. Then w * (C) = k + 1 2 -2k+1 i=1 x * i (remember that w * e = 1 2 (1 -x * u -x * v )
, for all e = (u, v) ∈ E). Hence x * violates the cycle inequality corresponding to C if and only if W * (C) < 1 2 . Therefore a most-violated cycle inequality corresponds to an odd cycle in G having minimum weight (with respect to w * ).

A minimum-weight odd cycle can be computed using the algorithm introduced by Grötschel and Pulleyblank [START_REF] Pulleyblank | Weakly bipartite graphs and the max-cut problem[END_REF] sketched below.

Let G ′ (V ′ 1 ∪ V ′ 2 , E ′ ) be a bipartite graph constructed from G, where V ′ 1 and V ′ 2
are copies of V with (u 1 , v 2 ) and (u 2 , v 1 ) in E ′ if and only if (u, v) ∈ E; furthermore,

C ′ (u 1 , v 2 ) = C ′ (u 2 , v 1 ) = C(u, v
). Hence a minimum-weight path (with respect to Cheng and Cunningham [START_REF] Cheng | Whell inequalities for stable set polytopes[END_REF] generalized a set of valid inequalities for P G called "wheel inequalities". They derived these inequalities in the case of simple 1-wheel configurations (subdivisions of wheels in which each face-cycle is odd, see figure 2.8) as their support graphs. Cheng and Vries [START_REF] Vries | Antiweb-wheel inequalities and their separation problems over the stable set polytopes[END_REF] enlarged this class of separable inequalities to a new large class antiweb-wheel inequalities valid for P G . Before providing some valid inequalities in the case cited above, we will introduce some definitions [START_REF] Cheng | Whell inequalities for stable set polytopes[END_REF].

C ′ ) from v 1 to v 2 in G ′ corresponds
p m = (V (W ), E(W )) is a graph, where V (W ) = {v 1 , . . . , v m } is a vertex set and the edge set is E(W ) = {(v i , v j )|v i , v j ∈ V (W )

Further connections between the k-separator problem and other problems

Let k be a positive integer, G = (V, E) an undirected graph with

V = {v 0 , v 1 , ..., v 2k+1 } and E = {(v 0 , v i ), (v i , v i+1 ) : 1 ≤ i ≤ 2k + 1}.
We take v 2k+1 = v 1 . We denote by P 0,i a path obtained from v 0 to v i and P i,i+1 a path obtained from v i to v i+1 .

A graph is a 1-wheel of size 2k + 2 if each cycle C i constructed by concatenation of P 0,i , P i,i+1 , P 0,i+1 is odd for any i. ). Now we mention some valid inequalities for the polytope P G [START_REF] Cheng | Whell inequalities for stable set polytopes[END_REF]:

Consider W = W (v 0 , v 1 , v 2 , ..., v 2k+1 ) is a 1-wheel. v 0 is
• (2k + 1)x 0 + 2 2k+1 i=1 x i + 2 v∈S x v + v∈R x v ≤ |S| + 1 2 |R| + 2k + 1 (3). • (2k + 1)x 0 + 2 2k+1 i=1 x i + 2 v∈E x v + 2 v∈S∪R x v ≤ |S| + |R| + |E| + 2k + 1 (4).
In the case of p-wheel inequalities, we have [START_REF] Cheng | Whell inequalities for stable set polytopes[END_REF]:

• 2(2k + 1) p+1 i=1 x 0 i + 2(p + 1) v∈E x v + 2 v∈S x v + v∈R x v ≤ 2k + 1 + |S| + 1 2 |R| + p|E| (5). • 2(2k + 1) p+1 i=1 x 0 i + 2(p + 1) v∈E x v + 4 v∈O x v + 2 v∈S∪R x v ≤ 3(2k + 1) + |S| + |R| + (p -1)|E| (6).
In this thesis we generalize these inequalities for the k-separator problem in chapter 5.

Further connections between the k-separator problem and other problems

As mentioned in the introduction, the case k = 1 corresponds to the vertex cover problem (or the stable set problem) that received a lot of attention in literature. In this section we present two problems close to k-separator problem [START_REF] Neto | The k-separator problem[END_REF]. It starts in 2.4.1 with the first part by describing the disconnecting graphs problem [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. The problem consists in disconnecting a graph by removing a set of vertices of minimum size, such that each connected component has a size less than a given positive number. Finally, the 2.4.2 second and last part is devoted to vertex-separator problem [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. It is a subset of vertices C, where the graph without it is divided into two parts A and B, where there is no edge between A and B, and |C| is minimized subject to a bound on max {|A|,|B|} [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF].

Disconnecting Graphs problem

The only paper where the k-separator problem [START_REF] Neto | The k -separator problem: polyhedra, complexity and approximation results[END_REF] is considered in its general form is [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] where the goal is to remove vertices to disconnect graphs. The following {0,1}-programming formulation is proposed in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF].

Let G(V,E) be an undirected graph, with

n = |V | and m = n 2 IP 2.6                                  max i∈V y i s.t. : x ij + x ik -x jk ≤ 1 , ∀i, j, k ∈ V ,i = j = k (2.6.1) j∈V \{i} x ij ≥ c -1, ∀ i ∈ V (2.6.2)
y i + y j -x ij ≤ 1, ∀ (i, j) ∈ E (2.6.3)
x ij ∈ {0, 1}, ∀i, j ∈ V ,i = j (2.6.4)

y i ∈ {0, 1}, ∀i ∈ V (2.6.5)
and an integer c ≥ 1 (denotes capacity of each commponent). The formulation proposed in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] uses variables y i ∈ {0, 1} and x ij ∈ {0, 1} for all i, j ∈ V , i = j where y i = 0 if and only if i ∈ V is deleted from G and x ij = 0 if and only if i, j ∈ V are not in the same component.

The conditions (2.6.1) are called triangle inequalities and they mean that, for any i, j, k ∈ V , such that i = j = k, if vertices i and j and also vertices j and k are assigned to the same component, then vertices i and k must be assigned to the same component. The constraints (2.6.2) are named the capacity constraints and they ensure that each component must have at most c vertices. Moreover, the inequalities (2.6.3) are called the connectivity constraints, and they imply that for the two vertices of every edge (i, j) ∈ E, they must be in the same component or they will be deleted from the graph G. At last, constraints (2.6.4), (2.6.5) are the integrality constraints.

Further connections between the k-separator problem and other problems

In [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] we have the following lemma 2.4.

Lemma 2.4 [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] Let (x, y) ∈ ℜ m × ℜ n be a feasible solution to the Linear Programming relaxation of (IP 2.1) with y i ∈ {0, 1} for all i ∈ V . Then there exists a feasible solution (x, y) ∈ {0, 1} m+n to (IP 2.1) with y i = y i for all i ∈ V Therefore, by lemma 2.4 the inequalities x ij ∈ {0, 1}, such that i = j can be relaxed to 0 ≤ x ij ≤ 1, by this relaxation the number of variables in (IP 2.1) can be reduced to n [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. In [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] we have a polyhedral study of the polytope related to the formulation above, we will show some of this results below. Many applications of this problem are mentioned in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. This includes a process planning (or scheduling) application. It consists to consider a set of machines M 1 ,M 2 ,. . . ,M n , and a set of process P 1 ,P 2 ,. . . ,P l . Additionally, a ij = 1 (where

a ij ∈ n × l {0,1}-matrix A) if
and only if P j (j = 1, . . . , l) has to be runned on machine M i (i = 1, . . . , n) and an postive integer d ≥ 1. The problem is to assign a maximum process to the so-called production cells, where each one contains no more than d processes, each process and each machine take place in at most one cell and processes assigned to different cells are not connected (i.e., there is not any machine h such that a hi a hj = 0 if P i and P j are in different cells) [START_REF] Wemmerlov | Group technology in the us manufacturing industry: A survey of current practices[END_REF]. See also [START_REF] Crama | Models for machine-part grouping in cellular manufacturing[END_REF][START_REF] Hadley | Finding part-machine families using graph partitioning technique[END_REF] for more details. Other applications are mentioned in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF].Let P (G, c) denote a polytope of the disconnecting graphs problem (DG). We can observe that P (G, 1) is isomorphic to the independent set polytope. The polytope P (G, c) with c ≥ 2 is full dimensional [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. Theorem 2.12 gives some conditions to define a facet for P (G, c).

Theorem 2.12 [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] Let G = (V, E) be a graph, c ≥ 2 an integer, and let (a, b) T (x, y) ≤ a 0 be a facet-defining inequality for P (G, c).

1. If, for any d ≥ c, the inequality (a, b) T (x, y) ≤ a 0 is valid for P (G, d), then (a, b) T (x, y) ≤ a 0 is facet-defining for P (G, d).

If, for any E

′ ⊆ E, the inequality (a, b) T (x, y) ≤ a 0 is valid for P ((V, E ′ ), c), then (a, b) T (x, y) ≤ a 0 is facet-defining for P ((V, E ′ ), c)
For subgraph of G we can define also a facet in some conditions, the result is given in theorem 2.13.

Theorem 2.13 [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] Let G = (V, E) be a graph, let c ≥ 2 be an integer, let G ′ = (U, E(U )) be a subgraph of G, and let i,j∈U, i =j

a ij x ij + i∈U b i y i ≤ a 0 (2.1)
be a facet-defining inequality for P (G ′ , c) such that the following conditions hold.

1. Inequality 2.1 is valid for P (G, d) for some integer d ≥ c.

2. There exists an order (e 1 , . . . , e p ) of the elements in

E := {(i, j)|i ∈ U, j ∈
V \U } such that for each e k ∈ E there exists (x, y) ∈ P (G, d) satisfying 2.1 at equality with x e k = 1 and x e l = 0 for all l = k + 1, . . . , p.

3. For all i ∈ V \U there exists (x, y) ∈ P (G, d) with y i = 1 satisfying 2.1 at equality. Then 2.1 is facet-defining for P (G, d).

Some trivial facet-defining inequalities are shown in theorem 2.14.

Theorem 2.14 [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] Let G = (V, E) be a graph, let c ≥ 2 be an integer and let (a, b) T (x, y) ≤ a 0 be any facet-defining inequality for P (G, c).

1. The inequalities x ij ≥ 0 (i, j ∈ V, i = j) define (trivial) facets of P (G, c).

The inequalities

x ij ≤ 1 (i, j ∈ V, i = j)
do not define facets of P (G, c).

The inequalities

y i ≥ 0 (i ∈ V ) define (trivial) facets of P (G, c).

The inequalities

y i ≤ 1 (i ∈ V ) define facets of P (G, c).
5. a 0 ≥ 0.

For nontrivial facets : b

i ≥ 0 for all i ∈ V .
In [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] we found also a relationship between clique partitioning polytope, capacitated clique partitioning polytope, maximal weighted clique polytope, boolean quadric polytope and a polytope denoted by P (G, B, C) on the one hand and P (G, c) polytope on the other hand. Let us first describe these polytopes. Then in a second stage we show a relationship between these polytopes and P (G, c).

Given a complete graph

K n = (V n , E n )
where |V n | = n and with edge weights

Further connections between the k-separator problem and other problems

w ij ∈ R for all {i, j} ∈ E n , the clique partitioning problem (CLP) [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] is defined by

CLP              max {i,j}∈En w ij x ij s.t. : x ij + x ik -x jk ≤ 1, ∀i, j, k ∈ V, i = j = k (2.
2)

x ij ∈ {0, 1}, ∀i, j ∈ E n Let P CLP n
denote a polytope of (CLP ). This polytope is studied in [START_REF] Wakabayashi M | facets of the clique partitioning polytope[END_REF][START_REF] Spieksma | The clique partitioning problem: Facets and patching facets[END_REF].

If we add a bound on the number of nodes in a clique (called it c), we obtain the capacitated clique partitioning problem (CCLP ) [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]: add to (CLP ) the inequali-

ties j∈V \{i} x ij ≤ c -1 f or all i ∈ V (2.
3)

The polytope associated with this problem is declared

P CCLP n,c
. A depth study can be found in [START_REF] Suletzki | A cutting-plane algorithm for optimal graph partitioning[END_REF][START_REF] Faigle | A cutting-plane approach to the edge-weighted maximal clique problem[END_REF]. If we add the variables y i ∈ {0, 1}, ∀i ∈ V to (CCLP ) and the appropriate connectivity constraints we get the polytope P (G, c).

When we look for a single maximal weighted clique it's sufficient to add the constraints [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] :

x ij + x jk + x kl -x ik -x jl ≤ 1, ∀i, j, k, l ∈ V and i = j = k = l (2.4)
The polytope of this problem, called

P CLI n,c
is studied by Dijkhuizen and Faigle [START_REF] Faigle | A cutting-plane approach to the edge-weighted maximal clique problem[END_REF][START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. Park and Lee studied in [41] the same problem but they introduced the following extended formulation :

EXT CLI                              max {i,j}∈En w ij x ij s.t. : y i + y j -x ij ≤ 1∀{i, j} ∈ E n i∈Vn y i ≤ c (2.5) x ij -y i ≤ 0, x ij -y j ≤ 1, ∀{i, j} ∈ E n x ij ∈ {0, 1}, ∀{i, j} ∈ E n y i ∈ {0, 1}, ∀i ∈ V n Let P extcli n,c
denote a polytope of (EXT CLI). This polytope is also investigated in [START_REF] Souza | The edge-weighted clique problem: valid inequalities, facets and polyhedral computations[END_REF]. When we remove constraint 2.5 from the formulation above we get the boolean quadric polytope P boqd n , which has been studied by Padberg in [START_REF] Padberg | The boolean quadric polytope: some characteristics, facets and relatives[END_REF].

The last polytope is based on formulation proposed by Borndörfer et al. [START_REF] Borndörfer | Decomposing matrices into blocks[END_REF] in the field of decomposition constraint matrices, and by Kumar et al. [START_REF] Vanelli | Grouping parts and components in flexible manufacturing systems[END_REF] in a cell-formation context. This formulation has a supplementary input parameter, an integer B ∈ N , where B is an upper bound on the number of components to be created. The formulation uses variables z ib ∈ {0, 1}, ∀i ∈ V and b ∈ {1, . . . , B}, such as

z ib =    1 if vertex i ∈ V is assigned to component b, 0 otherwise. The corresponding integer program is [53]: MD                          max i∈ B b=1 z ib s.t. : B b=1 z ib ≤ 1, ∀i ∈ V i∈V z ib ≤ c, ∀b ∈ {1, . . . , B}(2.6) z ib + z jb ′ ≤ 1, ∀{i, j} ∈ E, b, b ′ ∈ {1, . . . , B}, b = b ′ z ij ∈ {0, 1}, ∀i ∈ V, b ∈ {1, . . . , B} Let P (G, B, c
) denote a polytope of M D. The block-invariant inequalities have been defined in [START_REF] Borndörfer | Decomposing matrices into blocks[END_REF]. This inequalities can be written as

i∈V a i B b=1 z ib ≤ a 0 (2.7)
The following lemma 2.5 shows the relationship between the polytopes introduced above.

Lemma 2.5 [53]

1. An inequality valid for

P CLP n is valid for P CCLP n,c
for all n, c ∈ N .

An inequality valid for

P CCLP n,c is valid for P CLI n,c
for all n, c ∈ N as well as valid for P (G, c).

An inequality valid for

P CLI n,c is valid for P (G, c) if G is a clique , for all c ∈ N .

Further connections between the k-separator problem and other problems

4. A block-invariant inequality valid for P (G, B, c) is valid for P (G, c) when substituting y i = B b=1 z ib , f or i = 1, . . . , n.

5. An inequality valid for P (G, c) is valid for

P extcli n,c
for all n, c ∈ N .

A graphical representation of lemmas 2.5 is given in figure 2.9 [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF].

Lemma 2.6 [53]
1. An inequality a T x ≤ a 0 facet-defining for P CLP n is also facet-defining for

P CCLP n,c
for all c ≥ k CLP a .

2. An inequality a T x ≤ a 0 facet-defining for P CCLP n,c is facet-defining for P (G, c)

for all graphs G = (V, E) with |V | = n.
3. An inequality a T x ≤ a 0 facet-defining for P extcli n,c

which is valid for

P (G, c) is facet-defining for P (G, c) for all graphs G = (V, E) with |V | = n.
4. An inequality a T x ≤ a 0 facet-defining for P BOQD n is also facet-defining for P (G, c) for all graphs c ≥ k BOQD a and for all graphs G = (V, E) with |V | = n.

A block-invariant inequality

i∈V b i B b=1 z ib ≤ b 0 (2.8)
facet-defining for P (G, B, c) is facet-defining for P (G, c) when substituting

y i = B b=1 z ib , f or i = 1, . . . , n.
A graphical representation of lemmas 2.6 is given in figure 2. ), a T x = a 0 ∀x ∈ M a where a T x ≤ a 0 f acet-def ining f or P BOQD n } They are many other valid inequalities for P (G, c) in the reference [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF], among these we found the following constraints used in the branch-and-cut algorithm presented in the same reference (see [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] for more details).

• The cover inequalities :

Let W ⊂ V such that |W | = c+k, c ≥ 2 and (W, E(W )) is k-vertex connected,
we have the following valid inequality :

i∈W y i ≤ c (2.9)
Borndörfer gives in [START_REF] Borndörfer | Decomposing matrices into blocks[END_REF] the following heuristic (algorithm 7) to separate cover inequalities with k = 1 and k = 2. Let E({v}, W ) denote the set of edges incident to v and to W . [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] for each edge {i, j} ∈ E do Set W := {i, j} and N := N (i) ∩ N (j) while (N = ∅) and

Algorithm 7 Searching W ⊆ V such that (W, E(W )) is two connected
(|W | < c + 2) do Choose l ∈ N W := W ∪ {l} N := {v ∈ V \W : |E({v}, W )| ≥ 2} end while if |W | = c + 2 then Check cover inequality end if end for • Clique inequalities : Let c, p two integers with c ≥ p + 1 and let U ⊆ V be such that (U, E(U )) is a clique in G. Then the inequality 2.10 defines a facet iff |U | ≥ p + 2 [53]. p. i∈U y i - {i,j}∈E(U ) x ij ≤ p+1 2 (2.
U = ∅ and N = V Call the subroutine Clique(U, N ) CLIQUE (U,N) BEGIN k := min{l|(v l ∈ N ) ∧ (l > max{m|vm ∈ U })} while (k ≤ n) do U := U ∪ {v k } N ′ := {v ∈ N |{v, v k } ∈ E} if (N ′ = ∅) then U is maximal clique else CLIQU E(U, N ′ ) end if U := U \{v k } k := min{l|(v l ∈ N ) ∧ (l > k)} end while END • Star inequalities : Let c ≥ 2 an integer, and let i ∈ V be such as |N (i)| ≥ c. Then the inequality below is valid for P (G, c) (|N (i)| -c + 1).y i + j∈N (i) y i ≤ |N (i)| (2.11)
The number of star inequalities is n, and therefore separation of this class of inequalities is done by enumeration [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF].

• K 1,2 inequalities :

Let c ≥ 3 be an integer, and i, j, k ∈ V, i = j = k such that {i, j}, {i, k} ∈ E and {i, j} / ∈ E. Then K 1,2 inequalities

y i + y j + y k -x jk ≤ 2 (2.12)
is valid and facet-defining for P (G, c). The separation algorithm is done by enumeration and the number of K 1,2 -inequalities is O(n 3 ).

• Arrow inequalities :

Let c ≥ 3 an integer and U = i, j, k, l ⊆ V such that (U, E(U )) is a clique in G. Then the inequality y(i, j, l) + x ik -x(E(j, k, l)) ≤ 2 (2.13) problems
is valid and facet-defining for P (G, c). The separation is done by an enumeration algorithm in O(n 4 ).

• Four-cycle inequalities :

The four-cycle inequality is

y(C) -x v 1 ,v 3 -x v 2 ,v 4 ≤ 2 (2.14)
Where c ≥ 3 is an integer and

C := v 1 , v 2 , v 3 , v 4 is a subset of V that induces a cycle in G.
This inequality is valid and facet-defining for P (G, c). The separation of these inequalities is done by enumeration.

• Triangle inequalities :

The separation of the following triangle inequalities is done by enumeration

x ij + x ik -x jk ≤ 1, f or all distinct i, j, k ∈ V (2.15)

Vertex Separator problem

The last problem is the vertex separator problem. Given a connected graph G, a vertex separator in G is a subset of vertices whose removal disconnects G. Balas in [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] proposes a polyhedral study of a vertex separator problem (V SP ). A V S can be defined as a subset of vertices, whose removal divides the graph into two disjoint subgraphs. In [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] we have the following definition of VSP : given G(V, E)

an undirected graph, an integer b ≤ n and C i a cost for vertex i ∈ V , we want to split V into three sets A, B and C, where A and B are not empty (called shores),

(i, j) / ∈ E, i ∈ A and j ∈ B (condition (i)), max{|A|, |B|} ≤ b (condition (ii))
and j∈C C j is minimized subject to the two conditions mentioned before (i.e. , condition (i) and condition (ii)).

A mixed integer formulation is proposed in [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF].

IP 2.7                                    max i∈V C i (u i1 + u i2 ) s.t. : u i1 + u i2 ≤ 1 , ∀i ∈ V (2.7.1)
u i1 + u j2 ≤ 1 , ∀(i, j) ∈ E (2.7.2) u j1 + u i2 ≤ 1 , ∀(i, j) ∈ E (2.7.3) 1 ≤ u k (V ) ≤ b , k = 1, 2 (2.7.4)
u ik ≥ 0, ∀i ∈ V, k = 1, 2 (2.7.5) u i1 integer, ∀i ∈ V (2.7.6) Let u i1 =    1 if i ∈ A 0 otherwise u i2 =    1 if i ∈ B 0 otherwise
For S ⊂ V and k = 1, 2, we denote by u k (S) = i∈S u ik and u(S) = u 1 (S) + u 2 (S). Many applications of VSP are mentioned in [START_REF] Djidjev | Partitioning planar graphs with vertex costs: Algorithms and applications[END_REF][START_REF] Vazirani | Finding separator cuts in planar graphs within twice the optimal[END_REF][START_REF] Tarjan | A separator theorem for planar graphs[END_REF][START_REF] Peyton | Parallel algorithms for sparse linear systems[END_REF], among them a problem of minimizing the work involved in solving systems of equations [START_REF] Peyton | Parallel algorithms for sparse linear systems[END_REF].

Inequality (2.
We detail below the class of symetric facets of P (G, b) [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. A valid inequality of P (G, b) is called symmetric if for all i ∈ V , the coefficients u j 1 and u j 2 are equal.

Let G(V, E) be a simple undirected graph. A valid inequality αu ≤ α 0 is maximal if there exists no valid inequality α ′ u ≤ α 0 with α ′ ≥ α and α ′ j > α j for some j ∈ V [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. In objective to prove in which case the inequality 2.16 is maximal for P (G, b) let us introduce some definitions [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. Let S ⊂ V be a dominator of V . For i ∈ S,

S ⊆ V such that V ⊆ (S ∪ N S (G)) is called a dominating set for G or for V . A vertex i ∈ V is universal if it is neighbor to evry j ∈ V \{i}.
P (i) := {k ∈ V \S : N S (k) = i}
is the set of pendent vertices of i [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF].

Let S D := {i ∈ S : [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] (label 2.4.2). A forbidden vertex v ∈ V \S relative to a minimal connected dominator S of G is a node where G({S ∪ {v}}) has a non articulation point and v is adjacent to every j ∈ i∈S P (i) [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. Now we present the proposition 2.4.

P (i) = ∅}, S Q := S\S D , if S Q = ∅ then every i ∈ S Q is an articulation point of G(S)

Proposition 2.4 [21]

The inequality 2.16, with |S| ≤ b, is maximal if and only if G has no forbidden vertices relative to S.

Let F := {u ∈ P (G, b) : u(S) = |S| -1} be a face of P (G, b). F is a facet of P (G, b)
if and only if for each equation αu = |S| -1, where u ∈ F and have a coefficients α j 1 and α j 2 such that

α j 1 = α j 2 =    1 if j ∈ S
0 otherwise (i.e., j ∈ V \S) We need propositions 2.5 -2.7 to prove proposition 2.9. But before giving this proposition we will present proposition 2.8 in order to show that if G has a node for which none of three conditions cited in propositions 2.5 -2.7 is satisfied, then inequality 2.16 is not a facet of P (G, b) Proposition 2.5 [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] If for some v ∈ V \S, G(S ∪ {v}) and G(S) have a common articulation point, then

α v 1 = α v 2 = 0. Proposition 2.6 [21] If for some v ∈ V \S there exists l ∈ P (i) for some i ∈ S such that (v, l) / ∈ E, then α v 1 = α v 2 = 0 Proposition 2.7 [21] If v ∈ P (i) for some i ∈ S such that |P (i)| ≥ 2, then α v 1 = α v 2 = 0.
Under consideration of some conditions the inequality 2.16 is not facet-defining for P (G, b), the proposition 2.8 shows us this result.

Proposition 2.8 [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] Suppose there exists v ∈ V \S with the properties

• G(S ∪ {v}) and G(S) have no common articulation point

• v is adjacent to every j ∈ k∈S P (k)

• {v} = P (i) for some i ∈ S

Then the inequality 2.16 does not define a facet of P (G, b).

Proposition 2.9 shows in which case (2.16) is a facet of P (G, b). But before presenting it, we give some definitions and notations taken from [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] where those definitions are required for the presentation of proposition 2.9.

Let S be a minimal connected dominator, with S = S D ∪ S Q , where S D is defined above in label 2.4.2 that is the unique minimal dominator contained in S, and

S Q which is defined above in label 2.4.2. A subset S ⊂ V is called orderly, if either S Q = ∅, or else S D contains no articulation point of G(S)
, and S Q can be ordered into sequence i 1 , . . . , i q , with the property that for r = 1, . . . , q, G(S\{i r })

has exactly two components with vertex sets S ′ , S ′′ , such that {i 1 , . . .

, i r-1 } ⊂ S ′ , {i r+1 , . . . , i q } ⊂ S ′′ [21]. Let s = |S|, d = |S D | and q = |S Q | . Let C i is a separator in F with shores A i , B i , let a i = |A i ∩S D | and b i = |B i ∩S D |. A separator C i is called of type 1 if S\{i} is contained in a single shore, and of type 2 if (S\{i}) ⊆ A i ∪ B i , with A i ∩ S = ∅ = B i ∩ S [21]
. We have a i + b i = d for the separators of type 2, with i ∈ S Q [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. A collection C of type 2 separators is called representative if it contains exactly one member C i for each i ∈ S Q [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF]. If the members of such a collection is ordered according to the rule a i ≥ a i+1 (b i ≤ b i+1 ), i = 1, . . . , q -1, and V \S satisfies at least one of the conditions of propositions 2.5, 2.6 and 2.7.

a 2k+1 1 = a 1 + a 3 + . . . +
a q-1 1 -a q 2 = (d-1) 2 , if q is even a q 1 -a q-1 2 = d 2 , if q is odd Proposition 2.
In the reference [START_REF] De Souza | The vertex separator problem: a polyhedral investigation[END_REF] we find more results of V SP polytope among this a class of asymmetric facets of P (G, b) and some generalized inequalities for P (G, b).

Conclusion

In this chapter we have exposed some related works to k-separator problem. Among these we mentioned many combinatorial optimization problems that have a relationship with k-separator problem. From primal-dual method to polyhedral approach, Chapter 3

Polynomial cases

Basics

A tree-decomposition of G is defined by a pair (X , T ) where X = (X t ) t∈V (T ) is a set of vertex subsets of G indexed by vertices of a tree T satisfying the following:

(i) for each v ∈ V (G), there is some t ∈ V (T ) such that v ∈ X t ; (ii) for each edge (u, v) ∈ E(G), there is some t ∈ V (T ) such that u ∈ X t and v ∈ X t ; (iii) for each vertex v ∈ V (G), if v ∈ X t 1 and v ∈ X t 2 then v belongs to X t for each t ∈ V (T )
on the path between t 1 and t 2 .

Property (iii) implies that the subgraph of T induced by the vertices t such that X t contains v is a subtree. The width of the decomposition is given by

max t∈V (T ) |X t |-1.
The treewidth of G is the minimum width over all tree-decompositions of G.

We assume here that G has a treewidth bounded by a constant l. It is well-known that computing the treewidth of a graph and a corresponding minimum-width treedecomposition can be done in linear time (assuming that l is constant) [START_REF] Bodlaender | A linear time algorithm for finding tree-decompositions of small treewidth[END_REF]. Many NP-hard optimization problems can be solved in polynomial time for boundedtreewidth graphs. The algorithms are generally based on dynamic programing and a tree-decomposition of the graph (see e.g., [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF][START_REF] Borie | Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs[END_REF][START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF]).

A relatively general approach is proposed in [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF] to solve vertex partitioning problems in bounded-treewidth graphs. Since the k-separator problem can be seen as a vertex partitioning where the partition is given by the k-separator and the remaining connected components, the approach of [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF] might be used. However, the algorithm of [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF] has a polynomial complexity only if the number of subsets of the partition is bounded by the logarithm of the size of the graph (Theorem 5.7 of [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF]).

Unfortunately, this does not hold for the k-separator problem. The approach of [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF] also leads to a non-polynomial algorithm. Another extension is proposed in [START_REF] Borie | Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs[END_REF] but it is not clear for us how to express the k-separator problem in a compatible way with [START_REF] Borie | Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs[END_REF].

However, it is not difficult to derive a dynamic programming algorithm for our problem. It is described below for sake of completeness.

A dynamic-programming algorithm

Similarly to most dynamic-programming algorithms for bounded-treewidth graphs, we are going to use the separator property induced by the tree-decomposition: given an edge (t 1 , t 2 ) ∈ E(T ), let T 1 and T 2 be the connected components of T obtained by deletion of the edge, let

Y 1 = ∪ t∈V (T 1 ) X t and Y 2 = ∪ t∈V (T 2 ) X t , then X t 1 ∩ X t 2 separates Y 1 from Y 2 . In other words, Y 1 ∩ Y 2 = X t 1 ∩ X t 2 and each vertex of Y 1 \ Y 2 is not adjacent to any vertex of Y 2 \ Y 1 .
Let us consider T as a rooted tree (by choosing an arbitrary root) and let T t be the subtree rooted at t ∈ V (T ).

Then, we can define Y t as the union of all subsets indexed by the vertices of T t :

Y t = ∪ t ′ ∈V (Tt) X t ′ .
The main idea of this type of algorithms is to consider, for each t ∈ V (T ), a table of partial solutions of the optimization problem that can be built by considering the tables of the children vertices of t (in the rooted tree). The validity of this table construction is based on the separator property induced by the tree-decomposition. The optimal solution of the problem is obtained at the root of the tree. This approach is useful in order to derive a polynomial-time algorithm to solve the problem when the size of the table of each t ∈ V (T ) is polynomially bounded (for the case when the width of the tree decomposition is bounded by a constant).

Before describing how these tables are built, let us introduce one more concept.

A nice tree-decomposition is a decomposition where each vertex t ∈ V (T ) falls into one of the following categories:

• Leaf: t is a leaf of T and |X t | = 1.
• Join: t has exactly two children, say t ′ and t ′′ , and X t = X t ′ = X t ′′ .

• Introduce: t has exactly one child, say t ′ , and there is a vertex v ∈ V (G) such that X t = X t ′ ∪ {v}.

• Forget: t has exactly one child, say t ′ , and there is a vertex

v ∈ V (G) such that X t = X t ′ \ {v}.
It is easy to show that given a tree-decomposition, one can transform it into a nice tree decomposition having the same width and a linear number of vertices.

This can be done in polynomial time [START_REF] Kloks | Treewidth -computations and approximations[END_REF]. We will then assume that a nice treedecomposition of minimum-width is known.

For each t ∈ V (T ), for each partition (S 0 , S 1 , ..., S j ) of X t where j ≤ l and for each set of numbers l 1 , ..., l j with |S i | ≤ l i ≤ k, let Z * (t, S 0 , S 1 , ..., S j , l 1 , ..., l j ) be the weight of a minimum-weight k-separator of G(Y t ) where S 0 belongs to the k-separator while all vertices of S i (1 ≤ i ≤ j) belong to the same connected component of size l i . Observe that if S i and S i ′ (1 ≤ i < i ′ ) are adjacent then Z * (t, S 0 , S 1 , ..., S j , l 1 , ..., l j ) = ∞ since S i and S i ′ should be merged into one connected component. We assume that the table of t ∈ V (T ) contains an entry for each partition (S 0 , S 1 , ..., S j ) with the associated numbers l 1 , ..., l j and the optimal cost Z * (t, S 0 , S 1 , ..., S j , l 1 , ..., l j ). A k-separator of G(Y t ) achieving this cost (containing S 0 ) can also be kept in the table of t.

The number of entries of the table for each t ∈ V (T ) is bounded by k l+1 (l + 1) l+1 which is polynomial. The optimum solution is obtained at the root vertex by considering the solution of minimum weight among all partial solutions at the root's table.

To complete the algorithm description, we only have to show how to build the table of a vertex t knowing the tables of the children of t. The case where t is a leaf is obvious. Let us consider the case of a Join vertex t with two children t ′ and t ′′ . To obtain Z * (t, S 0 , S 1 , ..., S j , l 1 , ..., l j ), it is clear that we should consider entries of type Z * (t ′ , S 0 , S ′ 1 , ..., S ′ j ′ , l ′ 1 , ..., l ′ j ′ ) and Z * (t ′′ , S 0 , S ′′ 1 , ..., S ′′ j ′′ , l ′′ 1 , ..., l ′′ j ′′ ) (with the same set S 0 ). Consider two such partitions (S 0 , S ′ 1 , ..., S ′ j ′ ) and (S 0 , S ′′ 1 , ..., S ′′ j ′′ ) of the same set X t . By merging S ′ a and S ′′ b if they are adjacent, we get a new partition (S 0 , S 1 , ..., S j ) of X t . Let S i = (∪ a∈I S ′ i ) ∪ (∪ b∈J S ′′ b ) be one of the subsets of this new partition where I ⊂ {1, ..., j ′ } and J ⊂ {1, ..., j ′′ } are the set of indexes of the merged subsets that led to S i . Then the size of the connected component containing S i is given by

l i = |S i | + a∈I (l ′ a -|S ′ a |) + b∈J (l ′′ b -|S ′′ b |). Observe that l ′ a -|S ′ a |
represents the number of vertices of G(Y t ′ ) that belong to the same connected components as S ′ a but not to X t ′ = X t . These vertices do not belong to Y t ′′ by the separator property.

If the combination of Z * (t ′ , S 0 , S ′ 1 , ..., S ′ j ′ , l ′ 1 , ..., l ′ j ′ ) and Z * (t ′′ , S 0 , S ′′ 1 , ..., S ′′ j ′′ , l ′′ 1 , ..., l ′′ j ′′ ) leads to connected components of size less than or equal to k (i.e., all numbers l i are ≤ k), then we keep in the table of t the cost Z * (t ′ , S 0 , S ′ 1 , ..., S ′ j ′ , l ′ 1 , ..., l ′ j ′ )+ Z * (t ′′ , S 0 , S ′′ 1 , ..., S ′′ j ′′ , l ′′ 1 , ..., l ′′ j ′′ ) -v∈S 0 w v obtained with the new partition and the corresponding numbers l i . Observe that the cost v∈S 0 w v is subtracted since it is counted twice in Z * (t ′ , S 0 , S ′ 1 , ..., S ′ j ′ , l ′ 1 , ..., l ′ j ′ ) and Z * (t ′′ , S 0 , S ′′ 1 , ..., S ′′ j ′′ , l ′′ 1 , ..., l ′′ j ′′ ). Notice that since the same partition (S 0 , ..., S j ) with the corresponding sizes (l 1 , ..., l j ) might be obtained by different combinations of Z * (t ′ , S 0 , S ′ 1 , ..., S ′ j ′ , l ′ 1 , ..., l ′ j ′ ) and Z * (t ′′ , S 0 , S ′′ 1 , ..., S ′′ j ′′ , l ′′ 1 , ..., l ′′ j ′′ ), we should of course keep the one having the lowest cost. As a conclusion, the table of each Join vertex t can be built in polynomial time using the tables of its children t ′ and t ′′ .

Let us now assume that t is an Introduce vertex whose unique child is t ′ and let v ∈ V (G) be the vertex such that X t = X t ′ ∪ {v}. Let us consider the entry Z * (t, S 0 , ..., S j , l 1 , ..., l j ) where v ∈ S 0 . Then, Z * (t, S 0 , ..., S j , l 1 , ..., l j ) = Z * (t ′ , S 0 \ {v}, S 1 , ..., S j , l 1 , ..., l j ) + w v . The case where v / ∈ S 0 is slightly more complicated.

Assume that v ∈ S i 0 for some i 0 = 0. Since v / ∈ Y t ′ (by property (iii) of treedecompositions), the deletion of v can split the component containing S i 0 into several components and the set S i 0 \ {v} will be partitionned into several subsets A 1 , ..., A p where the vertices of A i belong to the same connected component of size l ′ i . Observe that since v is not adjacent to any vertex in Y t ′ \ X t , we should have l i 0 -1 = i l ′ i . This clearly implies that Z * (t, S 0 , ..., S j , l 1 , ..., l j ) = min A 1 ,...,Ap;l ′ 1 ,...,l ′ p : S i 0 \{v}=A 1 ∪...∪Ap;

i l ′ i =l i 0 -1;|A i |≤l ′ i ≤k
Z * (t ′ , S 0 , ..., S i 0 -1 , A 1 , ..., A p , S i 0 +1 , ..., S j , l 1 , ..., l i 0 -1 , l ′ 1 , ...., l ′ p , l i 0 +1 , ..., l j ).

The equation above shows again that the table of t can be computed in polynomial time using the table of its child. The case where v is a Forget vertex can be handled in a similar way.

Proposition 3.1 The k-separator problem can be solved in polynomial time for graph with bounded treewidth. This holds even if k is part of the input.

Paths, trees and cycles

A more specialized algorithm is described for paths, trees and cycles.

Let us start with the case where G = (V, E) is a tree denoted T . Without loss of generality, we assume that the edges of T are oriented such that T can be seen as a tree rooted at an arbitrary vertex r. Let N + v denote the set of children of a vertex v. The number of children of v is denoted by

d + v = |N + v |.
The children of v can be assumed to be arbitrarily ordered from the first to the last. Then v i corresponds to the i th child of v. Let T v be the subtree rooted at v. We also use T p v to denote the subtree containing v and the p subtrees rooted at the first p children of v. Observe that

T v = T d + v v .
We will describe a dynamic programming approach to compute a minimumweight k-separator. Let C v be the weight of an optimal k-separator of the subtree

T v . The global optimum is of course obtained when v = r.
Let us also use C in v to denote the cost of an optimal k-separator of T v under the conditions that v belongs to this k-separator.

Observe that when v belongs to the k-separator, the subtrees rooted at the children of v become non connected together. In other words, one can write the following:

C in v = w v + y∈N + v C y . (3.1)
For each number i such that 1 ≤ i ≤ k and each vertex v ∈ V , let C out v (i) be the weight of an optimal k-separator under the condition that v does not belong to this separator and there is a connected component of T v of size exactly equal to i containing v and not belonging to the separator. In other words, we require here that after the deletion of the k-separator of T v , v remains in the graph and belongs to a component of size i.

Observe that C v is just given by:

C v = min C in v , min i=1...k C out v (i) . (3.2)
We need one more definition. For any vertex v ∈ V , any number

1 ≤ i ≤ k and any number 1 ≤ p ≤ d + v , let C out v (p, i)
be the weight of an optimal k-separator of T v under the following conditions: v does not belong to the separator; after the deletion of the k-separator T p v contains a connected component of size i including v. Observe that:

C out v (i) = C out v (d + v , i). (3.3)
It is now easy to see that C out v (p, i) can be expressed as follows: Similarly to many dynamic programming algorithms related to trees, we start by the leaves of the tree, and we go up until we reach the root r.

C out v (p, i) = min C out v (p -1, i) + C in vp , min j=1...i-1 C out v (p -1, i -j) + C out vp (j) . ( 3
To finish the description of the algorithm we should only observe that when v is a leaf, then

C in v = w v , C out v (1) = 0 and C v = min {w v , 0}
while all other quantities are not defined (assumed to be infinite).

The number of quantities to be computed (

C out v (p, i), C in v , C out v (i) and C v ) is about O(nk) (using the fact that v∈V d + v = |V | -1 = n -1)
. The complexity of the algorithm is also easy to estimate. Observe that assuming that all children of a vertex v are already addressed, the additional time required to compute all terms

related to v is O(d + v k 2 ).
A simple induction implies that the dynamic programming algorithm has a complexity of O(nk 2 ).

Since paths are also trees, the algorithm described for trees can also be used.

The problem for cycles can also be solved using dynamic programming. If there are vertices with negative weights then they belong to the k-separator. By deleting these vertices we get a set of subpaths. Then we can use dynamic programming to solve the problem on each subpath. If all vertices have strictly positive weights and the size of the cycle is less than or equal to k, then the optimal separator is the empty set. Finally, if weights are positive and the size of the cycle is strictly greater than k, then we select a connected subset of k + 1 vertices and we solve k + 1 path problems by deleting from the cycle one vertex belonging to this subset.

Proposition 3.2

The k-separator problem can be solved in polynomial time for trees and cycles. This holds even if k is not constant.

mK 2 -free graphs

Before presenting mK 2 -free graphs, let us introduce a construction G ⋆ from G allowing to transform the k-separator problem into a maximum weight stable set problem.

Given a vertex-weighted graph G, we build a vertex-weighted extended graph

G ⋆ = (V ⋆ , E ⋆ ) as follows. Each subset of vertices S ⊂ V such that 1 ≤ |S| ≤
k and G(S) is connected, is represented by a vertex in G ⋆ . In others words, Let R be a maximum-weight stable set of G ⋆ . If two vertices S ∈ V ⋆ and T ∈ V ⋆ belong to this stable set R, then S ∩ T = ∅ and there are no edges in G with one endvertex in S and another endvertex in T . In other words, if we consider ∪ S∈R S, we get a set of vertices in V inducing a subgraph where each connected component has a size less than or equal to k. The complementary set of ∪ S∈R S in V is a kseparator for the graph G. This graph construction can be seen as a generalization of a construction proposed by [START_REF] Rautenbach | Some results on graphs without long induced paths[END_REF] for the dissociation problem (k = 2).

V ⋆ = {S ⊂ V, |S| ≤ k, G(S) is connected}. The set of edges is defined as fol- lows: E ⋆ = {(S, T ), S ∈ V ⋆ , T ∈ V ⋆ , S = T,
Let us now assume that G does not contain an induced matching of size m where m is a constant. This is equivalent to say that G is mK 2 -free.

It is shown in [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] that the dissociation problem is easy to solve in this case.

Remember that the last is equivalent to the k-separator problem with k = 2. We generalize this result for any constant k.

Proposition 3.3

The k-separator problem can be solved in polynomial time for mK 2 -free graphs if we assume that m and k are constants.

Proof: we consider again the extended graph G ⋆ . Since k is a constant, G ⋆ has a polynomial size. We know from [START_REF] Balas | On graphs with polynomially solvable maximum-weight clique problem[END_REF] that the stable set problem can be solved in polynomial time if the graph is mK 2 -free. It is then enough to prove that G ⋆ is

mK 2 -free if G is mK 2 -free.
Suppose that G ⋆ contains an induced matching of size m. Consider an edge (u, w) Moreover, given two edges of the induced matching (u 1 , w 1 ) and (u 2 , w 2 ), then each vertex in V u 1 ∪ V w 1 is not adjacent to any vertex in V u 2 ∪ V w 2 (otherwise, the matching is not an induced one). Consequently, the graph G contains an induced matching of size m. This concludes the proof.

(G 1 , G 2 , G 3 , P 6 )-free graphs

Let G 1 be the chair graph (or fork) obtained from the claw by a single subdivision of one if its edges. G 1 is represented on the left of Figure 3.1. It is proved in [START_REF] Milanic | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF] that the maximum weight stable set problem can be solved in polynomial time if the graph is G 1 -free. Their result is an improvement of the classical result of [START_REF] Sbihi | Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile[END_REF][START_REF] Minty | On maximal independent sets of vertices in claw-free graphs[END_REF] related to claw-free graphs since the class of G 1 -free graphs includes the class of claw-free graphs. Proof: It is easy to check that if G contains one of the graphs G 1 , G 2 , G 3 and P 6 as an induced graph, then G ⋆ contains G 1 . Let us do it for P 6 . Assume that the vertices of P 6 are {1, 2, ..., 6} and let

When k = 2, it is proved in [90] that the graph G ⋆ is G 1 -free if and only if G is (G 1 , G 2 , G 3 )-
V 0 = {2, 3, 4}, V 1 = {1}, V 2 = {3}, V 3 = {5}
and V 4 = {6}. Each subset V i (i = 0, .., 4) induces a connected graph of G with at most k vertices. Considering V i (i = 0, .., 4) as vertices of G ⋆ , the graph induced by {V 0 , V 1 , V 2 , V 3 , V 4 } is clearly a chair. The same kind of constructions can be exhibited for G 1 , G 2 and G 3 .

Let us now assume that G ⋆ contains G 1 . We should prove that G necessarily contains one of the graphs G 1 , G 2 , G 3 and P 6 as an induced graph. Among all chairs included in G ⋆ , consider a chair induced by

{V 0 , V 1 , V 2 , V 3 , V 4 } such that |V 0 | + |V 1 | + |V 2 | + |V 3 | + |V 4 | is minimum.
We assume that V 0 is the central vertex of the chair while V 4 is adjacent to V 3 and not adjacent to V 0 .

Since V 1 only has to be connected to V 0 in G ⋆ , there is no need for V 1 to contain more than one vertex. This holds also for V 2 . Moreover, V 4 must be adjacent to Suppose that |V 3 | ≥ 2. If all vertices of V 3 are adjacent to V 0 , then consider a vertex a ∈ V 3 that is also adjacent to v 4 . Observe that we could choose V 3 = {a} to still obtain an induced chair in G ⋆ . This contradicts the minimality of i=4 i=0 |V i |. Let us now assume that there are vertices in V 3 that are not adjacent to V 0 . Then, there are at least two adjacent vertices a and b of V 3 such that a is adjacent to V 0 while b is not adjacent to V 0 . By taking V 3 = {a} and V 4 = {b} without changing V 0 , V 1 and V 2 , we clearly obtain a chair in G ⋆ violating the minimality condition.

Consequently, we necessarily have |V 3 | = 1. Similarly to the other subsets, V 3 is denoted by {v 3 } where v 3 ∈ V . The only subset V i that might have more than one

vertex is V 0 . Notice that since |V 4 | = |V 3 | = 1 and V 4 is not adjacent to V 0 , we should also have V 3 ∩ V 0 = ∅.
We will now study all possible situations depending on V 0 and how it is connected

to V 1 , V 2 and V 3 . Case 1 . If |V 0 | = 1, then G(V 0 ∪ {v 1 , v 2 , v 3 , v 4 }) is clearly a chair.
assumption.

-Let us now assume that v 1 is only adjacent to b (and not to a).

Then, if v 2 is only adjacent to a, G(V 0 ∪ {v 1 , v 2 , v 3 }) is isomorphic to G 1 .
On the contrary, if v 2 is adjacent to both a and b, then

G(V 0 ∪ {v 1 , v 2 , v 3 , v 4 }) is isomorphic to G 3 . Finally, if v 2 is only adjacent to b, then G(V 0 ∪ {v 1 , v 2 , v 3 }) is isomorphic to G 1 .
Case 4 . Let us now assume that 3 ≤ |V 0 | ≤ k and G(V 0 ) is a tree having at least 3 leaves (vertices of degree 1 in the tree). The minimality assumption require that for each leaf, there is a subset V i (i ∈ {1, 2, 3}) such that V i is only adjacent to this leaf (otherwise, we could reduce the size of V 0 by delete this leaf). This implies that the number of leaves is exactly equal to 3. Let x 1 be the unique leaf adjacent to v 1 . By taking V 1 = {x 1 }, V 0 = V 0 \ {x 1 } (observe that V 0 is still connected) without changing the other subsets, we obtain a chair in G ⋆ contradicting the minimality assumption.

Case 5 . Suppose that 3 ≤ |V 0 | ≤ k and G(V 0 ) is a simple path. For each one of the two leaves, there is at least one subset V i (i ∈ {1, 2, 3}) such that V i is only adjacent to this leaf. For symmetry reasons, we can assume without loss of generality that v 1 is only adjacent to x 1 (so x 1 is a leaf). Observe that this implies that v 1 / ∈ V 0 . Let x 2 (resp.x 3 ) be a vertex of V 0 such that v 2 (resp. v 3 ) is adjacent to x 2 (resp. x 3 ). We will study all possible situations depending on the positions of x 2 and x 3 .

Subcase 5.1 . Assume that x 2 ∈]x 1 , x 3 [. Then x 3 is the second leaf of the path. By the minimality assumption, x 3 is not adjacent to V 0 \ {x 3 } (otherwise |V 0 | can be reduced by eliminating x 3 ). Suppose that there is a vertex y ∈ [x 1 , x 3 [ such that v 2 and y are not adjacent. Then, but taking

V 1 = {y}, V 0 =]y, x 3 ]
without changing the other subsets, we get a chair in G ⋆ contradicting the minimality assumption. Then, v 2 is adjacent to all vertices of [x 1 , x 3 [. In a similar way, one can prove that v 2 is adjacent to x 3 . In other words, v 2 is adjacent to all vertices of V 0 . One can see

now that G({v 1 , x 1 , v 2 , x 3 , v 3 , v 4 }) is isomorphic to P 6 .
Subcase 5.2 . Assume that x 2 = x 1 . To avoid the previous subcase, we should also assume that v 2 is not adjacent to V 0 \ {x 2 = x 1 }. Remember that Consider a collection of intervals on a line L. Suppose that for each interval, we are given a curve above the line, connecting the endpoints of the interval, and remaining within the limits of the interval. An interval-filament graph (see figure 3.2) is the intersection graph of such a collection of intervals [START_REF] Gavril | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF]. Computing a maximum weight stable set in interval-filament graph can be done in polynomial time [START_REF] Gavril | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF]. It is proved in [START_REF] Hell | Independent packings in structured graphs[END_REF] that if G is an interval-filament graph, then H(G) is also an interval-filament graph. In other words, the class of interval-filament graphs is closed under the operation G → H(G). Notice that the class of interval-filament graphs includes polygon-circle graphs and cocomparability graphs.

The same was also proved in [START_REF] Hell | Independent packings in structured graphs[END_REF] for the class of weakly chordal graphs [START_REF] Hayard | Weakly triangulated graphs[END_REF] (graphs such that neither the graph nor its complement contain an induced cycle on 5 or more vertices, see figure 3.4) and the class of asteroidal triple-free graphs (graphs not containing an asteroidal triple defined as a stable set of 3 vertices such that between each pair of vertices of this triple, there is path connecting them and avoiding the neighborhood of the third vertex, see figure 3.3). We know from [START_REF] Müller | Independent sets in asteroidal triple-free graphs[END_REF] that the maximum weight stable set problem can be solved in polynomial time for asteroidal triple-free graphs. The same holds for weakly chordal graphs (see, e.g., [START_REF] Sritharan | Algorithms for weakly triangulated graphs[END_REF]).

Let us now go back to our k-separator problem and let us slightly change the definition of H by allowing it to depend on G. More precisely, let H be the set of all connected subgraphs of G containing at most k vertices. Then, H(G) is exactly our graph G ⋆ . Consequently, the results of [START_REF] Hell | Independent packings in structured graphs[END_REF] can be directly applied here to deduce that the problem is easy to solve. We only have to ensure that the size of G ⋆ = H(G) is polynomially bounded. This of course occurs if k is a constant.

Proposition 3.5 Assuming that k is a constant, the k-separator problem can be solved in polynomial time for interval-filament, asteroidal triple-free and weakly chordal graphs.

Interval and circular-arc graphs

Interval graphs are graphs where a vertex corresponds to an interval and an edge (u, v) exists if there is a non-empty intersection between the intervals represented by u and v, see figure 3.5. We prove below that the k-separator problem is easy to solve for interval graphs.

Interval graphs are obviously interval-filament and are also chordal. So the results of Section 3.6 can be applied here to deduce that the k-separator problem can be solved in polynomial-time for this class of graphs. However, in Section 3.6, k is required to be constant. This was necessary to get a graph G ⋆ with a polynomial size. We will prove in this section that the problem is easy to solve even if k is part

v ∈ V satisfying [a v , b v ] ⊂ [x, y]
and a v = c j . In this case, let j + δ(j) be the index such b v = c j+δ(j) . Thus, if j ∈ O, then 1 ≤ δ(j) ≤ rj. The simple observation made above directly leads to a dynamic programming approach. To make things more precise, let us introduce further notation. Let i 0 and i 1 be two integer numbers such that 1 ≤ i 0 ≤ i 1 ≤ r. For any integer number 1 ≤ l ≤ k, let f (i 0 , i 1 , l) be the maximum weight that we can have to cover the

interval [c i 1 , y] using at most l intervals among {[a w , b w ] : w ∈ V, c i 0 ≤ a w , b w ≤ y}. If i 1 < r, it is clear that to cover [c i 1 , y],
we need at least one interval belonging to {[a w , b w ] : w ∈ V, c i 0 ≤ a w , b w ≤ y}. This clearly leeds to the following induction formula:

f (i 0 , i 1 < r, l) = max j∈O:i 0 ≤j≤i 1 w [c j ,c j+δ(j)) ] + f (j + 1, max (j + δ(j), i 1 ) , l -1) . (3.6) If O ∩ {i 0 , i 0 + 1, ..., i 1 < r} = ∅, then f (i 0 , i 1 < r, l) = -∞. If l = 0, we also have f (i 0 , i 1 < r, 0) = -∞.
If i 1 = r, then y = c r is already reached. The induction formula is then given by: f (i 0 , r, l) = max 0, max j∈O:i 0 ≤j≤r w [c j ,c j+δ(j)) ] + f (j + 1, r, l -1) .

(3.7)

Conclusion

Problem (3.5) is solved by computing f (1, 1, k). The complexity of the dynamic programming algorithm is obviously given by O(kn 3 ).

Proposition 3.6

The k-separator problem can be solved in polynomial time for interval graphs. This holds even if k is not constant.

Proof:

We already observed that the size of the graph G ⋆⋆ is polynomially bounded.

Since problem (3.5) can be solved in polynomial time, the weight of each vertex of G ⋆⋆ is easy to compute. Then, we only have to solve the maximum weight stable set problem in G ⋆⋆ . Using the fact that this problem is easy to solve for interval graphs, concludes the proof.

Circular-arc graphs are a simple generalization of interval graphs. They are defined by the intersection graphs of a set of arcs on the circle. The previous proposition and the algorithm described in the proof of Lemma 3.1 can be generalized in an obvious way.

Proposition 3.7

The k-separator problem can be solved in polynomial time for arccircular graphs. This holds even if k is not constant.

Conclusion

Many cases where the k-separator problem can be solved in polynomial time are

shown in this chapter. In the next chapter many integer formulations of the kseparator problem will be investigated.

Chapter 4

Integer Formulations

Introduction

This chapter is organized as follows. In the section 4.2, we present a basic formulation in the space of original variables indexed on the vertices of graph G. We study, in the section 4.3, a stable set formulation based on a graph transformation.

The section 4.4 focuses on a metric formulation containing among these, triangle inequalities. A projected metric formulation is presented in section 4.5. The section 4.6 presents partitioning formulations containing variables associated with a partition of the vertex set. We conclude in the last section.

Basic formulation

Basic formulation

Let S be a subset of vertices such that |S| = k + 1 and G(S) is connected. Then, the following inequality is obviously valid for S k (G).

v∈S x v ≥ 1. (4.1)
The k-separator problem can be formulated as the following integer program:

IP 1        min v∈V w v x v v∈S x v ≥ 1, ∀S ⊂ V, |S| = k + 1, G(S)connected x v ∈ {0, 1}, ∀v ∈ V
Let LP 1 denote the linear relaxation of IP 1. We will see in Section 6.2 that inequalities (4.1) are generally difficult to separate when k is part of the input.

Stable set formulations

These formulations are based on the G ⋆ construction of Section 3.4. Remember

that V ⋆ = {S ⊂ V : |S| ≤ k, G(S) is connected} and E ⋆ = {(S, T ) : S ∈ V ⋆ , T ∈ V ⋆ , S = T, such that either S ∩ T = ∅, or (u, v) ∈ E for some u ∈ S and v ∈ T }.
The connection with the stable set problem made in Section 3.4 directly leads to the following formulation.

IP 2                min v∈V w v x v x v = 1 - S∈V ⋆ :v∈S y S , ∀v ∈ V y S ∈ {0, 1}, ∀S ∈ V ⋆ y S + y T ≤ 1, ∀S ∈ V ⋆ , T ∈ V ⋆ , (S, T ) ∈ E ⋆ Let Q v = {S ∈ V ⋆ : v ∈ S}.
One can add to IP 2 the obvious valid inequalities S∈Qv∪Qw y S ≤ 1, ∀ (v, w) ∈ E. The number of these inequalities is (|E|). This leads to formulation IP 3.

IP 3                  min v∈V w v x v x v = 1 - S∈Qv y S , ∀v ∈ V S∈Qv∪Qw y S ≤ 1, ∀ (v, w) ∈ E y S ∈ {0, 1}, ∀S ∈ V ⋆
Let LP 3 denote the linear relaxation of IP 3. Let F 1 (resp. F 3) be the set of feasible solutions of LP 1 (resp. LP 3) with respect to variables (x v ) v∈V . Let T denote a spanning tree of C (in the original graph) and consider the following quantity:

(v,w)∈T S∈Qv∪Qw y S . Notice that in the last expression, the number of times a variable y S occurs is equal to the number of edges of T that intersect with S, and thus is larger than or equal to |S ∩ C|. From this we deduce that v∈C S∈Qv y S ≤ (v,w)∈T S∈Qv∪Qw y S . Moreover, using the feasibility of (x, y), we can write that (v,w)∈T S∈Qv∪Qw y S ≤ k.

Combining the two previous inequalities leads to v∈C S∈Qv y S ≤ k. Consequently, inequality v∈C x v ≥ 1 holds. In other words, x is a feasible solution of LP 1.

Metric formulations

A metric formulation is proposed in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. In addition to variables (x i ) i∈V , we consider a variable x ij for each pair of vertices {i, j} to indicate whether i and j belong to the same component. More precisely, x ij is equal to 0 if they are in the same component. Then triangle inequalities are clearly valid. Moreover, to express the fact that a connected component does not contain more than k vertices, we can add the constraints j∈V \{i}

x ij ≥ nk, ∀ i ∈ V . Finally, we must add constraints to impose that if two adjacent vertices are not in the k-separator, then they belong

Metric formulations

to the same component:

x i + x j -x ij ≥ 0, ∀ (i, j) ∈ E. The formulation is given below. IP 4                            min v∈V w v x v x ij ≤ x ik + x jk , ∀i, j, k ∈ V j∈V \{i} x ij ≥ n -k, ∀ i ∈ V x i + x j -x ij ≥ 0, ∀ (i, j) ∈ E 0 ≤ x ij ≤ 1, ∀i, j ∈ V x i ∈ {0, 1}, ∀i ∈ V
Observe that the x ij variables are not required to be integer. In fact, as noticed in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF], relaxing the integrity constraint of x ij variables does not modify the solution of IP 4. The polytope related to formulation IP 4 is studied in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] and many valid inequalities and facets are presented there. Since some of these inequalities are also valid for S k (G), they will be presented in Section 5.4.

Let us present a new way to strengthen the linear relaxation of IP 4. First, constraint j∈V \{i}

x ij ≥ n -k can obviously be strengthened into j∈V \{i} x ij ≥ n -k + (k -1)x i .
Let p be any simple path joining i and j. Remember that x(p) denotes the sum of x v values for all vertices belonging to p (including i and j). It is clear that

x(p) ≥ x ij is a valid inequality: if x(p) = 0, then all vertices of p do not belong to the k-separator, so they will be in the same component implying that x ij = 0. Let IP 5 be the obtained integer formulation and let LP 5 be its linear relaxation.

LP 5                      min v∈V w v x v j∈V \{i} x ij ≥ n -k + (k -1)x i , ∀ i ∈ V x(p) -x ij ≥ 0, ∀ i, j ∈ V , p ∈ P ij 0 ≤ x ij ≤ 1, ∀i, j ∈ V 0 ≤ x i ≤ 1, ∀i ∈ V
Observe that we do not consider triangle inequalities in LP 5. In fact, it is clear that there is nothing against taking x ij = min 1, min p∈P ij x(p) . Triangle inequalities are then naturally satisfied. In other words, adding triangle inequalities does not improve the relaxation.

Notice that constraints x(p)x ij ≥ 0 can be separated by computing shortest paths. We will show in Section 4.5 that formulation LP 5 can be easily projected on the space of x i variables. Constraints x(p)-x ij ≥ 0 can also be induced by adding for each pair of vertices a variable y ij representing the length of the shortest path between i and j in sense of x v values. Then, we should write that y ij = x i + x j if i and j are adjacent, and

y ij ≤ x i + y kj if (i, k) ∈ E.
For more clearness, we give below the new compact linear formulation.

LP 6                                  min v∈V w v x v j∈V \{i} x ij ≥ n -k + (k -1)x i , ∀ i ∈ V y ij = x i + x j , ∀ (i, j) ∈ E y ij ≤ x i + y kj , ∀ i, j ∈ V, (i, k) ∈ E y ij -x ij ≥ 0, ∀ i, j ∈ V 0 ≤ x ij ≤ 1, 0 ≤ y ij , ∀i, j ∈ V 0 ≤ x i ≤ 1, ∀i ∈ V
LP 5 and LP 6 are obviously equivalent.

Projected metric formulation

Let S be a set of vertices with |S| ≥ k and let i ∈ S. For each j ∈ S, let p ij ∈ P ij be a path joining i and j. Notice that p ij \ {i} is a path joining j and the neighbor of i in p ij . Consider the following inequality Proof: if x i = 1, then inequality (4.2) obviously holds. Let us now assume that

(|S| + 1 -k)(1 -x i ) ≤ j∈S x(p ij \ {i}).
x i = 0. This is equivalent to say that i does not belong to the k-separator. Let j ∈ S. If there is a path p ij such that x(p ij \ {i}) = 0, then j and i belong to the same connected component after the removal of the k-separator. The number of such vertices is less than or equal to k -1 since i is already in the component. In other words, we necessarily have

(|S| + 1 -k) ≤ j∈S x(p ij \ {i}).

Projected metric formulation

We will show in Section 6.2 that inequalities (4.2) can be separated in polynomial time.

Let us now consider a formulation based on inequalities (4.2).

IP 7          min v∈V w v x v (|S| + 1 -k)(1 -x i ) ≤ j∈S x(p ij \ {i}), ∀i ∈ V, S ⊂ V \ {i}, |S| ≥ k; p ij ∈ P ij , ∀j ∈ S x v ∈ {0, 1}, ∀v ∈ V Lemma 4.2 Formulation IP 7 is exact.
Proof: The solution of IP 7 is integer. Since we already proved the validity of inequalities (4.2), we do not eliminate the incidence vector of any k-separator. To prove the exactness of IP 7, it is enough to prove that v∈S ′ x v ≥ 1 for any subset

S ′ ⊂ V with |S ′ | = k + 1 and G(S ′ ) connected.
Let us consider such a subset S ′ and let i be any vertex of S ′ . For each j ∈ S = S ′ \ {i}, let p ij be a path joining i and j and contained in G(S ′ ) (this is possible by the connectivity of G(S ′ )).

If x i = 1, then v∈S ′ x v ≥ 1 is clearly satisfied.
Let us now assume that x i = 0.

Inequality (4.
2) in addition to the integrity constraint imply that x(p ij \ {i}) ≥ 1 for some j ∈ S. Since all vertices of p ij \ {i} are inside S ′ , this leads to v∈S ′ x v ≥ 1.

Let LP 7 be the linear relaxation of IP 7.

Proposition 4.2 Formulation LP 7 is equivalent to formulations LP 5 and LP 6. It is then stronger than formulation LP 4.

Proof: We know that LP 5 and LP 6 are equivalent. They both dominate LP 4. Let us then prove that LP 7 is equivalent to LP 5.

Let x ⋆ be an optimal solution of LP 7. Let x ⋆ ij = min 1, min

p∈P ij x ⋆ (p) for i ∈ V , j ∈ V \ {i}. Then, inequalities x(p) -x ij ≥ 0 are naturally satisfied for any path p ∈ P ij .
Let i be any vertex and let S be the subset of vertices such that x ⋆ ij < 1. Thus, if j ∈ S, there exists a path

p ij ∈ P ij such that x ⋆ (p ij ) = x ⋆ ij . Using the fact that x ⋆ is a solution of LP 7, one can write that (|S| + 1 -k)(1 -x ⋆ i ) ≤ j∈S x ⋆ (p ij \ {i}) = j∈S (x ⋆ ij -x ⋆ i ). Consequently, we have j∈S x ⋆ ij ≥ (|S| + 1 -k) + (k -1)x ⋆ i . Moreover,
we know by the definition of S that x ⋆ ij = 1 if j ∈ S. Then, the last inequality is equivalent to

j∈V \{i} x ⋆ ij ≥ (n -k) + (k -1)x ⋆ i .
Consequently, all constraints of LP 5 are satisfied.

Let us now prove the opposite sense by considering an optimal solution of LP 5 defined by (x ⋆ i ) i∈V and (x ⋆ ij ) i,j∈V . Let i be an arbitrary vertex, S be a subset of vertices of V \ {i} of cardinality at least k, and p ij ∈ P ij be an arbitrary path joining i and j for each j ∈ S. We aim to prove that inequality (4.2) is satisfied. Since we are considering a solution of LP 5, we can write that

j∈S x ⋆ (p ij ) ≥ j∈S x ⋆ ij = j∈V \{i} x ⋆ ij - j∈V \{i}∪S x ⋆ ij . Using the fact that j∈V \{i} x ⋆ ij ≥ (n -k) + (k -1)x ⋆ i ,
and

j∈V \{i}∪S x ⋆ ij ≤ n -1 -|S|, the previous inequality becomes j∈S x ⋆ (p ij ) ≥ (k -1)x ⋆ i + (|S| + 1 -k) which is exactly inequality (4.2)
. Notice that it is not difficult to show that there is not any general domination result relating LP 7 and LP 1 (no formulation is dominating the other one in general). This can also be deduced from the results of Chapter 6 where we see that inequalities (4.2) and inequalities (4.1) induce facets under some conditions.

Partitioning formulations

Another natural formulation for the k-separator problem can be inspired from partitioning or clustering problems [START_REF] Vanelli | Grouping parts and components in flexible manufacturing systems[END_REF][START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. Let B be an upper bound of the number of connected components that will be obtained after the removal of the k-separator.

B can be, for example, equal to n. Components are then numbered from 1 to B.

A variable z ib is considered for each vertex i and each component b ∈ {1, ..., B}. z ib will be equal to 1 if i belongs to component b. The formulation follows.

IP 8                        min i∈V w i x i x i + B b=1 z ib = 1, ∀i ∈ V i∈V z ib ≤ k, ∀b ∈ {1, ..., B} z ib + z jb ′ ≤ 1, ∀(i, j) ∈ E, b, b ′ ∈ {1, ..., B}, b = b ′ x i ∈ {0, 1}, z ib ∈ {0, 1}, ∀i ∈ V, b ∈ {1, ..., B}
The first set of constraints expresses the fact that a vertex i either belongs to the k-separator (x i = 1) or to one of the remaining components. The second set of constraints allows to bound the size of each component, while constraints 4.6. Partitioning formulations z ib +z jb ′ ≤ 1 guarantee that adjacent vertices do not belong to different components.

In fact, constraints z ib + z jb ′ ≤ 1 are dominated by constraints z ibz jb ≤ x j for any (i, j) ∈ E and b ∈ {1, ..., B}. Another compact exact formulation can then be obtained.

IP 9                        min i∈V w i x i x i + B b=1 z ib = 1, ∀i ∈ V i∈V z ib ≤ k, ∀b ∈ {1, ..., B} z ib -z jb ≤ x j , ∀(i, j) ∈ E, b ∈ {1, ..., B} x i ∈ {0, 1}, z ib ∈ {0, 1}, ∀i ∈ V, b ∈ {1, ..

., B}

A further improvement is obtained by considering a subset U ⊂ {1, ..., B}, its complement U and two adjacent vertices i and j: b∈U

z ib + b∈U z jb ≤ 1, ∀(i, j) ∈ E. (4.3)
We will see in Section 6.2 that inequalities (4.3) can be separated in polynomial time.

Let us now go back to the definition of B. Remember that B is an upper bound of the number of remaining components after the removal of the k-separator. It is clear that we should take B as small as possible to improve the quality of the relaxations. The maximum number of connected components that can be obtained after the deletion of a k-separator is in fact exactly equal to the maximum size of a stable set in G ⋆ (defined in Section 3.4). We show below that this number is in fact exactly equal to the maximum size of a stable set in G.

Proposition 4.3

The lowest upper bound B that can be considered in formulations IP 8 and IP 9 is equal to the maximum size of a stable set in G Proof: Since G is included in G ⋆ , the maximum size of a stable set in G ⋆ is larger than or equal to the maximum size of a stable set in G. Consider a stable set of G ⋆ .

Each vertex S ∈ V ⋆ belonging to the stable set corresponds to a subset of vertices of G. Let us pick an arbitrary vertex v S from each S. Consider any pair of vertices S and S ′ of the stable set. v S and v S ′ are necessarily not adjacent in G since S and S ′ are not adjacent in G ⋆ . This clearly implies that G contains a stable set whose size is equal to the size of the stable set of G ⋆ .

Introduction

This chapter is dedicated to a polyhedral study of S k (G). We will first present some properties of this polytope. Then we will focus on the path and cycle cases. Finally, several valid inequalities will be presented and studied.

Some general properties

of nodes V a corresponding to the support of the vector a contains a connected component with size at least k + 1. (For, if G a would not contain a component with size at least k + 1, considering the set of nodes V \ V a : it corresponds to a k-separator, thus a contradiction with the validity of the inequality).

Assume that the subgraph G a contains a component C with size at most k.

Then any k-separator S whose incidence vector saturates the constraint a t x ≥ α should verify v w = 0, ∀w ∈ C. So the face defined by the inequality a t x ≥ α would be contained in faces defined by trivial inequalities: a contradiction.

Finally assume that G a contains two components C 1 , C 2 with size at least k + 1.

Let S and S ′ denote two k-separators whose incidence vectors saturate the inequality

a t x ≥ α, with v∈S∩C 1 a v = k 1 and v∈S ′ ∩C 1 a v = k ′ 1 . Assuming k 1 > k ′ 1 (the case k 1 < k ′ 1 can be treated similarly) we have v∈S\C 1 a v < v∈S ′ \C 1 a v . Now consider the node set W = (S \ C 1 ) ∪ (S ′ ∩ C 1 ) ∪ (V \ V a ). W is a k-separator satisfying v∈W a v < v∈S a v ,
thus contradicting the validity of the inequality a t x ≥ α.

It follows that the inequality a t x ≥ α is redundant with respect to inequalities associated with each connected component of G a (which are of the form v∈C a v x v ≥ k c , where k c denotes the value v∈S∩C a v , with S as defined above).

The following proposition characterizes when a facet defining inequality for S k (G) is also facet defining for S k (G ′ ), where G ′ is obtained from G by adding a vertex (and a set of edges between this additional vertex and vertices in G).

Proposition 5.5 Let a t x ≥ b define a facet of the k-separator polytope S k (G) with

G = (V, E). Let G ′ = (V ′ = V ∪ {v}, E ′
) denote a graph obtained from G by adding a node v and some edges of the form vw, w ∈ V . Then the inequality a t x ≥ b defines a facet of S k (G ′ ) iff there exists a k-separator S ⊆ V in G ′ whose incidence vector

χ(S) ∈ R |V | satisfies a t χ(S) = b.
Proof: Notice firstly that if a t x ≥ b defines a facet of the k-separator polytope

S k (G) then it is valid for S k (G ′ ). (For, if S ⊆ V ′ is a k-separator in G ′ then S ∩ V is a k-separator in G).
[⇒] By contradiction. Assuming such a k-separator S ⊆ V does not exist, then the face of S k (G ′ ) that is defined by a t x ≥ b is contained in the one defined by x v ≤ 1 and hence it cannot define a facet of S k (G ′ ).

[⇐] Given a set of |V | k-separators S 1 , . . . , S |V | in G whose incidence vectors (in R |V | ) are affinely independent the sets (S ′ i )

|V | i=1 with S ′ i = S i ∪ {v}, ∀i ∈ {1, . . . , |V |} are k-separators in G ′ .
And adding to this latter set of vectors the incidence vector

χ(S q ) ∈ R |V ′ |
, for some arbitrarily chosen index q ∈ {1, . . . , |V |}, we get a set of |V ′ | incidence vectors of k-separators in G ′ that are affinely independent.

Proposition 5.6 Let a t x ≥ b, x ∈ R |V | define a facet F for S k (G). Given x ∈ R |V | , let x ′ ∈ R |V ′
| denote the restriction of x to the entries corresponding to nodes in the node subset V ′ = V \ {v}, for some node v ∈ V such that a v = 0. Then the set

F ′ = {x ′ ∈ S k (G ′ ) : x ∈ F } contains |V ′ | affinely independent incidence vectors of k-separators in G ′ : the subgraph of G that is induced by the node set V ′ .
Proof: Let A ∈ {0, 1} m×|V | be a matrix whose rows correspond to all the incidence

vectors of k-separators in G that are in F = {x ∈ S k (G) : a t x = b}. Since F is facet defining for S k (G) and S k (G) is full-dimensional, A contains |V | affinely independent
rows. Let A ′ be obtained from A by dropping the column corresponding to node v and assume A ′ contains at most |V | -2 affinely independent rows. This implies that

F ′ = {x ∈ S k (G ′ ) : a t x = b} is not a facet of S k (G ′ ).
Thus, there exists an inequality Then it is also facet defining for S k (G ′ ) where

c t x ≥ d that is valid for S k (G ′ ) and such that F ′ ⊆ F ′′ = {x ∈ S k (G ′ ) : c t x = d} with (c, d) that is
G ′ = (V ′ , E ′ ) denotes the subgraph of G that is induced by the node set V ′ ⊆ V and such that a v = 0, ∀v ∈ V \ V ′ .
Proof: Iterative application of Proposition 5.6, removing nodes of G that are not in V ′ .

The path and cycle cases

Let us assume that G = (V, E) is a path where

V = {v 1 , v 2 , ..., v n } and E = {(v 1 , v 2 ), ..., (v n-1 , v n )}. The connected components of size k + 1 considered in LP 1
are denoted by S 1 , ..., S i , ...S n-k , where S i = {v i , v i+1 , ..., v i+k }. The constraints of LP 1 related to large connected components can be written in the matrix form Ax ≥ 1, where the i th row of A corresponds to the incidence vector of S i .

The path and cycle cases

Proposition 5.7 If G is a path, then formulation LP 1 is exact (the extreme solutions of LP 1 are optimal k-separators).

Proof: We can write LP 1 as {min wx :

Ax ≥ 1, 0 ≤ x v ≤ 1, v ∈ V }. Consider-
ing the matrix B where the first nk rows correspond to matrix A, the next n rows correspond to the identity matrix of dimension n and the last n rows correspond to the opposite of the identity matrix. It is clear that all constraints of LP 1 can be summarized in the form Bx ≥ b where b is an integer vector. Using the fact that interval matrices are totally unimodular, we deduce that B is also totally unimodular [4,[START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]. This terminates the proof.

Knowing that the problem can be solved in polynomial-time for trees, one may look for a polyhedral description in this case. In fact, inequalities (4.1) considered in (IP 1) can be separated in polynomial time using the algorithm proposed in [START_REF] Hochbaum | K-edge subgraphs problems[END_REF] to find a maximum-weight connected subgraph of a given size when the graph is a tree. However, these inequalities are generally not sufficient to describe the convex hull of the incidence vectors of k-separators. A complete description of S k (G) in the tree case is still an open question.

Let us now assume that G = (V, E) is a cycle where V = {v 1 , v 2 , ..., v n } and

E = {(v 1 , v 2 ), ..., (v i , v i+1 ), ..., (v n-1 , v n ),(v n , v 1 )}.
It is clear that if we know that x v i = 1 for some vertex v i (i.e., v i belongs to the k-separator), then any k-separator of the cycle should contain a k-separator of the path V \ v i . Using Proposition 5.7, we deduce that a minimum-weight k-separator containing vertex v i can be computed by solving the following linear program LP i .

LP i                    min v∈V w v x v s.t. : v∈S x v ≥ 1 ∀ |S| = k + 1, G(S) connected and v i 0 / ∈ S 0 ≤ x v ≤ 1 ∀v ∈ V x v i = 1
Let P i be the polytope corresponding to the feasible region of the formulation

LP i . Then, P i = conv{χ (S) ∈ {0, 1} n , S is a k-separator containing v i }.
Let T be an arbitrary subset of vertices such that |T | = k + 1 and G(T ) is connected. Since at least one vertex of T belongs to the k-separator, we can write that S k (G) =

conv{ v i ∈T P i }.
Using the projection result of Balas [5], we get the following equivalent formulation for the k-vertex separator problem when the graph is a cycle:

                         min v∈V w v x v s.t. : x = i∈T z i 0 ≤ z i j ≤ z i i ∀v i ∈ T, v j ∈ V v j ∈S z i j ≥ z i i ∀ |S| = k + 1, G(S) connected, and v i ∈ T \ S v i ∈T z i i = 1
In the formulation above, z i is a vector of dimension n whose components are given by z i j for v j ∈ V .

Let us now focus on some special cases. Let C k denote a cycle with length k.

Proposition 5.8 S k (C k+1 ) = {x ∈ [0, 1] k+1 : i x i ≥ 1}
Proof: Constraint matrix is TU.

The formulations for S k (C k+1 ) and S k (P k+1 ) are the same (where P k+1 stands for an elementary path obtained from C k+1 by removing an edge).

Proposition 5.9 S k (C k+2 ) = {x ∈ [0, 1] k+2 : i x i ≥ 2}
Proof: Constraint matrix is TU.

Note that differently from the case of C k+1 , the formulations of S k (C k+2 ) and S k (P k+2 ) do not coincide (since the constraint i x i ≥ 2 is not valid for S k (P k+2 )).

For the particular case of C 5 and k = 2 the following proposition shows that the addition of the constraints on all paths with length k + 1 provides an exact formulation.

Proposition 5.10 S 2 (C 5 ) = {x ∈ [0, 1] k+1 : i x i ≥ 2, i∈p x i ≥ 1, ∀p ∈ P 3 }
, where P 3 stands for the set of all the paths on C 5 with length 3.

Proof: Let a t x ≥ α denote a facet defining inequality for S 2 (C 5 ) which is different from the trivial inequalities. From Proposition 5.3, we have a v ≥ 0, ∀v ∈ V and α > 0. We consider two cases. case 1 : there exists a node w ∈ V with a w = 0. From Corollary 5.1 the inequality a t x ≥ α must be facet defining for S 2 (P 4 ) where P 4 stands for the graph 5.4. Valid inequalities for S k (G) obtained from C 5 by removing the node w: hence a path with 4 nodes. From Proposition 5.7 it follows that a t x ≥ α is an inequality of the form v∈P x v ≥ 1 where P stands for a path with 3 nodes that is contained in C 5 . case 2 : a v > 0, ∀v ∈ V . Let S ⊆ V denote a k-separator whose incidence vector saturates the inequality. Then necessarily S is a minimal (w.r.t. inclusion) k-separator and it follows that S must consist of 2 nonadjacent nodes of C 5 .

There exists exactly 5 such sets for C 5 and writing the saturation of the inequality for all these sets we derive that a v = a w , ∀v, w ∈ V . Hence a t x ≥ α must correspond to the inequality i∈V x i ≥ 2 up to multiplication by a positive scalar. Proof: Let us build n affinely independent vectors related to k-separators and saturating inequality (4.1). For each vertex w ∈ S, we consider a k-separator incidence vector where x w = 0, x v = 1 for each v ∈ S (v = w), and x v = 0 for each v ∈ S except for one vertex v that is a neighbor of w (if w does not have neighbors, the vertex v such that x v = 1 is chosen arbitrarily in S). In this way, we obtain n -|S| vectors saturating (4.1). The remaining |S| vectors are built as follows. For each vertex v ∈ S, we consider the vector where x v = 1, x w = 0 for w ∈ S \ {v}, and x w = 1 for any w ∈ S.

It is now easy to see that the n vectors correspond to k-separators and are affinely independent. First, for each v ∈ S, there is only one vector such that x v = 0.

Second, among the last |S| vectors, for each v ∈ S there is only one vector such that x v = 1. These two observations immediately lead to the affine independence of the n vectors.

If G is a tree and S is a subtree of G, then each vertex v ∈ S has at most one neighbor in G. This leads to the following obvious corollary. Corollary 5.2 If G is a tree, then each inequality (4.1) induces a facet of S k (G).

Connectivity inequalities

Proposition 5.12 Let S ⊂ V be a subset of vertices such that |S| ≥ k + q, q ≥ 1 and G(S) is q-node-connected. Then the following inequality is valid for S k (G):

v∈S x v ≥ q (5.1)
Proof: It is clear that by removing less than k vertices from S, the remaining subgraph is still connected and it contains at least k + 1 vertices. This immediately implies that v∈S x v ≥ q is valid.

Notice that inequalities (5.1) were also considered in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] but in a more restricted form (it is required in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] that

|S| = k + q).
Let us focus on the special case where |S| = k + q. The next result can be seen as a generalization of Proposition 5.11 where q was equal to 1.

Proposition 5.13 Let S ⊂ V be a subset of vertices such that |S| = k + q, q ≥ 1 and G(S) is q-node-connected. Then inequality (5.1) induces a facet of S k (G) if each vertex w ∈ V \ S is adjacent to at most q vertices in S.

Proof: The proof is very similar to the proof of Proposition 5.11. We build n affinely independent vectors related to k-separators and saturating inequality (5.1). For each vertex w ∈ S, we consider a k-separator incidence vector defined as follows. We have

x w = 0 and x v = 1 for each v ∈ S (v = w).
We select a subset of vertices S w ⊂ S of size q containing all neighbors of w in S. Then x v = 1 for any v ∈ S w and x v = 0 for v ∈ S \S w . In this way, we obtain n-|S| vectors saturating (5.1). The remaining |S| vectors are built as follows. Observe that v∈S x v ≥ q induces a facet of S k (G(S)).

This is easy to check: assume that all k-separators saturating inequality (5.1) satisfy the equality v∈S α v x v = β, then by considering two k-separators containing the same subset of vertices of size q -1 and differing in only one vertex, we show that It is now easy to see that the n vectors correspond to k-separators and are affinely independent.

α v = α v ′ for any vertices v, v ′ of S.
If we consider the more restrictive assumption: G(S) is q + 1-node-connected, then the condition related to the number of neighbors in S becomes necessary and sufficient to obtain a facet.

Proposition 5.14 Let S ⊂ V be a subset of vertices such that |S| = k + q, q ≥ 1 and G(S) is q + 1-node-connected. Then inequality (5.1) induces a facet of S k (G) if and only if each vertex w ∈ V \ S is adjacent to at most q vertices in S.

Proof: If each vertex w ∈ V \ S is adjacent to at most q vertices in S, we know from the previous proposition that (5.1) induces a facet of S k (G). Let us now prove that this condition is necessary. Suppose that there is a vertex w ∈ V \ S adjacent to at least q + 1 vertices in S. By removing any subset of nodes of size q from S, we still obtain a connected component of size k (by q + 1-node-connectivity of G(S)). The vertex w has necessarily at least one neighbor in the remaining part of S. This implies that whenever v∈S x v = q, we should have x w = 1. In other words, inequality (5.1) does not induce a facet of S k (G).

Notice that the case where G(S) is a clique was considered in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. Then the previous proposition can be seen as a generalization of the clique case.

Cycle inequalities

Proposition 5.15 Let S be a subset of vertices such that |S| ≥ k + 1 and G(S) is an elementary cycle, then the following inequality is valid for S k (G):

v∈S x v ≥ ⌈ |S| k + 1 ⌉. ( 5
⌈ |S| k+1 ⌉ in G(S ∪ {w}).
Proof: The existence of a k-separator of size ⌈ |S| k+1 ⌉ in G(S∪{w}) is equivalent to say that there are k-separators saturating (5.2) and not containing w. If there is a vertex w ∈ S for which there are no such k-separators, then equality v∈S x v = ⌈ |S| k+1 ⌉ implies that x w = 1. We deduce that the existence of such k-separators is a necessary condition to get a facet.

Let us now assume that the condition is satisfied and let us build n affinely independent vectors related to k-separators and saturating inequality (5.2).

For each vertex w ∈ S, we consider a k-separator incidence vector defined as follows.

We have x w = 0 and x v = 1 for each v ∈ S (v = w). We select a subset of vertices S w ⊂ S of size ⌈ |S| k+1 ⌉ corresponding with a k-separator of G(S ∪ {w}). Then x v = 1 for any v ∈ S w and x v = 0 for v ∈ S \ S w . In this way, we obtain n -|S| vectors saturating (5.2).

To build the remaining |S| vectors, we should first prove that v∈S x v ≥ ⌈ |S| k+1 ⌉ induces a facet of S k (G(S)). Assume that all k-separators saturating inequality (5.2) satisfy the equality v∈S α v x v = β. Given any k-separator of G(S) of size ⌈ |S| k+1 ⌉, there is at least one vertex v belonging to the k-separator such that the next vertex v ′ belonging to the k-separator (when we go through the cycle in the clockwise direction) is situated at a distance less than or equal to k -1. In other words, there is a subset S ′ ⊂ S of size less than or equal to k, containing v and v ′ where both v and v ′ belong to the k-separator. This is true because |S| is not a multiple of k + 1.

It is now clear that if we replace v by the vertex v ′′ preceding v in the cycle (in clockwise direction), we still obtain a k-separator of G(S) of size ⌈ |S| k+1 ⌉. By writing that both the initial and the modified k-separators satisfy equality v∈S α v x v = β, we get that α v = α v ′′ where v and v ′′ are adjacent on the cycle. This obviously implies that all coefficients α v are equal. This is enough to say that inequality (5.2) induces a facet of S k (G(S)).

We are now ready to build the remaining |S| k-separators. First, we consider |S| k-separators (of G(S)) whose incidence vectors are affinely independent and contained in the face induced by (5.2). These k-separators of G(S) can be extended to k-separators of G by taking x w = 1 for any w ∈ S.

It is now easy to see that the n vectors are affinely independent.

The existence of a k-separator of size ⌈ |S| k+1 ⌉ in G(S ∪{w}) mentioned in Proposition 5.16 does not appear to be very explicit. While it is possible to find an explicit equivalent condition related to how the neighbors of a w ∈ G \ S are located in S, we will only give a sufficient condition (to keep the size of the paper under control).

Let v w 1 , ..., v w r be the neighbors of w in S. We assume that they are encountered in the order v w 1 , ..., v w r when one goes through the cycle in the clockwise sense. Let h(v w i , v w i+1 ) be the number of vertices located between v w i and v w i+1 (when going from v w i to v w i+1 in the same sense and not counting v w i and v w i+1 ). We will consider that v w r+1 = v w 1 .

Proposition 5.17 Let S be a subset of vertices such that |S| > k + 1, |S| is not a multiple of k + 1, and G(S) is an elementary cycle, then inequality (5.2) induces a facet of S k (G) if for each vertex w ∈ S having r adjacent vertices v w 1 , ..., v w r in S, the following equality holds:

r + r i=1 ⌊ h(v w i , v w i+1 ) k + 1 ⌋ = ⌈ |S| k + 1 ⌉.
Proof: Observe that if w does not have neighbors in S, then the existence of a k-separator of size ⌈ |S| k+1 ⌉ in G(S ∪ {w}) is obviously guaranteed. Assume that w has r neighbors in S. Then r

+ r i=1 ⌊ h(v w i ,v w i+1 ) k+1
⌋ represents the size of a k-separator including the r neighbors in addition to a minimum number of vertices that must be removed to disconnect the connected components of size k + 1 located between

v w i and v w i+1 (1 ≤ i ≤ r). If r + r i=1 ⌊ h(v w i ,v w i+1 ) k+1 ⌋ = ⌈ |S|
k+1 ⌉, then this k-separator has a minimum size.

Wheel inequalities

Let W denote a wheel (contained in G) having for rim the cycle C = (V C , E C ) and hub v 0 (i.e., W is the subgraph of G whose node set is V C ∪ {v 0 } and edge set is So the first q nodes following v i on C (for the chosen order) necessarily belong to U . And as this holds for each connected component B i , i ∈ {1, . . . , p}, we have

|U ∩ C| ≥ qp.
And since each connected component has at most k nodes, the number of nodes r satisfies r ≤ kp + |U ∩ C|.

Combining the last two inequalities and rounding leads to |U ∩ C| ≥ rq k+q . Finally, for the case p ≤ 1, using the inequalities |U ∩ C| ≥ q, r ≤ k + |U ∩ C| and then rounding, leads to the proposition. Proposition 5.20 Let G = AW (n, q) with n = r(k + q)z, 1 ≤ z ≤ k q , q ≥ 2, and n, q relatively prime integers. Then the inequality (5.4) is facet-defining for S k (G).

Proof: Let v∈AW (n,q) α v x v ≥ β be an inequality defining a facet F of S k (G) and such that F contains all the incidence vectors of the k-separators saturating inequality (5.4). We show that α v = α w for all v, w ∈ V , thus implying that the inequality (5.4) is facet-defining for S k (G).

Let U denote the node set of a k-separator saturating inequality (5.4). From the assumptions on n and z we deduce |U | = rq.

Let B i denote a connected component of the graph G(V \ U ) with cardinality at least 2. Then B i can be described by a sequence of nodes in C: (v i 1 , . . . , v i p ) such that two consecutive nodes in the sequence are at distance at most q on C from each other. This namely implies that all the nodes in the cycle C from v i 1 to v i p must belong to either U or B i (i.e. they cannot belong to another connected component of G(V \U )). From this observation it follows that if G(V \U ) consists of l connected components then the k-separator |U | must contain at least lq nodes. We mentioned above that for a separator saturating inequality (5.4) we have |U | = rq, thus implying that G(V \ U ) has at most r connected components.

And from the assumption on n, it follows that G(V \ U ) must consist of (at least , and so) exactly r connected components. This shows that G(U ) consists of r paths contained in C, each having length q (and consequently each connected component of the graph G(V \ U ) consists of a path contained in C and having length at most k -1). Since the graph G(V \ U ) has rkz nodes and r connected components, there exists at least one connected component with cardinality at most k -1 and there is at most one connected component consisting of a single node. Let B 0 , . . . , B r-1 denote the connected components of G(V \ U ) that appear sequentially on C (for some arbitrarily set order) and let B l , l ∈ {0, . . . , r -1} denote one such component with minimum cardinality. Consider now the nodes w 1 : the last node of B l-1 (taking indices modulo r) and w 2 : the node of U that is located after w 1 on C (for the chosen order) and is a neighbor of the first node of B l . (So the q nodes which follow w 1 on C belong to U and w 2 is the last one of these nodes in U ). Then the node set U ′ := U \ {w 2 } ∪ {w 1 } is a k-separator with the same cardinality as U , and we can deduce α w 1 = α w 2 .

We may then proceed in this manner until the component B i of G(V \ U ) to which we added a node attains a cardinality of value k. We may then consider the component B i-1 in place of B i ... and so on, leading to the equations α v i = α v i+q , with C = (v 0 , . . . , v n-1 ), taking indices modulo n. Since n and q are relatively prime integers we deduce the equations α v = α w , ∀v, w ∈ V .

Generalized projected metric inequalities

Remember that the projected metric inequalities (4. For each vertex j ∈ S, let p Aj be a path connecting j to one vertex from A. The internal vertices of p Aj can be assumed to be in A. Similarly to Section 4.5, p Aj \ A denotes the path connecting j to the last vertex of p Aj not belonging to A. It is then easy to see that the following inequalities are valid:

(|S| + |A| -k)(1 -x(A)) ≤ j∈S x(p Aj \ A).
(5.5) Inequalities (5.5) can be written in a different way by making two observations. First, the paths p Aj for j ∈ S should be shortest paths from j to A (with respect to vertex weights (x v ) v∈V ). Second, we can assume that each path p Aj \A is included in S since otherwise inequality (5.5) can be strengthened by deleting j from S, adding to S a vertex l from p Aj \ A and replacing p Aj by the subpath of p Aj connecting l to A . These two observations imply that we can assume that j∈S p Aj is in fact the disjoint union of some trees rooted at vertices in A. All vertices of each rooted tree

(|S| + |A| -k)(1 -x(A)) ≤ v∈S d ′ v x v (5.6)
where A ⊂ V and S ⊂ A such that: G(A) is connected, |A| ≤ k, and |S|+|A| ≥ k+1.

In the situation depicted by Figure 5.1, inequality (5.6) can be written as follows:

(|S| + |A| -k)(1 -x a -x b -x c ) ≤ (x f + x g + x h + x j + x k ) + 2x d + 3(x e + x i ).
If we consider the special case where S ⊂ N (A), then inequality (5.6) becomes

(|S| + |A| -k)(1 -x(A)) ≤ x(S). (5.7)
Since the exhibition of all cases where inequality (5.6) induces a facet requires some tedious proofs, we will only focus on a special case of inequality (5.7). Proof: Assume that all k-separators saturating inequality (5.7) satisfy the equality Chapter 6. Computational Results

Cutting-plane algorithms

Three cutting-plane algorithms will be compared. The first one is related to the stable set formulation IP 2. The second one is related to the partitioning formulation IP 9. The third cutting plane algorithm is related to both basic and projected metric formulations (IP 1 and IP 7). Thanks to Proposition 4.2, we do not need to consider formulations IP 4, IP 5 and IP 6. Moreover, many valid inequalities including (4.1) and those of Section 5.4 can be used to strengthen the linear relaxation LP 7.

A cutting-plane algorithm related to the stable set formulation IP 2

The linear relaxation LP 2 can naturally be strengthened using some of the valid inequalities of the stable set polytope including odd-cycle inequalities, clique inequalities, etc. (see, e.g., [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]). Gerards and Schrijver [START_REF] Schrijver | Matrices with the edmonds-johnson property[END_REF] gave a polynomial-time separation algorithm for odd-cycle inequalities. In our implementation, only oddcycle inequalities and clique inequalities are considered. Clique inequalities are separated using a basic greedy algorithm.

More valid inequalities could be considered. However, the size of formulation IP 2 becomes huge when k increases. Then we can not expect a cutting-plane algorithm related to IP 2 to be competitive with the two next cutting-plane algorithms.

A cutting-plane algorithm related to the partitioning formulation IP 9

We consider the linear relaxation LP 9. Only inequalities (4.3) are iteratively added to improve the relaxation LP 9. The separation of these inequalities can obviously be done in polynomial time. For each edge (i, j), we should take U = {b ∈ {1, ..., B} :

z ib ≥ z jb }.
Then we only have to check if the inequality is violated.

Proposition 6.1 Inequalities (4.3) can be separated in polynomial time.

We have used a heuristic method to compute B. We solve LP 2 and then we round the max stable set (obj) value to the ceiling one(⌈obj⌉).

Experimental results

the maximum size of each component is k, T ime is the total time in minutes and seconds spent in the cutting-plane and the branch-and-bound or branch-and-cut phases, the O.IP is the best solution found before one hour. In table 6 in each iteration. The separation of these inequalities are mentioned before in 6.2.3 (resp. 6.2.2). The branching phase of our two branch-and-cuts algorithms is done as follows : we branch on variable x i (i ∈ V ) for which {x i , 1x i } is maximal. If

x i < 0.5 we first examine the branch corresponding to x i = 0, if x i ≥ 0.5 we start with the case x i = 1.

The program was written in C++. All experiments were conducted on a computer with a processor "Intel Core 2 Quad CPU Q6600" of frequency 2,4 Ghz, and a RAM size of 3,25 Gbytes running on Windows operating system.

While the problem is solved very quickly by using IP2, one can observe that the gap between the linear-programming bound at the end of the cutting-plane phase and the optimum can be very large even for problems of medium size.

x v ≥ 1, ∀S ⊂ V, |S| = k + 1, G(S)connected " in (IP 1
) is NPhard even if all vertex-weights belong to {0, 1} when k is part of the input [START_REF] Hochbaum | K-edge subgraphs problems[END_REF]. If k is constant, the separation is obviously easy. It is also known that a maximum-weight connected subgraph of size k + 1 can be computed easily if the graph is a tree [START_REF] Hochbaum | K-edge subgraphs problems[END_REF].

An LP-based approximation algorithm 9 is obtained by generalizing the basic approximation algorithm for the vertex cover problem.

A connected subgraph G(S) is said to be large if |S| ≥ k + 1. is connected, the vertex v (maximizing x v inside R) necessarily satisfies x v ≥ 1 k+1 . Adding v to S is equivalent to rounding x v to 1. The final solution is clearly a k-separator. The weight of this k-separator is not more than k + 1 times the weight of the fractional solution x (since in the rounding procedure, x v is multiplied by at most k + 1). Since the weight of the fractional solution x is a lower bound of the optimal weight, we deduce that we have a (k + 1)-approximation.

Primal Dual approach

Observe that the algorithm described above is a polynomial-time algorithm if we assume that k is bounded by a constant. This is necessary to guarantee that the size of (LP 1) is polynomial. The primal-dual approach (see, .e.g., [START_REF] Williamson | The primal-dual method for approximation algorithms[END_REF]) leads also to a (k + 1)-approximation. In fact, the k-separator problem is a special-case of the hitting set problem where we want to hit large connected components.

Inapproximability

Greedy approximation algorithm

If all vertex weights are equal to 1, then there is another simple (k+1)-approximation algorithm (Algorithm 10). Proof: Since the algorithm stops only when there are no large connected components, the final set S is a k-separator. Each subset R selected in any iteration is a large connected component. Then, we know that any optimal k-separator should contain at least one vertex from this subset R. Since we put all vertices of R in S and |R| = k + 1, the size of S cannot be more than k + 1 times the size of an optimal k-separator.

Algorithm 10 Greedy Approximation Algorithm

The greedy algorithm obviously has a polynomial time complexity even if k is part of the input.

Inapproximability

Notice that we should not expect much better approximation algorithms since it is shown that the vertex cover (corresponding with k = 1) cannot be approximated within a factor of 1.3606 [START_REF] Safra | On the hardness of approximating minimum vertex cover[END_REF] unless P = N P . It is even hard to approximate it within a factor less than 2 if the unique games conjecture is true [START_REF] Khot | Vertex cover might be hard to approximate to within 2ε[END_REF].

Finally, since computing a minimum-weight k-separator is equivalent to maximizing the weight of the vertices that are not in the k-separator, one can also study the approximability of the maximization problem. Let us call this problem the maximum k-coseparator problem. For k = 2, it is shown in [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] that this problem cannot be approximated within a factor of |V | 1/2-ε for any constant ε > 0. We extend their results for any k using the same reduction technique.

Conclusion

Approximation algorithms are presented above. Inapproximability is also studied.

For big instances, a heuristic approach must be considered.

Chapter 8

Conclusion

In this thesis we presented and studied the k-separator problem which consists, given some vertex-weighted graph G = (V, E), in determining a minimum-weight set of vertices S ⊆ V such that no component in the subgraph induced by V \ S has size strictly larger than k. Connections with other classical combinatorial optimization problems have been established and cases when the problem is easy to solve (i.e. polynomial time solvable) have been identified and methods for such cases, proposed.

A polyhedral study has then been undertaken, leading to many valid inequalities that may be used to strengthen formulations of the problem. Part of these inequalities have been integrated in different cutting-plane algorithms that have been applied on a wide range of instances. These evaluations illustrate the potential advantages and limits for some of the different formulations presented throughout this work.

Then different formulations of the problem and relaxations have also been studied and compared. Particularly, with respect to linear relaxations. Some approximation results and algorithms have been demonstrated.

A matter for future research work is the exhibition of some new classes of problems for which better approximation algorithms can be provided. Completing the polyhedral description when the problem can be solved in polynomial-time (such as for trees) deserves further research.

A heuristic algorithm is required in the case of big instances for the future works.

The graphs related to social network are known to be huge. Applying the results obtained in this thesis for these graphs can be useful to detect communities.

A.2. Problématique

un graphe (orienté ou non selon le cas) où les liens modélisent des échanges ou des points communs entre les membres du réseau (ou groupe). La détection des communautés à l'intérieur d'un réseau social est un sujet qui a fait couler beaucoup d'encre [START_REF] Gavalas | Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction[END_REF]. L'idée de base consiste à voir les communautés comme des sous-graphes denses.

Plusieurs algorithmes ont été développés pour y parvenir incluant le très classique algorithme des k-moyennes et différents algorithmes de partitionnement de graphes.

Les points communs entre les réseaux de télécommunications et les réseaux sociaux sont très nombreux. Le point qui nous intéresse le plus ici est le fait que dans les deux cas, on essaye de voir (ou de construire) le réseau comme des clusters (des sous-graphes denses). Dans la section suivante A.2 on présente le thème principal de la thèse. La section A.3 décrit les approches développées. Enfin nous essayons de tirer les conclusions qui s'imposent et nous proposons quelques perspectives dans la section A.4.

A.2 Problématique

L'objectif de cette thèse est la généralisation d'un problème connu de la théorie de graphes et son étude en caractérisant les cas où le problème est polynomial ou approximable avec un bon rapport. Le problème à étudier consiste plus précisément en la construction d'algorithmes afin de déterminer le nombre minimum de noeuds qu'il faut enlever à un réseau (ou graphe) pour que toutes les composantes connexes restantes contiennent chacune au plus k-sommets. Ce problème on l'appelle Problème de k-Séparateur et on désigne par k-séparateur le sous-ensemble recherché. Il est une généralisation du Vertex Cover qui correspond au cas k = 1 (nombre minimum de sommets intersectant toutes les arêtes du graphe).

A.3 Propositions

7: FINTANTQUE

Notons que les deux algorithmes sont (k + 1)-approchés.

A.4 Conclusion & Perspective

Dans cette thèse nous avons présenté le problème de k-Séparateur. Il consiste à trouver le sous-ensemble de sommets de poids minimal à supprimer dans un graphe non orienté dont les sommets sont pondérés afin d'obtenir des sous-ensembles connexes de taille inférieure ou égale à un entier positif k donné. Une étude polyédrale a été faite, conduisant à de nombreuses inégalités valides qui peuvent être utilisées pour renforcer les différentes formulations linéaires du problème. Une partie de ces inégalités a été implémentée dans des algorithmes de type branch-and-cut et ces algorithmes ont été appliqués sur une large variété d'instances. Les différentes formulations du problème et relaxations ont également été étudiées et comparées.

Si k = 1 ,

 1 nous obtenons le problème classique Vertex Cover. De nombreuses formulations sont proposées pour ce problème dans notre thèse. Les relaxations linéaires de ces formulations sont comparées. Une étude polyédrale est proposée (inégalités valides, facettes et algorithmes de séparation). Des cas où le problème peut être résolu en temps polynomial sont présentés. Entre autres, le cas de chemins, de cycles, d'arbres, et plus généralement les graphes avec largeur arborescente bornée ainsi que des graphes ne contenant pas certains graphes particuliers comme sous graphes induits. Des algorithmes d'approximation de rapport (k +1) sont également exposés et quelques résultats d'inapproximabilité. La plupart des algorithmes sont implémentés et comparés. Mots Clés:Couverture par des sommets, Méthode de coupe, Problème de séparateur, Approches polyèdrales, Algorithmes d'approximation.

2. 1 1 Introduction Contents 1 . 1 15 1. 3

 1111153 Maximal dissociation sets of graph P 5 [90] . . . . . . . . . . . . . . . 2.2 K 1,4 bipartite graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 K 2,2 bipartite graph in the left and C 4 in the right . . . . . . . . . . 2.4 Example of planar graph . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Example of line graph . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Some P k and K 1,n graphs . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Left : web W 3 10 and right :antiweb AW 3 10 . . . . . . . . . . . . . . . . 2.8 1-wheel graph [12] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Inheritance of valid inequalities [53] . . . . . . . . . . . . . . . . . . 2.10 Inheritance of facets inequalities [53] . . . . . . . . . . . . . . . . . . 3.1 The graphs G 1 , G 2 , G 3 and P 6 . . . . . . . . . . . . . . . . . . . . . 3.2 Example of an interval-filament graph . . . . . . . . . . . . . . . . . 3.3 Asteroidal triple-free graph . . . . . . . . . . . . . . . . . . . . . . . 3.4 Chordal and weakly chordal graphs . . . . . . . . . . . . . . . . . . . 3.5 Example of an interval and circular-arc graphs . . . . . . . . . . . . 3.6 On the dynamic programming approach to solve problem (3.5) . . . Chapter General Context . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thesis plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

  .1 diss + (P 5 ) = 4 and diss -(P 5 ) = 3. diss + (G) is a lower bound for the 1-improper chromatic number of a graph G [69]. The dissociation set problems refer to maximum dissociation set problem and minimum

Figure 2 . 1 :

 21 Figure 2.1: Maximal dissociation sets of graph P 5 [90]

Figure 2 . 2 :

 22 Figure 2.2: K 1,4 bipartite graph

Figure 2 . 3 :Figure 2 . 4 :

 2324 Figure 2.3: K 2,2 bipartite graph in the left and C 4 in the right

Figure 2 . 5 :Figure 2 . 6 :

 2526 Figure 2.5: Example of line graph

b

  v on x v , i.e. a vertex v can used at most b v times to cover edges, we can obtain a 2-approximation in which x * v ≤ 2x v . The weights on the vertices constitute a generalization of the problem. Denote by c eu cost of assignment an edge e to vertex u. The change in the IP (IP 2.5) is to add e∈E u∈e c eu y eu to the objective function.

Chapter 2 .

 2 Related work Algorithm 3 Threshold and Round

  and p ≤ |i -j| ≤ m -p}. (for a sample see figure 2.7). The antiweb AW p m = (V (W ), E(W )) is the complement of the web W p m (an example is shown in

Figure 2 . 7 : 10 Figure 2 . 8 : 1 -

 2710281 Figure 2.7: Left : web W 3 10 and right :antiweb AW 3 10

Figure 2 . 9 :

 29 Figure2.9: Inheritance of valid inequalities[START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]

. 4 )

 4 In Equation(3.4), C out v (p -1, i) + C in vp represents the situation where v p (the p th child of v) belongs to the k-separator of T v while T p-1 v contains a connected component of size i including v after the removal of the k-separator. The second term min j=1...i-1 C out v (p -1, ij) + C out vp (j) clearly corresponds to the case where v p does not belong to the k-separator. Equation (3.4) can be used in combination with equations (3.1), (3.2), (3.3) to compute all optimal weights. For a vertex v, quantities C out v (p, i) can be computed only when the children of v were already addressed. We should of course start by p = 1 and increase it until reaching d + v .

  such that either S ∩ T = ∅, or (u, v) ∈ E for some u ∈ S and v ∈ T }. Said another way, S ∈ V ⋆ and T ∈ V ⋆ are connected by an edge if the subsets of vertices of G they are representing either have a common vertex or contain two adjacent vertices. The weight of a vertex S ∈ V ⋆ is defined by w S = v∈S w v .

Figure 3 . 1 :

 31 Figure 3.1: The graphs G 1 , G 2 , G 3 and P 6

  free where G 2 and G 3 are shown on Figure3.1. We are going to extend this result when k ≥ 3. More precisely, we will prove thatG ⋆ is G 1 -free if and only if G is (G 1 , G 2 , G3 , P 6 )-free graph where P 6 is the simple path containing 6 vertices (shown on the right part of Figure 3.1). Proposition 3.4 Assuming that k ≥ 3, the extended graph G ⋆ is G 1 -free if and only if the original graph G is (G 1 , G 2 , G 3 , P 6 )-free.

V 3 and

 3 not adjacent to the rest of vertices. It is cleat that |V 4 | = 1 by the minimality assumption of i=4 i=0 |V i |. Let then V 1 = {v 1 }, V 2 = {v 2 } and V 4 = {v 4 } where v 1 , v 2 and v 4 are vertices of G.

Figure 3 . 2 :Figure 3 . 3 :

 3233 Figure 3.2: Example of an interval-filament graph

Figure 3 . 4 :

 34 Figure 3.4: Chordal and weakly chordal graphs

Figure 3 . 5 :Lemma 3 . 1

 3531 Figure 3.5: Example of an interval and circular-arc graphs

Figure 3 .

 3 Figure 3.6 illustrates the definitions where we have r = 16, O = {1, 2, 3, 6, 7, 8, 11, 14}, δ(1) = 4, δ(2) = 8, δ(3) = 1, δ(6) = 3, etc. Assume that k = 6 and suppose that the optimal solution of problem (3.5) is given by the intervals represented by thick arrows in Figure 3.6. The intervals belonging to the optimal solution can be numbered

Figure 3 . 6 :

 36 Figure 3.6: On the dynamic programming approach to solve problem (3.5)

Contents 4 . 1

 41 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Basic formulation . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Stable set formulations . . . . . . . . . . . . . . . . . . . . . . 4.4 Metric formulations . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Projected metric formulation . . . . . . . . . . . . . . . . . . 4.6 Partitioning formulations . . . . . . . . . . . . . . . . . . . . . 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Proposition 4 . 1

 41 The following inclusion holds:F 3 ⊆ F 1.Proof: Let (x, y) stand for a feasible solution of LP 3. Let C denote a connected component of size k + 1 in the original graph G = (V, E). So we have:v∈C x v = k + 1 -v∈C S∈Qv y S .Notice that in the last expression each variable y S such that S has a nonempty intersection with C occurs exactly |S ∩ C| times.

(4. 2 ) 4 . 1

 241 Lemma Inequalities (4.2) are valid for S k (G).

Corollary 5 . 1

 51 not a scalar multiple of (a, b) (i.e. there does not exist α > 0 with (c, d) = α(a, b)). Notice that since c t x ≥ d is valid for S k (G), F ′ ⊆ F ′′ , we have F ⊆ {x ∈ S k (G) : c t x = d}. This namely implies c t x ≥ d is facet defining for S k (G), so that we must have (c, d) = α(a, b) for some scalar α > 0, a contradiction. Let the inequality a t x ≥ b be facet inducing for S k (G), G = (V, E).

5. 4

 4 Valid inequalities for S k (G) 5.4.1 Hitting set inequalities Hitting set inequalities are the basic inequalities (4.1). Proposition 5.11 Let S be a subset of vertices such that G(S) is connected and |S| = k + 1. Then the inequality v∈S x v ≥ 1 defines a facet of S k (G) if each vertex w ∈ V \ S is adjacent to at most 1 vertex in S.

  This implies that inequality (5.1) induces a facet of S k (G(S)). Then, it is possible to find |S| k-separators (of G(S)) whose incidence vectors are affinely independent and contained in the face induced by (5.1). These k-separators of G(S) can be extended to k-separators of G by taking x w = 1 for any w ∈ S.

  2) are given by (|S| + 1k)(1 -x i ) ≤ j∈Sx(p ij \ {i}) where i ∈ V . They can be generalized as follows. Vertex i is replaced by a subset of vertices A ⊂ V such that G(A) is connected and |A| ≤ k.Let S be a subset of vertices A ⊂ V such that S ∩ A = ∅ and |S| + |A| ≥ k + 1.

Figure 5 . 1 :

 51 Figure 5.1: Illustration of inequality (5.6)

Figure 5 .

 5 1 illustrates the situation. Observe that in the sum j∈S x(p Aj \ A), the variable x v related to vertex v ∈ S appears as many times as the number of vertices in the subtree rooted at v. Let us use d ′ v to denote this number. Then inequality (5.5) can be written as follows:

Proposition 5 .

 5 21 Let A = {i} and S ⊂ N (A) be such that |S| ≥ k + 1, and G(S ∪ {j}) does not contain a connected component of size greater than or equal to k + 1 for any j ∈ S ∪ A. Then inequality (5.7) induces a facet of S k (G).

Algorithm 9 LP-based Approximation Algorithm 1 :

 91 Input: A vertex-weighted undirected graph G = (V, E, w) and an integer k. 2: Output: A k-separator S. 3: Solve (LP 1) and let x be an optimal solution of (LP 1). 4: Set S := ∅. 5: while G(V \ S) contains large connected components do 6:Select R ⊂ V \ S such that |R| = k + 1 and G(R) connected.7:Select v ∈ R such that xv is maximum and set S := S ∪ {v}. 8: end while Proposition 7.1 The LP-based approximation algorithm (Algorithm 9) is a (k+1)approximation algorithm. Proof: Since y∈R x y ≥ 1 for each subset R ⊂ V \S where |R| = k+1 and G(R)

1 :

 1 Input: A graph G = (V, E) and an integer k. 2: Output: A k-separator S. 3: Set S := ∅. 4: while G(V \ S) contains large connected components do 5: Select R ⊂ V \ S such that |R| = k + 1 and G(R) is connected. 6: S := S ∪ R. 7: end while Proposition 7.2 For the case when all vertex weights are equal to 1, the greedy algorithm (Algorithm 10) is a (k + 1)-approximation algorithm for the k-separator problem.

Proposition 7 . 3

 73 Assuming that P = N P , the maximum k-coseparator problem cannot be approximated in polynomial time within a factor of ( |V | k ) 1-ε for any constant ε > 0.Proof: Let us focus on instances of the k-coseparator problem with unit weights and let cosep k (G) denote the maximum size of the complement of a k-separator of a graph G. Consider an instance of the maximum stable set problem given by a graphG = (V, E). Build a new graph G ′ = (V ′ , E ′ ) by k duplications of each vertex v ∈ V (each vertex v ∈ V is replaced by k vertices v 1 , ..., v k ), and adding edges (u i , v j ) for 1 ≤ i ≤ j ≤ k when (u, v) ∈ E. It is easy to see that cosep k (G ′ ) = kα(G) where α(G)is the size of a maximum stable set of G. Indeed, a stable set of size α(G) directly leads to a k-coseparator of size kα(G) by replacing each vertex of the stable set by its k duplicate vertices. Moreover, given a maximum size k-coseparator of G ′ , if two adjacent vertices u i and v j belong to the same connected component, then there is at least an index l (1 ≤ l = i ≤ k) such that u l does not belong to the k-coseparator (otherwise the size of the connected component will be strictly greater than k). By deleting v j and adding u l , we get a new k-coseparator of maximum size.By repeating this process, we should obtain a k-coseparator where each connected component contains exactly the k duplicate vertices v 1 , ..., v k of some vertex v ∈ V .By considering the vertices v whose duplicate vertices are inside the k-coseparator, we get a stable set of G whose size is 1/k times the size of the k-coseparator of G ′ . Consequently, cosep k (G ′ ) = kα(G). Using the fact that the maximum stable set of G cannot be approximated within |V | 1-ε[START_REF] Hastad | Clique is hard to approximate within n (1-ε)[END_REF][START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], we deduce that the maximum k-coseparator of G ′ cannot be approximated within ( |V ′ | k ) 1-ε in polynomial time unless P = N P .

  Nous travaillons sur deux volets à savoir les méthodes exactes basées sur les approches polyédrales et les algorithmes d'approximation avec garantie de performance. Avant de présenter les approches adoptées, nous introduisons quelques notations. Notons par G = (V, E, w) un graphe non orienté dont les sommets sont pondérés. Etant donné un sous-ensemble S ⊂ V , χ (S) ∈ {0, 1} n désigne le vecteur d'incidence de S. P k est l'enveloppe convexe pour touts les k-séparateurs. On note A.3. Propositions Proposition A.1 Le problème du k-séparateur peut être résolu en temps polynomial dans le cas de chemins, de cycles et plus géneralement des graphes avec largeur arborescente bornée même si k est paramètre de l'entrée. A.3.1.1.b Graphes sans couplage mK 2 induit Avant de présenter les graphes sans couplage mK 2 induit, nous introduisons une construction d'un graphe étendu H à partir du graphe G permettant de transformer le problème du k-séparateur à un problème de stable de poids maximal. L'idée consiste à créer un graphe étendu H= (V (H), E(H)) à partir du graphe G. Chaque sous-ensmble de sommets S ⊂ V tel que 1 ≤ |S| ≤ k et G(S) est connexe est representé par un sommet dans H. V (H) = {S ⊂ V, |S| ≤ k, G(S) est connexe}.Les arêtes sont définies comme suit :E(H) = {(S, T ), S ∈ V (H), T ∈ V (H), S = T, tel que S ∩ T = ∅, ou (u, v) ∈ E avec u ∈ S et v ∈ T }. Autrement dit, S ∈ V (H) et T ∈ V (H)sont reliés par une arête si les sous ensembles de sommets de G qui correspondent à S et T , comportent un sommet commun ou contiennent deux sommets adjacents. Le poids du sommet S ∈ V (H) est égal à w S = v∈S w v . Notons par R le stable de poids maximum de H. Si deux sommets S ∈ V (H) et T ∈ V (H) appartiennent à ce stable R, alors S ∩ T = ∅ ne contient pas une arête dans G avec une extremité dans S et l'autre extremité dans T . Autrement dit, si on considère ∪ S∈R S, on obtient un ensemble de sommets dont chaque composante connexe est de taille inférieure ou est égale à k. Le complémentaire de ∪ S∈R S est un k-séparateur. Cette construction du graphe étendu peut être considérée comme une généralisation de la construction proposée dans [81] pour le problème de la dissociation (k = 2). Supposons maintenant que G ne contient pas un couplage m induit où m est une constante. Cela est équivalent à dire que G est sans couplage mK 2 . Dans ce cas le problème de dissociation est facile à résoudre comme il est prouvé dans [90]. Et comme le problème de dissociation est un cas particuliers du problème de kséparateur (k = 2), nous généralisons ce résultat pour toute constante k. Proposition A.2 Le problème de k-séparateur peut être résolu en temps polynomial pour les graphes sans les couplages mK 2 induit dans le cas où m et k sont des constantes.A.3.2 Algorithmes d'approximationLe premier algorithme est une généralisation d'un autre algorithme d'approximation du vertex cover. Algorithm 11 Algorithme d'approximation basé sur la programmation linéaire 1: Entrée: un graphe G = (V, E, w) dont les sommets sont pondérés et un entier k. 2: Sortie: un k-séparateur S. 3: résoudre (LP 1) et soit x la solution optimale de LP 1. 4: S = ∅. 5: TANTQUE G(V \ S) contient une composante large FAIRE 6: Choisir R ⊂ V \ S telque: |R| = k + 1 et G(R) connexe. 7: Choisir v ∈ R telque: xv est maximum et on pose S = S ∪ {v}. 8: FINTANTQUE En utilisant la méthode primale-duale [86] nous avons un autre algorithme d'approximation. Algorithm 12 Algorithme glouton 1: Entrée: un graphe G = (V, E, w) dont les sommets sont pondérés et un entier k. 2: Sortie: un k-séparateur S. 3: S = ∅. 4: TANTQUE G(V \ S) contient une composante large FAIRE 5: Choisir R ⊂ V \ S tel que: |R| = k + 1 et G(R) connexe. 6: S = S ∪ R.

  The primal-dual method . . . . . . . . . . . . . . . . . . . . . 2.3.2 The Rounding Approach . . . . . . . . . . . . . . . . . . . . . 2.3.3 The Greedy Method . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Polyhedral Approach . . . . . . . . . . . . . . . . . . . . . . . .4.1 Disconnecting Graphs problem . . . . . . . . . . . . . . . . . 37 2.4.2 Vertex Separator problem . . . . . . . . . . . . . . . . . . . . 46 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Related problems to k-separator problem . . . . . . . . . . . 2.2.1 Vertex Cover problem . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Stable Set problem . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Maximal Clique problem . . . . . . . . . . . . . . . . . . . . . 2.2.4 Hitting Set problem . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 Set Cover problem . . . . . . . . . . . . . . . . . . . . . . . . 2.2.6 Capacitated Vertex Cover problem . . . . . . . . . . . . . . . 2.2.7 Dissociation Set problem . . . . . . . . . . . . . . . . . . . . 2.2.7.1 K 1,4 -free bipartite graphs . . . . . . . . . . . . . . . 2.2.7.2 C 4 -free bipartite graphs . . . . . . . . . . . . . . . . 2.2.7.3 Planar graphs . . . . . . . . . . . . . . . . . . . . . 2.2.7.4 Line graphs . . . . . . . . . . . . . . . . . . . . . . . 2.2.7.5 (P k ,K 1,n )-free graphs . . . . . . . . . . . . . . . . . 2.3 Used methods and techniques . . . . . . . . . . . . . . . . . . 2.3.1 2.4 Further connections between the k-separator problem and other problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1. Introduction 2

Table 2 .

 2

	59]

1: Complexity of MDS, MIM and MIS

[START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF]

  and then we increase y k for all T k ∈ V l until ∃e l / ∈ A l such that i:e l ∈T i y i = C e l . Finally, we start the deletion step by removing from A

	Chapter 2. Related work
	cover problem. The following integer program (IP 2.3) describes the problem :
	′
	the not necessary elements and still maintain it feasible.
	To illustrate the primal-dual method, we consider the minimum-weight vertex

  the hub ({a} in figure 2.8). P 0,1 , P 0,2 , ..., P 0,2k+1 are the spokes.(v 1 , v 2 , . . . , v 2k+1 ) are the spoke-ends ({b, c, d, g, i} in figure 2.8). P 1,2 , P 2,3 , ..., P 2k+1,1 is the rim. E={v i ∈ V : where P 0,i is an even path} ({b, c, i} in figure 2.8).

	O={v

i ∈ V : where P 0,i is an odd path } ({d, g} in figure 2.8). S = S(W ) is the set of internal vertices of the spokes ({j, k, l} in figure 2.8). R = R(W ) is the set of internal vertices of the rim-paths ({m, e, f, h} in figure 2.8

  S Q = ∅, and for any representative collection of type 2 separators

			a 2k+1
		a 2k 2	= a 2 + a 4 + . . . + a 2k	(2.17)
	with b 2k+1 1	and b 2k 2 defined in the same way, then an orderly minimal connected
	dominator S is called exceptional [21] if
	1. s is odd and
	2.

  .2) Proof: By writing inequality (4.1) for each subset S ′ ⊂ S for which G(S ′ ) is connected and adding up all of them, we obtain the inequality (k+1) v∈S x v ≥ |S|. Proposition 5.14 can be applied with q = 1 to know under which conditions inequality (5.2) induces a facet. Let us then focus on the case where |S| > k + 1. It is clear that if |S| ≡ 0[k + 1], then (5.2) is just the sum of inequalities of type (4.1). Proposition 5.16 Let S be a subset of vertices such that |S| > k + 1, |S| is not a multiple of k + 1, and G(S) is an elementary cycle, then inequality (5.2) induces a facet of S k (G) if and only if for each vertex w ∈ S, there is a k-separator of size

	Inequality (5.2) follows by simple rounding.

Notice that when |S|

= k + 1,

  .1 : the gap defined by 0 if the optimum value (O.IP ) found before one hour, otherwise Gap = (O.IP -O.LP )/O.IP * 100 , the cost O.LP at the end of the cutting-plane phase, the number of generated odd cycle inequalities denoted by Cuts and the number of iterations in the cutting-plane phase is Iter. Let IP 1&IP 7 denotes the formulations IP 1 and IP 7. In table 6.2 we have five different columns from Table 6.1 for the IP 1&IP 7. The first is HitSet corresponding to Hitting Set inequalities 4.1. The second is P rojM etric for the Projected metric inequalities (4.2). The third, B&C denotes the cuts added by Cplex solver. N #.Iter is the number of iterations one iteration consists of one round of adding violated inequalities then reoptimizing the IP 1&IP 7 or IP 9 and N odes is the number of nodes in the branch-and-cut tree.

We implemented two branch-and-cut algorithms for k-separator problem applied to IP 1&IP 7 (resp. IP 9). In the cutting-phase we add in the first step the Cplex solver cuts in the IP 1&IP 7 (resp. IP 9), then we add the violated constraints for each class of the valid inequalities. Precisely, we add in second step the HitSet to IP 1&IP 7 (resp. Compl to IP 9, where Compl is the constraints (4.3)). In the last step we add the P rojM etric to IP 1&IP 7 and reoptimize IP 1&IP 7 (resp.

IP 9)

Table 6 .

 6 This suggests the necessity of adding other valid inequalities. Moreover, when k increases, the size of the extended graph and thus the formulation LP 2 increases very quickly. In

	N ame	|V | |E|	k T ime N #.Iter N odes HitSet P rojM etric B&C O.IP
	afiro		20	5 00:00	53	40	26	85	126	2
	fit1d		228	6 00:01	61	62	103	198	320	16
	fit2d		279	7 00:01	73	98	54	73	143	18
	sc50b		110	7 00:03	645	660	362	679	3562	11
	sc50a		95	8 00:01	523	689	89	216	753	8
	kb2		330 10 00:01	78	178	95	139	432	14
	vtpbase		354 13 00:11	524	836	317	528	3585	14
	bore3d		615 13 00:08	531	639	429	832	2754	23
	scsd1		202 20 00:07	574	498	520	708	3302	8
	share2b		619 24 00:40	442	643	743	920	4720	8
	seba	2	0	1 00:00	1	1	0	0	0	0
	adlittle		239 14 00:32	1289	1784	611	1293	8390	10
	blend		548 14 00:21	456	559	532	840	3924	20
	recipe		129 14 00:01	40	19	21	49	67	0
	scagr7		661 15 00:37	671	847	828	891	5274	21
	sc105		356 15 00:23	889	1083	782	945	6007	16
	stocfor1		272 16 00:14	241	187	159	362	930	10
	beaconfd 1199 23 03:15	3261	3782	924	2749	15649	26
	Table 6.3: IP1 and IP7 formulations applied to NETLIB instances
	N ame	|V | |E|	k B T.B T ime N #.Iter N odes Compl B&C O.IP
	afiro		20	5 11 00:02 00:00	44	43	21	43	2
	fit1d		228	6	4 00:01 00:01	48	70	62	138	16
	fit2d		279	7	3 00:00 00:01	62	103	43	60	18
	sc50b		110	7	4 00:01 00:04	518	664	509	1548	11
	sc50a		95	8	3 00:02 00:02	415	663	225	413	8
	kb2		330 10 4 00:01 00:02	76	134	73	148	14
	vtpbase		354 13 4 00:04 00:13	534	903	604	1596	14
	bore3d		615 13 3 00:01 00:11	427	748	224	1275	23
	scsd1		202 20 5 00:07 00:11	493	523	655	1473	8
	share2b		619 24 5 00:10 00:42	398	514	1757	1188	8
	seba	2	0	1	2 00:00 00:00	1	1	0	0	0
	adlittle		239 14 6 00:05 00:49	1170	1161	2657	3504	10
	blend		548 14 5 00:03 00:29	432	538	1000	1290	20
	recipe		129 14 5 00:03 00:01	11	7	2	10	0
	scagr7		661 15 4 00:03 00:39	584	789	1399	1746	21
	sc105		356 15 6 00:05 00:37	776	1029	1659	1548	16
	stocfor1		272 16 13 00:08 00:25	187	212	575	185	10
	beaconfd 1199 23 3 00:09 02:36	2596	4624	889	10374	26
		Table 6.4: IP9 formulation applied to NETLIB instances

other words, to solve problems with larger values of k and |V |, it seems that we should try to strengthen formulation LP 1 rather than LP 2. We can observe that Contents 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.2 Approximation algorithms . . . . . . . . . . . . . . . . . . . . 106 7.2.1 LP-Based approximation algorithms . . . . . . . . . . . . . . 106 7.2.2 Primal Dual approach . . . . . . . . . . . . . . . . . . . . . . 107 7.2.3 Greedy approximation algorithm . . . . . . . . . . . . . . . . 108 7.3 Inapproximability . . . . . . . . . . . . . . . . . . . . . . . . . 108 7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

7.1 Introduction

The first approximation algorithm we give relies on the linear relaxation (LP 1) of the integer program (IP 1) introduced in Section 4.2. Notice that the separation of Chapter 7. Approximations inequalities " v∈S

Acknowledgments

we have tried to give an introduction to each of them and applied them to problems that have a relation with k-separator problem. In the next chapter we will show many cases where k-separator problem can be solved in polynomial time.

3.5.

(G 1 , G 2 , G 3 , P 6 )-free graphs Case 2 . Assume that G(V 0 ) contains a cycle. Since deleting any vertex of the cycle does not break the connectivity of G(V 0 ), the only reason that can prevent us to decrease the size of V 0 is that for each vertex v of the cycle, there is a subset V i (i ∈ {1, 2, 3}) such that V i is adjacent to v (and only to v in V 0 ). This clearly implies that the cycle is in fact a triangle. Moreover, by the minimality assumption, V 0 does not contain vertices outside of the triangle. It is also clear that we cannot simultaneously have v 1 ∈ V 0 and v 2 ∈ V 0 since V 1 and V 2 are not adjacent in G ⋆ . Let us consider the two possible subcases.

Subcase 2.1 . Assume that v 1 ∈ V 0 and v 2 / ∈ V 0 , then the graph

Case 3 . Assume that |V 0 | = 2. Let then V 0 = {a, b} where a and b are two adjacent vertices of G. Notice that we neither have v 1 ∈ V 0 nor v 2 ∈ V 0 . Indeed, if v 1 = a ∈ V 0 , then both v 2 and v 3 are adjacent to b (and not to a). Then, we could take V 0 = {b} without changing the other subsets to obtain a chair in G ⋆ . This contradicts the minimality assumption.

Let us now consider all possible subcases. Observe that there is some symmetry between V 1 and V 2 which reduces the number of subcases to be studied.

Subcase 3.1 . Assume that v 3 is adjacent to both a and b. This clearly implies that

-Suppose that a is adjacent to both v 1 and v 2 , then by taking V 0 = {a} without changing the other subsets, we still obtain a chair in G ⋆ .

This contradicts the minimality assumption. Replacing a by b leads to the same conclusion.

-Let us now assume that a is only adjacent to v 1 while b is only

Subcase 3.2 . Suppose that v 3 is adjacent to a (and not to b).

-Assume that both v 1 and v 2 are adjacent to a. Then, by taking V 0 = {a}, we still obtain a chair in G ⋆ contradicting the minimality 3.6. Interval-filament, asteroidal triple-free and weakly chordal graphs v 1 is only adjacent to x 1 . It is also clear that if v 3 is adjacent to any vertex y of [x 1 , x 3 [, then |V 0 | can be reduced by eliminating x 3 . Let us then change the subsets V i as follows: take

This contradicts the minimality assumption.

Subcase 5.3 . Assume that x 3 = x 2 . To avoid the two previous subcases, we assume

then we get the previous subcase. Let us then assume that v 3 is not adjacent to x 2 . By taking

the other subsets, we obtain a chair in G ⋆ contradicting the minimality assumption.

Corollary 3.1 Assuming that k is a constant ≥ 3, the k-separator problem can be solved in polynomial time for (G 1 , G 2 , G 3 , P 6 )-free graphs.

Proof: If k is a constant, then G ⋆ has a polynomial size. Using Proposition 3.4 and the algorithm of [START_REF] Milanic | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF] to compute a maximum weight stable set problem, one can solve the k-separator problem in polynomial time.

Interval-filament, asteroidal triple-free and weakly chordal graphs

The results of this section are a direct consequence of the results of [START_REF] Hell | Independent packings in structured graphs[END_REF]. Given a graph G and a family H of fixed connected graphs, a H-packing of G is a pairwise node-disjoint set of subgraphs of G, each isomorphic to a member of H [START_REF] Hell | Independent packings in structured graphs[END_REF]. If we add the requirement that each two subgraphs of the packing are not joined by Proof: Given v ∈ V , the incidence vectors of the following k-separators are affinely independent and all saturate the inequality x v ≥ 0: V \ {v} and V \ {v, w}, ∀w ∈ V \ {v}.

Given v ∈ V , the incidence vectors of the following k-separators are affinely independent and all saturate the inequality x v ≤ 1: V and V \ {w}, ∀w ∈ V \ {v}.

Proposition 5.3 If a t x ≥ α denotes a facet defining inequality for S k (G) different from the trivial inequalities (i.e. 0 ≤ x v ≤ 1, for all v ∈ V ) then necessarily a v ≥ 0, ∀v ∈ V and α > 0.

Proof:

[Necessity of the condition a v ≥ 0, ∀v ∈ V ]. Assume there exists some node w ∈ V with a w < 0. As the inequality a t x ≥ α is facet defining and different from -x w ≥ -1, there exists a k-separator Z ⊆ V \ {w} whose incidence vector saturates the constraint. But adding the node w to Z we still get a k-separator but its incidence vector violates the inequality, hence a contradiction with the validity of the constraint.

[Necessity of the condition α > 0]. From the former we have a v ≥ 0, ∀v ∈ V .

Since all the vectors in the k-separator polytope satisfy x v ≥ 0 and a t x ≥ α is facet defining, different from x v ≥ 0, it follows that necessarily α > 0. Proof: Let a t x ≥ α denote a facet-defining inequality for S k (G). From Proposition 5.3 α > 0. This implies that the subgraph G a of G which is induced by the set

The wheel inequality is defined below. Proof: Inequality (5.3) can be obtained by maximum lifting of (5.2).

The results of Section 5.4.3 can be directly used to get conditions under which inequality (5.3) induces a facet of S k (G).

Antiweb inequalities

Let AW (r, q) with r, q ∈ N, denote a graph (also called antiweb) consisting of a cycle C with length r: C = (v 1 , v 2 , . . . , v r ) and all edges of the form (v i , v j ) if the distance between v i and v j on C is at most q.

Proposition 5.19 If AW (r, q) with r ≥ k + q is a subgraph of G, then the following inequality is valid for S k (G) v∈AW (r,q)

x v ≥ rq k + q .

(5.4)

Proof: Let U denote the set of vertices in a k-separator of G. Let T denote the nodes of AW (r, q) that are not contained in U .

Consider first the case when the subgraph

Considering one component B i , for some i ∈ {1, . . . , p}, it is a simple observation (considering the nodes of B i in C sequentially, for some arbitrarily fixed order on C) that at least one node, denoted v i ∈ B i ∩ C satisfies the following:

• the first node which follows v i in C (for the chosen order on C) belongs to U , and

• the first node which follows v i in C (for the chosen order on C) and does not belong to U belongs to a different connected component B j , j ∈ {1, . . . , p}, j = i.

v∈V α v x v = β. Among these k-separator, we can select the separator defined by S. Since we assumed that G(S ∪ {j}) does not contain a connected component of size greater than or equal to k + 1 for any j ∈ S ∪ A, we still obtain a k-separator if we eliminate from S a vertex j ∈ S ∪ A. This clearly implies that α j = 0 for any

By considering the union of any subset of S of size |S| + |A|k with S ∪ A we still get a k-separator whose incidence vector satisfies (5.7) with equality. Since the choice of the subset of S of size |S| + |A|k is arbitrary, we deduce that α v = α w for any v and w belonging to S. In other words, equality v∈V α v x v = β can be written as α S x(S) + x(A) = β (remember that we assumed that |A| = 1).

Considering again the k-separator S leads to β = 1. Also by considering a k-separator given by the union of a subset of S of size |S| + |A|k with S ∪ A,

Conclusion

Several classes of valid inequalities have been investigated, along with conditions under which some of them are facet defining for the k-separator polytope. The next chapter is dedicated to computational results of some formulations studied in this chapter and the previous one.

Chapter 6

Computational Results

Contents

Introduction

In this chapter many cutting-plane algorithms based on branch-and-cut and branchand-bound are implemented. The first algorithm is related to the stable set formulation IP2 by using a branch-and-bound method. The second algorithm is based on the partitioning formulation IP9 using a branch-and-cut approach. The last implemented algorithm is related to formulations IP1 and IP7 using a branch-and-cut concept. A depth analysis of the results is also included in this chapter.

A cutting-plane algorithm related to formulations IP 1 and IP 7

We implemented a cutting-plane algorithm based on inequalities (4.1) and (4.2) in addition to some of the valid inequalities presented in chapter 5 (see section 5.4).

Separation of the hitting-set inequalities (4. Proof: We give here the algorithm. The subset S is initially empty. For each vertex i ∈ V , we first compute the shortest path p ij for each j = i. Then, we put in S the k closest vertices to i. We also add to S all vertices j ∋ S for which

x(p ij \ {i}), then we add the violated inequalities. The procedure is repeated for each vertex i. The complexity of the algorithm is obviously polynomial.

Observe that inequalities (5.6) (equivalent to (5.5)) can also be separated in polynomial-time if the size of A is bounded by a constant. This happens for example if k is bounded by a constant. The separation algorithm is similar to the one presented above to separate inequalities (4.2). We only need to enumerate all subsets

A of size at most k for which G(A) is connected.

Corollary 6.1 Inequalities (5.6) can be separated in polynomial-time if k is upperbounded by a constant.

Experimental results

We present numerical experiments obtained using many integer programs and instances. First integer program used is IP 2. Remember that (IP 2) is based on a stable set formulation in an extended graph. Then all valid inequalities for the stable set problem can be used to strengthen the linear relaxation of (IP 2). However, in our implementation we only focused on odd-cycle inequalities and clique inequalities. Odd-cycle inequalities are separated in polynomial time using the algorithm by [START_REF] Schrijver | Matrices with the edmonds-johnson property[END_REF] (see also 2.3.4), while clique inequalities are generated using a basic greedy heuristic. After a cutting-plane phase based on these two families of valid inequalities, a branch-and-bound follows using the default parameters of the Cplex solver.

Results are reported in the Now we look at the results of another instances. Precisely MIPLIB and NETLIB libraries instances (available at this reference [START_REF]MIPLIB and NETLIB instances[END_REF]). For these instances we use the same parameter values as [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. In tables 6.4 and 6.6 we have Compl, B and T.B.

Compl corresponding to the inequalities (4.3). B denotes the number of partitions and T.B is a time spent for computing B.

The performances of our two branch-and-cut algorithms on these instances are given in the tables, Table 6.3, Table 6.4, Table 6.5 and Table 6.6 . The results of these tables show that the branch-and-cut approach based upon IP 1&IP 7 and IP 9 is a robust method to solve instances for the MIPLIB and NETLIB libraries.

We can see that all instances, 28 MIPLIB instances and 18 NETLIB instances, are solved exactly in less than one hour i.e. with gap equal to zero, whereas 23 MIPLIB instances and 15 NETLIB instances are solved in the case of [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. For example, we solved some instances like share2b or stein15 whereas in [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF] we don't have the optimum value.

Conclusion

In this chapter some formulations are evaluated and some branch and cut algorithms are also presented. We study before concluding this thesis some approximation algorithms.

Appendix A

Résumé du manuscrit de thèse en français Une décomposition arborescente de G est définie par un couple (X , T ) où X = (X t ) t∈V (T ) est une famille de sous-ensembles de sommets de V étiquetés par les sommets d'un arbre T , tels que:

Propriété (iii) implique que le sous-graphe de T induit par les sommets t tel que X t contient v est un sous-arbre. La largeur de la décomposition est donnée par max t∈V (T ) |X t | -1. La largeur arborescente (treewidth) de G est la largeur minimale sur toutes les décompositions arborescentes de G.

Nous supposons ici que G a une largeur arborescente bornée par une constante l.

Le calcul de la largeur arborescente de G peut être fait en temps polynomial (en supposant que l est constante) [START_REF] Bodlaender | A linear time algorithm for finding tree-decompositions of small treewidth[END_REF]. Beaucoup de problèmes d'optimisation NP-complets peuvent être résolus en temps polynomial pour les graphes de largeur arborescente bornée. Les algorithmes utilisés sont généralement basés sur la programmation dynamique et une décomposition arborescente du graphe (plus de détails dans les références [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF][START_REF] Borie | Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs[END_REF][START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF]). Une approche générale est proposée dans [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF] pour résoudre les problèmes de partitionnement dans les graphes de largeur arborescente bornée. Vu que notre problème, c.à.d. le problème de k-séparateur peut être considéré comme un problème de partitionnement où les partitions sont données par le k-séparateur et les composantes connexes restantes, l'approche de [START_REF] Telle | Algorithms for vertex partitioning problems on partial k-trees[END_REF] peut être utilisée dans notre cas.

Soit G 1 le graphe de chaise (ou fourchette) représenté sur la gauche de la figure 3.1.

Dans [START_REF] Milanic | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF] il est démontré que le problème de stable de poids maximal est résolu en temps polynomial si le graphe est ne contient pas G 1 . Lorsque k = 2, il est prouvé dans [START_REF] Gordon | The complexity of dissociation set problems in graphs[END_REF] que le graphe étendu H ne contient pas

Nous allons étendre ce résultat lorsque k ≥ 3. Plus précisément, nous montrons que Les résultats de cette section sont une conséquence directe des résultats de [START_REF] Hell | Independent packings in structured graphs[END_REF].

Considérons une collection L d'intervalles sur une ligne. Supposons que, pour chaque intervalle, on donne une courbe au-dessus de la ligne reliant les extrémités de l'intervalle, et en restant dans les limites de l'intervalle. Un graphe est de type interval-filament s'il est défini par l'intersection d'une telle collection d'intervalles [START_REF] Gavril | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF] (voir la figure 3.2). Le problème de stable max dans le cas de graphes de type "interval filament" se résout en temps polynomial [START_REF] Gavril | Maximum weight independent sets and cliques in intersection graphs of filaments[END_REF]. Le même résultat a été également prouvé dans [START_REF] Hell | Independent packings in structured graphs[END_REF] pour la classe de graphes de type weakly chordal [START_REF] Hayard | Weakly triangulated graphs[END_REF] (graphe tel que ni le graphe en soi-même ni son complémentaire contiennent un cycle induit de taille 5 ou plus) et la classe de graphes sans asteroidal-triple (graphes qui ne contenant pas de stable de taille 3 de telle sorte que, entre chaque paire de sommets de ce triplet, il existe un chemin qui les relie, et en évitant le voisinage du troisième sommet). L'inégalité suivante est évidemment valable pour S k (G).

Le problème du k-séparateur peut être formulé comme le programme entier suivant:

Cette formulation peut être renforcée par des inégalités de cycles impaires, cliques, etc. [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF].

Notons par LP 3 la relaxation linéaire de IP 3. Soit F 1 (resp. F 3) l'ensemble des solutions possibles de LP 1 (resp. LP 3) par rapport aux variables (x v ) v∈V .

Proposition A.1 L'inclusion suivante est vérifiée : F 3 ⊆ F 1.

A.3.1.2.c Formulation métrique

Une formulation métrique est proposée dans [START_REF] Spiksma | Disconnecting graphs by removing vertices: a polyhedral approach[END_REF]. En plus des variables (x i ) i∈V .

Considérons la variable x ij qui indique pour chaque paire de sommets {i, j} si i et j appartiennent à la même composante ou non. Plus précisément, x ij est égal à A.3. Propositions 0 si elles sont dans la même composante connexe. On peux voir que les inégalités triangulaires sont valides. Pour exprimer le fait qu'une composante connexe ne contient pas plus de k sommets, nous pouvons ajouter les contraintes j∈V \{i}

x ij ≥ n-k, ∀ i ∈ V . Enfin, il faut ajouter les contraintes qui imposent que si deux sommets sont adjacents et qu'ils ne sont pas dans le k-séparateur alors, ils appartiennent à la même composante :

Nous présentons ci-dessous une nouvelle formulation qui renforce la relaxation linéaire de IP 4.

A.3.1.2.d Formulation métrique projetée

Soit S un ensemble de sommets avec |S| ≥ k et soit i ∈ S. Pour chaque j ∈ S, notons par p ij ∈ P ij un chemin joignant i et j. Considérons l'inégalité suivante

Considérons maintenant la formulation basée sur les inégalités (A.2).

IP 7