Denis Cornaz
email: denis.cornaz@dauphine.fr

Fabio Furini
email: fabio.furini@dauphine.fr

Mathieu Lacroix
email: mathieu.lacroix@lipn.univ-paris13.fr

Enrico Malaguti
email: enrico.malaguti@unibo.it

A Ridha Mahjoub
email: ridha.mahjoub@dauphine.fr

Sébastien Martin
email: sebastien.martin@univ-lorraine.fr

The vertex k-cut problem

Keywords: Vertex Cut, Mixed-Integer Programming Models, Branch and Price, Exact Algorithms

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A vertex cut of a graph G = (V, E) is a strict subset of vertices V 0 ⊂ V such that the graph obtained from G by removing V 0 has at least two (non-empty and pair-wise disconnected) components. If the number of components is at least k, the vertex cut V 0 is called a vertex k-cut.

Given G and an integer k ≥ 2, the vertex k-cut problem is to find, if it exists, a vertex k-cut of minimum cardinality. Berger, Grigoviev and Zwaan [START_REF] Berger | Complexity and approximability of the k-way vertex cut[END_REF] showed that the problem is NP-hard (k being part of the input) but polynomial-time solvable for graphs of bounded treewidth. Ben Ameur and Didi Biha [START_REF] Ben-Ameur | On the minimum cut separator problem[END_REF] proved that, for k = 2, it is polynomial-time solvable as it amounts to computing |V | 2 maximum flows. A fixed-parameter algorithm for the vertex k-cut problem, considering the parameter k, would be an algorithm solving the 1

The Vertex k-cut Problem problem with a running time of the form f (k) × poly(|V |) where f (k) is any function and poly(|V |) is a polynomial in |V |. Marx [START_REF] Marx | Parameterized graph separation problems[END_REF] showed that such an algorithm is unlikely to exist as he proved the W [1]-hardness of the problem. However, the complexity for fixed k was an open question.

Despite its basic setting, the vertex k-cut problem has received limited attention according to ILP approaches. Let us detail the literature on problem variants, where one wants to minimize the number of vertices to be removed to partition a given graph. The k-separator problem is a variant where cardinality bounds are required. It consists in finding a vertex cut whose removal gives a graph where the size of each connected component is less than or equal to k. In [START_REF] Ben-Ameur | The k-separator problem[END_REF], the authors analyze the complexity on several classes of graphs. They also propose approximation algorithms, a formulation and a polyhedral study. Another variant of this problem exists where the cardinality constraints are not on the size of the connected components but on vertex sets. More precisely, the problem consists in finding a vertex cut V 0 such that V \ V 0 can be partitioned into two sets of cardinality less than or equal to k, and no edge is incident to both sets. Remark that each set may contain several connected components. This problem is NP-hard even for planar graphs [START_REF] Fukuyama | Np-completeness of the planar separator problems[END_REF] or maximum degree 3 graphs [START_REF] Bui | Finding good approximate vertex and edge partitions is nphard[END_REF]. A first polyhedral study on this problem is done in [START_REF] Balas | The vertex separator problem: a polyhedral investigation[END_REF] from which a Branch-and-Cut algorithm is derived [START_REF] Souza | The vertex separator problem: algorithms and computations[END_REF]. In [START_REF] Biha | An exact algorithm for solving the vertex separator problem[END_REF] the authors introduce valid inequalities based on a lower bound given by the number of disjoint paths between all pairs of vertices. For these inequalities, the authors analyze their facial structures and add these inequalities in a Branch-and-Cut algorithm. In the q-balanced vertex k-separator problem, the bound is not on the size of the sets but on their differences. More formally, one seeks for a vertex k-cut V 0 such that V \ V 0 can be partitioned into k pairwise disconnected sets V 1 , . . . , V k and |V i | -|V j | is at most q for all i = j ∈ {1, . . . , k}. Different integer linear programming formulations are given in [START_REF] Cornaz | Mathematical formulations for the balanced vertex k-separator problem[END_REF]. The multi-terminal vertex k-cut problem consists, given a set T ⊂ V of k terminals, in finding a vertex k-cut V 0 of G containing no terminal such that each component of G[V \ V 0 ] contains at most one terminal. In [START_REF] Marx | Parameterized graph separation problems[END_REF] Marx shows also the W [START_REF]Dimacs implementation challenges[END_REF]-hardness of this problem. A path-based formulation is given in [START_REF] Cornaz | The multi-terminal vertex separator problem: Polyhedral analysis and branch-and-cut[END_REF] for solving this problem and several inequalities are proposed. A polyhedral analysis is also performed and an efficient Branch-and-Cut algorithm is developed.

Several variants of problems where one wants to disconnect a graph have been considered where an edge set, instead of a vertex set, is removed. Among them, the most two famous problems are the k-cut and the multiway cut problems. The first one is the edge counterpart of our problem: it consists in finding a minimum set of edges the removing of which leads to at least k-connected components [START_REF] Barahona | On the k-cut problem[END_REF][START_REF] Goldschmidt | A polynomial algorithm for the k-cut problem for fixed k[END_REF][START_REF] Karger | An nc algorithm for minimum cuts[END_REF]. In the multiway cut problem [START_REF] Chopra | On the multiway cut polyhedron[END_REF][START_REF] Cygan | On multiway cut parameterized above lower bounds[END_REF][START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF][START_REF] Garg | Multiway cuts in directed and node weighted graphs[END_REF][START_REF] Garg | Multiway cuts in node weighted graphs[END_REF][START_REF] Thorup | Minimum k-way cuts via deterministic greedy tree packing[END_REF], a vertex subset S is given and one has to find minimum set of edges in order to separate each pair of vertices of S. Some generalizations of this latter problem, such as minimum 0-extension of graph metrics (that also generalizes the minimum (s, t)-cut problem), have been considered. In [START_REF] Karzanov | Minimum 0-extensions of graph metrics[END_REF][START_REF] Hirai | Discrete convexity and polynomial solvability in minimum 0-extension problems[END_REF] the classes of graphs for which the minimum 0-extension problem is tractable are presented.

The first contribution of this paper improves on Marx's results by showing that the vertex k-cut problem is NP-hard for any fixed k ≥ 3. Our second contribution is to investigate the hardness of the problem in practise, we report computational experiments on the problem using Integer Linear Programming (ILP) tools to solve it on DIMACS instances.

The paper is organized as follows. Section 2 is devoted to the NP-hardness proof of the vertex k-cut problem for any fixed k ≥ 3. In Section 3, we reformulate this problem as a stable set problem with additional constraints. We deduce a compact integer linear program based on this reformulation. In Section 4, we present a formulation with an exponential number of variables and a polynomial number of constraints. We also give a column generation scheme to solve the linear relaxation. We prove the effectiveness of this approach by showing that the subproblem is polynomial-time solvable by using flow techniques. Section 5 reports the experimental results we obtain by solving the two formulations, the first one by a general-purpose ILP solver and the second by a Branch-and-Price algorithm. The rest of this section is devoted to notation and assumption.

Notation. Throughout, K denotes the set of integers {1, ..., k} and G = (V, E) is a simple undirected graph with |V | = n and |E| = m. The complement of a node subset S is denoted S = V \S, and the complement of G is denoted G = (V, E), where E = {uv : uv / ∈ E}. We say that u and v are neighbours if there is an edge

uv ∈ E. A subset W ⊆ V of vertices is a clique of G, if any two vertices of W are neighbours, and it is a stable set of G if it is a clique in G. The cardinality of the largest stable set of G is denoted by α(G). A subset W ⊆ V of vertices is a vertex k-multiclique of G, if there is a k-partition π = {W 1 , ..., W k } of W such that
any two vertices in different sets of π are adjacent in G, with W i = ∅ for all i ∈ {1, ..., k}. For each W ⊆ V , we indicate by δ(W ) the subset of edges incident with exactly one vertex in W (i.e., all edges uv with u ∈ W, v ∈ V \ W ), and with E(W ) the subset of edges incident with two vertices in W (i.e., all edges uv with u, w ∈ W ). Finally, we indicate by δ(v) ⊆ E the subset of edges incident with v.

Assumption. In the rest of the paper, we will assume that α(G) ≥ k. This is clearly a necessary and sufficient condition for G to have a vertex k-cut. We assume that G is connected. We will also use implicitely the basic property that a vertex k-cut V 0 is a set of vertices such that V \ V 0 can be partitioned into k non-empty subsets V 1 , ..., V k that are pairwise disconnected, i.e., there is no edge between two subsets V i and V j for all i = j ∈ {1, . . . , k}.

Complexity

In this section, the NP-hardness of the vertex k-cut problem for any fixed k ≥ 3 is proved.

We start by observing that the problem is equivalent to the vertex k-multiclique problem which consists, given an undirected graph G = (V, E) and k ≥ 2, in determining a vertex k-multiclique of maximum cardinality.

Proposition 1 A vertex subset V 0 of a graph G = (V, E) is a vertex k-cut if and only if W = V \ V 0 is a vertex k-multiclique in the complement graph G.
We now state our complexity result.

Theorem 1 For any fixed k ≥ 3, the vertex k-cut problem is NP-hard.

Proof. In order to prove the theorem, it suffices to prove that the vertex 3-cut problem is NP-hard. Indeed, G has a vertex k-cut of size s if and only if G has a vertex (k + 1)-cut of size s, where G is obtained by adding an isolated vertex to G. The basic idea of the proof is to reduce an instance of the NP-hard maximum stable set problem in tripartite graphs [START_REF] Phillips | The asymmetric median tree: a new model for building consensus trees[END_REF] into an instance of the vertex 3-cut problem.

By Proposition 1, it suffices to prove that the vertex 3-multiclique problem is NP-hard. We actually prove that this problem is already NP-hard in the class of tripartite graphs. To this end, we will use a reduction from the maximum stable set problem in tripartite graphs, which is NP-hard by Lemma 6 in [START_REF] Phillips | The asymmetric median tree: a new model for building consensus trees[END_REF]. Let G = (V 1 ∪ V 2 ∪ V 3 , E) be a tripartite instance of the maximum stable set problem. Since every isolated vertex belongs to all maximal stable sets, it is still NP-hard to solve tripartite instances with additional isolated vertices, hence, without loss of generality, we can suppose that V i contains an isolated vertex v i for each i ∈ {1, 2, 3}. We define the instance G

= (V 1 ∪ V 2 ∪ V 3 , Ẽ) of the 3-multiclique problem where Ẽ = {uv : u ∈ V i , v ∈ V j , i = j, uv /
∈ E}. (In Figure 2, the white vertices represent a maximal stable set of G (left graph). The same set corresponds to a maximal 3-multiclique on G (right graph).) We claim that a vertex subset S is a stable set of G containing {v 1 , v 2 , v 3 } if and only if S is a vertex 3-multiclique of G containing {v 1 , v 2 , v 3 }. Indeed, by construction, two vertices u ∈ V i ∩ S and v ∈ V j ∩ S where i = j are adjacent in G. Thus S is a vertex 3-multiclique in G. The converse is also true. Since any maximum stable set of G and any maximum vertex 3-multiclique of G contain {v 1 , v 2 , v 3 }, the proof is done.

u 1 1 u 1 2 u 1 3 u 1 4 v 1 u 2 1 u 2 2 u 2 3 v 2 u 3 1 u 3 2 u 3 3 u 3 4 u 3 5 v 3 V 1 V 2 V 3 u 1 1 u 1 2 u 1 3 u 1 4 v 1 u 2 1 u 2 2 u 2 3 v 2 u 3 1 u 3 2 u 3 3 u 3 4 u 3 5 v 3 V 1 V 2 V 3

Compact formulation

In this section, we show that the vertex k-cut problem can be reformulated as a maximum stable set problem on a specific k-partite graph with additional requirements. We also derive a compact integer linear program based on this reformulation.

Let G = (V, E) and k ≥ 2 be an instance of the vertex k-cut problem. As previously noted, a subset V 0 ⊂ V is a vertex k-cut of G if and only if V \ V 0 can be partionned into k nonempty pairwise disconnected sets. Hence, the vertex k-cut problem is equivalent to finding k nonempty disjoint sets V 1 , . . . , V k of V which are pairwise disconnected such that

| i∈K V i | is maximum.
We construct a k-partite graph G = (V , E ) so that the vertex k-cut problem on G reduces to the maximum stable set on G . Figure 3 gives an illustration of this equivalence. The graph on the left is G. The set V 0 of white vertices corresponds to a 3-vertex cut and

{V 1 , V 2 , V 3 } with V 1 = {v 3 }, V 2 = {v 4 } and V 3 = {v 2 , v 5 } is a partition of V \ V 0 into 3 pairwise disconnected sets.
The graph on the right corresponds to G . The white vertices form the stable set associated with Formally the construction of G is as follows. The set V is obtained by considering k copies v 1 , . . . , v k of every vertex v ∈ V . We define the k-partition of V as π = {V 1 , . . . , V k } with V i = {v i : v ∈ V } for all i = 1, . . . , k. In other words, V i corresponds to a copy of V . The edge set E is the union of two sets E α and E β . E α = {v i v j : i = j ∈ K} is the edge set obtained by considering a clique between all the copies of a same vertex v ∈ V . For E β , we consider for each uv ∈ E an edge between every copy of u and every copy of v. Hence, E β = {u i v j : uv ∈ E, i = j ∈ K}. There is a 1-to-1 correspondence between nonempty pairwise disconnected disjoint sets V 1 , . . . , V k of V and stable sets of G intersecting each V i , i ∈ K. Indeed, let V 1 , . . . , V k satisfying the aforementioned requirements. Let S ⊆ V be the set obtained by taking in V i the copies of the vertices in V i for all i ∈ K. S is a stable set because no edge exists between V i and V j and

{V 1 , V 2 , V 3 }. v 1 v 2 v 3 v 4 v 5 v 6 G v 1 1 v 1 2 v 1 3 v 1 4 v 1 5 v 1 6 v 2 1 v 2 2 v 2 3 v 2 4 v 2 5 v 2 6 v 3 1 v 3 2 v 3 3 v 3 4 v 3 5 v 3 6 V 1 V 2 V 3 G
V i ∩ V j = ∅ for i = j ∈ K. Moreover, S intersects every V i , i ∈ K, since V 1 , . . . , V k are nonempty. Finally S = | i∈K V i |.
The converse also holds which implies the result.

We now give a formulation of the vertex k-cut problem with an integer linear program. By the previous reformulation, we look for a stable set S of G intersecting every V i of the k-partition. For all vertices v ∈ V and for all integer i ∈ K, let us associate a binary variable x i v such that:

x i v = 1 if copy v i ∈ V i of vertex v ∈ V belongs to S 0 otherwise i ∈ K, v ∈ V.
The first natural compact ILP formulation (called ILP C ) reads as follows:

(ILP C ) max i∈K v∈V x i v (1)
i∈K x i v ≤ 1 v ∈ V, (2)
x i u + j∈K\{i} x j v ≤ 1 i ∈ K, uv ∈ E, (3)
v∈V x i v ≥ 1 i ∈ K, (4)
x i v ∈ {0, 1} i ∈ K, v ∈ V. (5)
The objective function maximizes the size of S. Constraints ( 2) and ( 3) are the clique constraints associated with cliques of E α and edges of E β , respectively. Constraints (4) impose that S intersects each V i for i ∈ K.

By replacing constraints (5) with

x i v ≥ 0 i ∈ K, v ∈ V, (6)
we obtain the Linear Programming relaxation of ILP C , that will be denoted as LP C in what follows. Descriptive natural ILP models are known to produce weak linear programming relaxations as the following proposition shows: Proof. Constraints (2) impose a trivial upper bound of value n. By setting

Proposition 2 An optimal solution to LP C is x i v = 1 k , i = 1, . . . , k, v ∈ V ,
x i v = 1 k , i = 1, . . . , k, v ∈ V ,
the objective function obtains exactly the value n and all the other constraints are satisfied by construction.

In order to improve the strength of the linear programming relaxation, and to remove the symmetry of ILP C , in the next section we design a new formulation for the vertex k-cut problem.

Exponential-size formulation

In this section, we derive an alternative formulation for the vertex k-cut problem having an exponential number of variables with respect to the input size. Let S = {S ⊆ V, S = ∅} be the family of all non-empty subsets of vertices of V .

For all subsets S ∈ S , let us associate a binary variable ξ S such that:

ξ S = 1 if S corresponds to one of the k disconnected subsets of G 0 otherwise S ∈ S .
The vertices that do not appear in any selected subset are assigned to the vertex cut. In the following we let C be an edge-covering family of cliques of G, that is, a family of cliques so that for each edge uv ∈ E, there is at least one clique C ∈ C containing both u, v ∈ C. The exponential-size ILP formulation for the vertex k-cut problem reads as follows

(ILP E ) max S∈S |S|ξ S (7)
S∈S :v∈S

ξ S ≤ 1 v ∈ V, (8)
S∈S :C∩S =∅ ξ S ≤ 1 C ∈ C , (9)
S∈S ξ S = k (10) ξ S ∈ {0, 1} S ∈ S . (11)
The objective function [START_REF] Ben-Ameur | The k-separator problem[END_REF] maximizes the sum of the cardinalities of the selected subsets S of vertices, which is equivalent to minimize the cardinality of the vertex cut. Constraints [START_REF] Berger | Complexity and approximability of the k-way vertex cut[END_REF] impose that each vertex i ∈ V does not appear in more than one of the selected subsets. Constraints [START_REF] Biha | An exact algorithm for solving the vertex separator problem[END_REF] impose that, for each clique C ∈ C , at most one subset containing any vertex of the clique can be selected. Constraint [START_REF] Bui | Finding good approximate vertex and edge partitions is nphard[END_REF] imposes that exactly k subsets are selected. Constraints [START_REF] Chopra | On the multiway cut polyhedron[END_REF] impose the variables to be binary, so, finally, by relaxing the integrality of constraints [START_REF] Chopra | On the multiway cut polyhedron[END_REF] to

ξ S ≥ 0 S ∈ S , (12)
we obtain the Linear Programming relaxation of ILP E , that is denoted as LP E in what follows.

A Branch-and-Price Algorithm

In this section we describe a Branch-and-Price algorithm which is designed to solve ILP E . The exact algorithm is composed by two main components, i.e., a Column Generation (CG) algorithm to solve LP E , and a branching scheme. We treat these two aspects in the next sections.

4.1.1 Solving the Linear Programming Relaxation of ILP E Model ( 7)-( 11) has exponential size, thus a column generation procedure is necessary to solve LP E .

The master problem (MP) can be initialized with the n subsets of V containing a single vertex. Since we assumed that G contains a stable set of cardinality k, this initialization assures the existence of a feasible solution to start the column generation. Additional variables needed to optimally solve the MP are then generated by separating the associated dual constraints. The pricing problem (PP) (see, e.g., [START_REF] Desaulniers | Column generation[END_REF] for definition and more details on column generation) can be solved efficiently as described in the following.

At each column generation step, the optimal values λ

* ∈ R V + , π * ∈ R C + , γ * ∈ R (re- spectively)
of the dual variables associated with constraints ( 8), ( 9), (10) (respectively) are given. The separation of a violated dual constraint is equivalent to find a non-empty subset S * ∈ S such that

v∈S * λ * v + C∈C :C∩S * =∅ π * C + γ * < |S * |
which can be reformulated as

v∈S * ν * v - C∈C :C∩S * =∅ π * C > γ * , (13)
where

ν * v = 1 -λ * v .
If such a subset exists, the corresponding variable ξ S * is added to the MP, and the procedure is iterated; otherwise, the MP is solved to proven optimality. Hence PP amounts to find a S * maximizing the left-term in [START_REF] Cornaz | The multi-terminal vertex separator problem: Polyhedral analysis and branch-and-cut[END_REF] and to check whether or not it is bigger or not than the right-term. It can be modeled as a Binary Linear Program using variables x v (v ∈ V ), which define S * , and variables y C (C ∈ C ), each of which takes value 1 if clique C intersects set S * , as follows:

max v∈V ν * v x v - C∈C π * C y C ( 14
)
y C ≥ x v v ∈ C ∈ C , (15)
v∈V x v ≥ 1 ( 16
)
x v ∈ {0, 1} v ∈ V, (17)
y C ∈ {0, 1} C ∈ C . (18)
Constraints [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF] impose y C = 1 (C ∈ C ) if at least a vertex v of a clique C belongs to S * ; while constraints ( 16) impose S * is not empty. If the value of the optimal solution of the PP is larger than γ * , S * = {v ∈ V, x * v = 1}, and the associated variable z S * is added to the MP. Note that, since π C ≥ 0 (C ∈ C ) and variables x v (v ∈ V ) are binary, we can relax constraints [START_REF] Fukuyama | Np-completeness of the planar separator problems[END_REF] to y C ≥ 0 (C ∈ C ).

The PP can be interpreted as follows: Given G = (V, E), a profit ν * v for each v ∈ V (possibly negative) and a penalty π * C ≥ 0 for each C ∈ C , the problem aims at selecting a non-empty subset of vertices of maximum profit; the penalty π * C associated with a clique C is paid if at least one of its vertices is selected. A vertex v with ν * v ≤ 0 can be removed together with its incident edges. If a clique C ∈ C is reduced to a single vertex u by the removal, then, π C is subtracted from the profit ν * u of vertex u. The procedure is iterated until all vertices have positive profit. In case all vertices have negative profit ν * , or all vertices are removed, the PP problem reduces to finding the vertex u = arg max v∈V {ν * v -C∈C :v∈C π * C }. The following proposition characterises the complexity of the PP.

Proposition 3 The PP is polynomial-time solvable.

Proof. In the PP we are looking for a non-empty subset of vertices. Let us define PP∪∅ a relaxation of the PP, where also the empty set is admitted as solution. Given a polynomialtime algorithm for the PP∪∅, we can select a vertex v ∈ V which is forced to be in S * , and then apply the algorithm to the subgraph of G induced by V \ {v}. By applying this procedure for each v ∈ V , in n iterations we obtain the optimal solution to the PP.

It remains to show that PP∪∅ is polynomially solvable. This can be done by observing that the PP∪∅ can be formulated by removing constraint [START_REF] Souza | The vertex separator problem: algorithms and computations[END_REF] from model ( 14)- [START_REF] Fukuyama | Np-completeness of the planar separator problems[END_REF]. The resulting model structure is the same as the generic structure described in [START_REF] Barahona | Plant location with minimum inventory[END_REF], model [START_REF] Berger | Complexity and approximability of the k-way vertex cut[END_REF]. A solution method for the latter model is given in [START_REF] Barahona | Plant location with minimum inventory[END_REF]. (The latter consists in solving a min-cut/max-flow problem on a network with one node associated with each variable, plus a source and a sink node as explained below).

In the case of our problem, we have a network N = (W, A), where the node set is W = {s, t} ∪ V ∪ {u C , C ∈ C }, i.e., in addition to the vertex set V of G, there are a source and a sink node, and a node u C for each clique C ∈ C .

The arc set is defined below:

• For each v ∈ V there is an arc (s, v) with capacity ν * v , • For each C ∈ C there is an arc (C, t) with capacity π * C , • For each C ∈ C and each v ∈ C, there is an arc (v, C) with infinite capacity.
There is a one-to-one correspondence between st-cuts of finite capacity in N , and feasible solutions of ( 14)- [START_REF] Fukuyama | Np-completeness of the planar separator problems[END_REF]. For a cut of capacity L, the responding solution of ( 14)-( 18) has value

C∈C π * C -L.
Hence, an optimal solution to ( 14)-( 18) can be obtained from a min-cut on a network N having n + |C | + 2 nodes.

Corollary 1 An optimal solution to the linear relaxation LP E of the exponential-size integer formulation ILP E of the minimum vertex k-cut problem can be computed in polynomial time.

Proof. Since the pricing problems PP ask for the solution of n = |V | min-cut problems, then solving the master MP (and, eventually, LP E ) is polynomial time solvable.

In case C is exactly the set of edges of the graph G (which is the only possible form of C for a triangle free graph), a solution method based on solving a min-cut problem on a smaller network having n + 2 nodes is described in the Appendix. Finally, let us mention that the constraint matrix of ( 15) is totally unimodular, as observed in [START_REF] Cornaz | Mathematical formulations for the balanced vertex k-separator problem[END_REF] for the case of edge constraints. This gives an alternative proof of polynomial-time solvability for the PP.

A branching scheme for ILP E

When the optimal solution of the master problem (MP) associated with the linear relaxation of model ILP E for the min vertex k-cut problem is fractional, a branching scheme is necessary in order to obtain an integer solution.

Let ξ * be the current (fractional) solution of the MP. A two-level branching scheme has to be considered. First we branch by imposing that, for each vertex v ∈ V , either v is in the vertex k-cut V 0 or it belongs to the vertex-set S of some component of the subgraph of G induced by V \ V 0 . This is in general not enough to define an integer solution, indeed, even if the vertex k-cut V 0 is well defined by

V 0 = v ∈ V : S∈S :v∈S ξ * S = 0 ,
it does not imply that the solution is 0-1 valued. We impose a second level branching, where, for two vertices u and v outside V 0 , we impose that either u and v are in the same component, or they belong to different ones.

In the first branching, for each vertex v ∈ V , we check if it is partially included in the components and the vertex cut, more precisely, if

0 < S∈S :v∈S ξ * S < 1. ( 19
)
In case of multiple partially included vertices, we branch on the vertex v for which the sum in ( 19) is closer to 1. Ties are broken randomly. Two subproblems are then created from the current one:

• in the first subproblem, we impose that v is in the vertex cut, by modifying the associated constraint [START_REF] Berger | Complexity and approximability of the k-way vertex cut[END_REF] to

S∈S :v∈S ξ S = 0;
we also modify the pricing procedure in order to forbid the selection of vertex v by modifying the cost structure of the associated min-cut problem;

• in the second subproblem, we impose that v is not in the vertex cut, by modifying the associated constraint [START_REF] Berger | Complexity and approximability of the k-way vertex cut[END_REF] to

S∈S :v∈S ξ S = 1;
the pricing procedure is unchanged.

Once V 0 is defined, then ξ * is still fractional if and only if we can find two vertices u, v so that 0

< S∈S :u,v∈S ξ * S < 1. (20)
(It holds more generally for 0-1 constraints of the form Aξ * = 1, see [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF]).

In case more than one such pair of vertices exist, we branch on the pair for which the sum in inequality ( 20) is closer to 1. Ties are broken randomly. Two subproblems are then created from the current one:

• in the first subproblem, we impose that u and v are in the same component; this can be obtained by contracting {u, v} in the pricing subproblem, that is, creating a supervertex w representing both u and v and such that δ(w) = δ(u) ∪ δ(v) (and removing u, v);

• in the second subproblem, we impose that u and v are in different components; this can be obtained by adding to the pricing subproblem an incompatibility constraint between u and v. In this case the subproblem cannot be formulated as a min-cut/maxflow problem, and we have to solve the MIP formulation ( 14)-( 18) with the additional constraint

x v + x u ≤ 1.
In this case the modified pricing problem might be NP-hard.

In our Branch-and-Price algorithm we first define the vertices in the vertex cut, i.e., we apply the first branching rule. Then, in case the solution is still fractional, we apply the second branching rule. After branching, the variables that are incompatible with the branching decision are removed from the children nodes. The following proposition states that the two proposed branching rules define a complete branching scheme for ILP E : Proposition 4 The two branching rules applied in sequence provide a complete branching scheme for model ILP E .

Proof. The rows of the constraints (8) associated with vertices forced out of the vertex cut, after the application of the first branching rule, are equalities with binary coefficients and right-and-side equal to 1. In this case, if a basic solution ξ * is fractional, then there exist u and v such that [START_REF] Garg | Multiway cuts in node weighted graphs[END_REF] holds. This result allows to conclude that, if a solution is fractional after the first branching rule is applied, then we can determine two vertices for applying the second branching rule.

Comparison of the strength of the LP relaxations of the two formulations

This section discusses the relation between the two formulations proposed for the vertex k-cut problem.

Proposition 5 Even when C = E, the bound for the vertex k-cut problem provided by the optimal solution value of the extended formulation LP E strictly dominates the corresponding bound provided by the compact formulation LP C .

Proof. Given a feasible solution ξ of LP E , we can construct a feasible solution x of LP C with same objective function value as follow:

xi v = 1 k S∈S :v∈S ξS i ∈ K, v ∈ V.
We first show that the two solutions have the same objective function value:

i∈K v∈V xi v = k∈K 1 k v∈V S∈S :v∈S ξS = S∈S v∈S ξS = S∈S |S| ξS .
It is straightforward to check that constraints (2) are satisfied. For each edge uv ∈ E and for i = j ∈ K:

xi u + j∈K\{i} xj v = 1 k S∈S :u∈S ξS + k -1 k S∈S :v∈S ξS ≤ 1,
i.e., constraints (3) are satisfied. Finally constraints (4) are satisfied since for each i ∈ K:

v∈V xi v = v∈V 1 k S∈S :v∈S ξS ≥ 1 k S∈S ξS = 1
To see that the domination can be strict, consider now solving the vertex k-cut problem with k = 3 for a cycle of 6 vertices. An optimal solution to LP C is x i v = 1 3 , v ∈ V, i = 1, . . . , 3, with value 6, while an optimal solution to LP E has value 3.

In the remaining of this section we discuss with an example the quality of the linear relaxation of ILP E , when constraints (9) are expressed for a family of cliques C or for the edge set E, respectively.

Let us consider the graph G = (V, E) of Figure 3. The example graph has 6 vertices

(v 1 , v 2 , v 3 , v 4 , v 5 , v 6 ) and 6 edges (v 1 v 2 , v 1 v 3 , v 1 v 5 , v 3 v 4 , v 4 v 5 , v 5 v 6
). One optimal solution to the min vertex 3-cut problem is obtained by removing vertices v 3 and v 5 , and the maximum in ILP E is then 4. By defining the clique family C = {{v 1 , v 3 , v 5 }, {v 1 , v 2 }, {v 3 , v 4 }, {v 5 , v 6 }}, the optimal solution of LP E is integer of value 4 and it is given by ξ S 1 = ξ S 2 = ξ S 3 = 1 where S 1 = {v 4 }, S 2 = {v 6 }, S 3 = {v 1 , v 2 }. If we consider instead C = E, the optimal solution of LP E is not integer and has value 4.5. This second solution is given by ξ

S 1 = ξ S 2 = ξ S 3 = ξ S 3 = ξ S 4 = ξ S 6 = 0.5 where S 4 = {v 2 }, S 5 = {v 5 , v 6 }, S 6 = {v 3 , v 4 }.
This example shows a case where a strictly better bound is obtained by considering maximal cliques in C .

v 4 v 3 v 2 v 1 v 5 v 6

Computational experiments

Despite the relevance of the vertex k-cut problem, to the best of our knowledge, no previous computational study on exact approaches appeared in the literature. Thus, laking a previous approach to compare the performance of our Branch-and-Price, with these experiments we wish to assess what is the size of instances that can be tackled by a "standard" approach, relying on the use of a state-of-the-art MIP solver, and whether an approach based on an extended formulation can improve on the standard one, or can eventually be complementar to the standard one, that is, by effectively solving instances with different features. Indeed, the development of a tailored solution approach (as our Branch-and-Price algorithm) is justified when it can enlarge the set of instances for which an optimal solution can be computed, or at least can improve information on upper or lower bounds. With this in mind, we first tune the performance of the two approaches on two sets of widely used graph instances from the literature, and then consider a further set of instances specifically collected for variants of vertex separator problems. In detail, in our experiments we evaluate:

• The computational performance of the compact formulation ILP C of Section 3, solved via a general purpose ILP solver;

• The computational performance of the extended formulation ILP E of section 4, solved via the Branch-and-Price algorithm described in Section 4.1;

• The size of solvable vertex k-cut problem instances, in terms of number of vertices of the graph;

• The effect of the number of subsets k of the partition on the relative performance of the two mentioned exact methods.

Experimental setting. The compact formulation ILP C is enhanced by a preprocessing phase in which a subset of variables is removed so as to reduce the symmetry of the formulation and to improve the quality of the associated linear programming relaxation. In this preprocessing, we search for k -1 vertex-disjoint cliques C 1 , . . . , C i , . . . , C k-1 of the graph G, and remove the following variables

x h v , i = 1, . . . , k -1, v ∈ C i , h = i + 1, . . . , k. (21)
Indeed, two vertices u, v of a clique cannot be in two different subsets V i and V j . Then for all solutions we can reordering the sets V 1 , ..., V k to ensure that each vertex of a clique C i must be in one set V j j ≤ i or in the separator. Thus we can remove the variables [START_REF] Goldberg | A new approach to the maximum-flow problem[END_REF] to reduce the symmetry. The resulting model is then solved by using the MIP solver of Cplex 12.6.0 in single-thread mode and default parameter setting. The resulting solution method is denoted as Cplex + reduction in what follows.

The extended formulation ILP E is solved via the Branch-and-Price algorithm, initialized with n variables ξ S , where S = {v}, v ∈ V . At each column-generation iteration, linear programs are solved with Cplex 12.6.0. The pricing subproblem, formulated as a mincut/max-flow problem, is solved by means of the pre-flow algorithm by Goldberg and Tarjan [START_REF] Goldberg | A new approach to the maximum-flow problem[END_REF]. We very rarely observed a branching requiring to solve the subproblem as a MIP (i.e., introducing incompatibility constraints between vertices). The exploration of the branching tree is performed in a depth-first fashion.

The experiments have been performed on a computer with a 3.40 Ghz 8-core Intel Core i7-3770 processor and 16Gb RAM, running a 64 bits Linux operating system. Both exact approaches were tested with a time limit of 3600 seconds of computing time.

Test-bed of instances. In the computational experiments, we considered one class of classical graph instances from DIMACS challanges, divided into two sets, and an additional class of instances specifically collected for variants of vertex separator problems, divided into three sets. All considered instances having up to 150 vertices. For the first class of instances, that are also used for tuning the solution approaches, we only consider graphs for which the size of the largest stable α(G) is at least 5. For the latter class, we only consider instances for which α(G) is at least 15. Instances are listed in Table 1. In the table, after the instance name, we report the number of vertices n, the number of edges m, the density d, and the size of largest stable set in the graph α(G). This last parameter determines whether a graph instance is feasible for a given value of k, i.e., α(G) ≥ k; and the corresponding stable set provides a feasible vertex k-cut problem solution.

The first class is composed by a set of 42 instances originally proposed for Maximum Clique, Graph Coloring, and Satisfiability in the second DIMACS challenge [START_REF]Dimacs implementation challenges[END_REF]. They have from 11 to 149 vertices, with densities varying from 3.35 to 96.79. The α(G) parameter varies from 5 to 80. It includes a second set, composed by 7 instances originally proposed for Graph Partitioning and Graph Clustering in the tenth DIMACS challenge [START_REF]Dimacs implementation challenges[END_REF]. They have from 34 to 115 vertices, with densities varying from 6.84 to 22.94. The α(G) parameter varies from 17 to 53.

The second class is composed by three sets of instance proposed in [START_REF] Souza | The vertex separator problem: algorithms and computations[END_REF] and collects intersection graphs of the coefficient matrices of systems of linear equations from different applications, including Physics, Electrical Engineering, Meteorology, Economics and Mathematics. The intersection graph of a matrix has one vertex for each column of and an edge between a pair of vertices if there exists an equation in the system where both variables have a nonzero coefficient. When the linear system is solved by some decomposition method, it will be divided into smaller subsystems that are solved separately. However, the solution of the whole system asks for merging the solutions of the subsystems (i.e., the same variables must take the same values in all the subsystems), and the cost of this tasks increases with the number of variables that appear in more than one subsystem. If one wants to partition the equations into k subsystems, the problem of minimizing the number of common variables can be formulated as a vertex k-cut problem. The instances in the second class, denoted as Intersection Graph Instances in the following, have from 49 to 136 vertices, with densities varying from 5.03 to 59.72. The α(G) parameter varies from 15 to 45. For more details on the second class, the reader is referred to [START_REF] Souza | The vertex separator problem: algorithms and computations[END_REF].

Computational performance on the DIMACS instances. In Tables 2 and3 we consider values of k = 5, 10, 15, 20, and report, for Branch and Price and Cplex + reduction, the CPU time is seconds (tl for time limit) and the associated number of explored nodes. For each instance and for each value of k, we report in bold the fastest method. Missing lines correspond to infeasible instances. At the end of each block, we report the number of instances solved to optimality by each method, with respect to the total.

• For k = 5, there are 42 2nd-DIMACS and 7 10th-DIMACS instances, 49 feasible instances in total. For 9 instances, no method could find the optimal solution within time limit; the Branch and Price could solve 26 out of 49 instances and is the fastest method in 9 cases; the Cplex + reduction could solve 40 out of 49 instances and is the fastest method in 30 cases; 13 instances are solved by Cplex + reduction while Branch and Price fails. For the solved instances, the number of nodes explored by the Branch and Price is not larger than 9651 but typically smaller than 100, Cplex + reduction in contrast tends to explore a much larger number of nodes (up to 365825), and on average needs thousands of nodes.

• For k = 10, there are 31 2nd-DIMACS and 7 10th-DIMACS instances, 38 feasible instances in total. For 10 instances, no method could find the optimal solution within time limit; the Branch and Price could solve 24 out of 38 instances and is the fastest method in 18 cases; the Cplex + reduction could solve 20 out of 38 instances and is the fastest method in 10 cases; 8 instances are solved by Branch and Price while Cplex + reduction fails; 4 instances are solved by Cplex + reduction while Branch and Price fails. For the solved instances, the number of nodes explored by the Branch and Price is not larger than 288, Cplex + reduction explores up to 405857 nodes, and on average needs much more nodes to solve the same graph instance for k = 10 than for k = 5.

• For k = 15, there are 24 2nd-DIMACS and 7 10th-DIMACS instances, 31 feasible instances in total. For 8 instances, no method could find the optimal solution within time limit; the Branch and Price could solve 21 out of 31 instances and is the fastest method in 20 cases; the Cplex + reduction could solve From these results we can conclude that Cplex + reduction has an average good performance for k = 5, and has increasing difficulties for larger values of k. A partial explanation can be found in the increase in the number of variables (n more variables for each incremental value of k). For k = 5, Cplex + reduction outperforms Branch and Price. For Branch and Price, an opposite behaviour is experienced when increasing the value of k. In this case, the performance of the method is improved. For example, instance polbooks needs 2036.05 CPU seconds for k = 5, while 330.90, 25.94, and 3.13 CPU seconds are needed for k = 10, 15 and 20, respectively. For k = 10, 15 and 20, Branch and Price outperforms then Cplex + reduction.

Gaps. In Table 4 we report, for each value of k, the value of the optimal or best known solution (column opt * ), and the linear relaxation and optimality gaps for the 10th-DIMACS instances. The linear programming relaxation lp gap is computed with respect to the optimal solution value opt as 100• lp val -opt opt , where lp val is the value of the linear programming relaxation of the corresponding formulation (or the best know solution). For instances for which the optimal solution value is not known, the lp gap is not reported. A "-" is reported when the time limit is incurred before the linear relaxation is computed. The optimality gap opt gap is computed as 100

• U B val -LB val U B val
, where U B val and LB val are the values of the best upper bound and of the incumbent solution of the corresponding method when the time limit is reached (0.00 for solved instances). The same figures are omitted for the 2th-DIMACS instances, because they have a similar pattern. For the ILP E , the opt gap is computed using LB val = lp val since the bound is never updated during the search tree which is explored in a depth-first fashion (LB val = U B val for the instances solved to proven optimality).

From the table we observe that the formulation ILP E is characterized by a much stronger linear programming relaxation. The value of its lp gap is not affected by the value of k, and ranges between 0.0 and 6.43. This explains the fact that Branch and Price explores on average a much smaller number of nodes, and justifies the computational effort spent in column generation. On the other hand, the quality of the lp gap of ILP C deteriorates when k increases, and can be as large as 42.60. Clearly, computing this bound is associated with a smaller computational effort, and many nodes can be explored in short CPU time. For From these results we can conclude that for the Intersection Graph instances Cplex + reduction and Branch and Price have similar performance. However, the two solution methods are highly complementar: there are 23 instances that can be solved to optimality by one method only.

Gaps. In Table 6 we report, for each value of k, the value of the optimal or best known solution (column opt * ), and the linear relaxation and optimality gaps for the Intersection Graph instances. From the table we observe that, also for the Intersection Graph instances, of Min-Cut Max-Flow problems. We computationally compared the performances of the two formulations on benchmark instances from the literature. The outcome of these experiments is that the Branch-and-Price algorithm outperforms the direct use of a general-purpose ILP solver on the compact formulation for large values of k (high number of disconnected subsets of the partition). For small values of k instead, directly tackling the compact formulation remains the best option.

Hence, actually, the PP∪∅ amounts to min 2ν * (S) + π * (δ(S)) + v∈S π * (δ(v)). This problem can be solved as a min-cut problem on network with source node s, sink node t, one node for each v ∈ V and the arc set defined below:

• For each v ∈ V , there is an arc (s, v) with capacity 2ν * v ; • For each edge uv ∈ E, there are an arc uv and an arc vu with capacity π * uv ; • For each node v ∈ V , there is an arc (v, t) with capacity π * (δ(v)).

In this case, the PP∪∅ can be solved in polynomial-time as a min-cut problem (equivalent to max-flow) on the above described network, having n + 2 nodes.

Figure 1 :

 1 Figure 1: Reduction from the maximum stable set problem in tripartite graphs to the 3multiclique problem.

Figure 2 :

 2 Figure 2: Transformation of the 3-vertex cut problem into a specific maximum stable set problem.

  and has value n = |V |.

Figure 3 :

 3 Figure 3: A graph G and an optimal solution to the vertex k-cut problem with k = 3. Removing the white vertices disconnects G in 3 components.

Table 1 :

 1 Instance Featuresand Price fails. For the solved instances, the number of nodes explored by the Branch and Price is not larger than 82. Cplex + reduction needs to explore on average several thousands of nodes.• For k = 20, there are 22 2nd-DIMACS and 6 10th-DIMACS instances, 28 feasible instances in total. For 8 instances, no method could find the optimal solution within time limit; the Branch and Price could solve 20 out of 28 instances and is the fastest method in 19 cases; the Cplex + reduction could solve 7 out of 28 instances and is the fastest method in 1 case; 12 instances are solved by Branch and Price while Cplex + reduction fails. For the solved instances, the number of nodes explored by the Branch and Price is not larger than 249. Cplex + reduction needs to explore on average several thousands of nodes and is able to solve only few instances. All instances solved by Branch and Price require less than 12.23 CPU seconds, except one that needs 460.07 seconds.

		n	m	d	α(G)		n	m	d	α(G)
	2nd-DIMACS					2nd-DIMACS
	myciel3	11	20	36.36	5	myciel6	95	755	16.91	47
	myciel4	23	71	28.06	11	queen8 12	96	1368	30.00	8
	queen5 5	25	160	53.33	5	mug100 1	100	166	3.35	33
	1-FullIns 3	30	100	22.99	14	mug100 25	100	166	3.35	33
	queen6 6	36	290	46.03	6	queen10 10	100	1470	29.70	10
	2-Insertions 3	37	72	10.81	18	4-FullIns 3	114	541	8.40	55
	myciel5	47	236	21.83	23	games120	120	638	8.94	22
	queen7 7	49	476	40.48	7	queen11 11	121	1980	27.27	11
	2-FullIns 3	52	201	15.16	25	r125.1	125	209	2.70	49
	3-Insertions 3	56	110	7.14	27	DSJC125.1	125	736	9.50	34
	queen8 8	64	728	36.11	8	r125.5	125	3838	49.52	5
	1-Insertions 4	67	232	10.49	32	DSJC125.5	125	3891	50.21	10
	huck	74	301	11.14	27	r125.1c	125	7501	96.79	7
	4-Insertions 3	79	156	5.06	39	miles250	128	387	4.76	44
	jean	80	254	8.04	38	miles500	128	1170	14.39	18
	3-FullIns 3	80	346	10.95	37	miles750	128	2113	26.00	12
	queen9 9	81	1056	32.59	9	miles1000	128	3216	39.57	8
	david	87	406	10.85	36	miles1500	128	5198	63.95	5
	mug88 1	88	146	3.81	29	anna	138	493	5.22	80
	mug88 25	88	146	3.81	29	queen12 12	144	2596	25.21	12
	1-FullIns 4	93	593	13.86	45	2-Insertions 4	149	541	4.91	74
	10th-DIMACS					10th-DIMACS
	karate	34	78	13.90	20	polbooks	105	441	8.08	43
	chesapeake	39	170	22.94	17	adjnoun	112	425	6.84	53
	dolphins	62	159	8.41	28	football	115	613	9.35	21
	lesmis	77	254	8.68	35
	MM-I					MM-HD
	bcspwr02	49	177	15.05	16	L80.cavity01	80	1201	38.01	31
	impcol	59	329	19.23	20	L80.wm1	80	1786	56.52	15
	dwt	59	256	14.96	15	L100.cavity01	100	1844	37.25	36
	can62	62	210	11.11	18	L100.wm1	100	2956	59.72	17
	dwt72	72	170	6.65	24	L100.wm3	100	2934	59.27	15
	ash219	85	219	6.13	29	L120.cavity01	120	2972	41.62	36
	dwt87	87	726	19.41	16	L120.wm2	120	3387	47.44	23
	MM-II					MM-II
	ash331	104	331	6.18	30	L125.gre	125	1177	15.19	19
	gre	115	576	8.79	33	L125.lop163	125	1218	15.72	17
	bcspwr03	118	576	8.34	32	L125.dwt	125	943	12.17	16
	L125.will199	125	386	4.98	45	L125.can	125	1257	16.22	15
	L125.west0167	125	444	5.73	39	west0132	132	560	6.48	39
	L125.ash608	125	390	5.03	37	rw136	136	641	6.98	39
	L125.can	125	1022	13.19	20

[START_REF] Cornaz | The multi-terminal vertex separator problem: Polyhedral analysis and branch-and-cut[END_REF]

out of 31 instances and is the fastest method in 2 cases; 9 instances are solved by Branch and Price while Cplex + reduction fails; 1 instance is solved by Cplex + reduction while Branch

Table 2 :

 2 Formulation performance comparison on the DIMACS instances (k = 5 and k = 10)

			k = 15				k = 20
		Branch and Price	Cplex + reduction	Branch and Price	Cplex + reduction
		time	nodes	time	nodes	time	nodes	time	nodes
	2-Insertions 3	0.10	22	683.56	676931
	myciel5	35.87	82	304.86	71515	1.71	33	2434.94	1105526
	2-FullIns 3	1.03	25	191.99	29987	1.46	40	992.17	382558
	3-Insertions 3	0.51	14	tl	783072	0.44	17	tl	766107
	1-Insertions 4	36.48	49	tl	143540	12.33	50	tl	104232
	huck	0.14	4	14.76	6619	0.07	2	4.98	1745
	4-Insertions 3	4.29	29	tl	369502	3.13	38	tl	201377
	jean	0.63	8	0.64	0	0.33	7	5.20	2085
	3-FullIns 3	tl	79	tl	182041	460.07	249	tl	105272
	david	0.27	2	14.75	4111	1.73	18	tl	2581828
	mug88 1	1.14	21	tl	540602	0.85	13	tl	348214
	mug88 25	0.49	1	tl	459082	1.10	33	tl	218404
	1-FullIns 4	tl	14	tl	72206	tl	22	tl	25797
	myciel6	tl	3	tl	59139	tl	6	tl	25128
	mug100 1	1.73	14	tl	413118	1.51	12	tl	247039
	mug100 25	1.97	22	tl	376089	1.64	18	tl	217955
	4-FullIns 3	tl	14	tl	69442	tl	33	tl	16830
	games120	tl	1779	tl	139497	tl	1	tl	81290
	r125.1	0.96	1	275.62	35565	2.32	1	tl	526415
	DSJC125.1	tl	15	tl	18733	tl	22	tl	4915
	miles250	0.74	1	tl	614993	1.85	8	tl	397307
	miles500	tl	1769	tl	156294
	anna	57.52	7	0.78	17	84.68	7	2.06	30
	2-Insertions 4	tl	8	tl	24929	tl	8	tl	6093
	solved	16/24		8/24		16/22		5/22
	karate	0.02	4	0.06	0	0.01	3	0.08	100
	chesapeake	0.06	9	8.46	4903
	dolphins	0.16	8	316.13	195342	0.10	4	tl	1688935
	lesmis	0.58	6	1.23	804	0.41	4	7.44	2226
	polbooks	25.94	44	tl	279125	3.13	11	tl	267568
	adjnoun	tl	12	2337.24	157113	tl	28	tl	90669
	football	tl	1544	tl	117103	tl	9228	tl	57614
	solved	5/7		5/7		4/6		2/6

Table 3 :

 3 Formulation performance comparison on the DIMACS instances (k = 15 and k = 20)

			k = 15				k = 20
		Branch and Price	Cplex + reduction	Branch and Price	Cplex + reduction
		time	nodes	time	nodes	time	nodes	time	nodes
	bcspwr02	1.38	1	0.78	381
	impcol	23.85	181	22.49	29240	25.89	689	380.80	717423
	dwt	22.19	253	154.07	63767
	can62	22.09	7	tl	1118811
	dwt72	121.35	6069	tl	903196	466.80	50711	tl	685004
	ash219	114.16	779	tl	358161	258.45	1974	tl	174120
	dwt87	tl	4587	202.22	43774
	solved	6/7		4/7		3/3		1/3
	ash331	tl	2026	tl	237020	tl	5112	tl	143100
	gre	tl	261	tl	137169	tl	574	tl	69700
	bcspwr03	1853.68	2292	tl	260470	tl	3175	tl	187362
	L125.will199	44.21	41	tl	186330	31.37	23	tl	95182
	L125.west0167	37.49	5	tl	324965	30.43	2	tl	217315
	L125.ash608	tl	128	tl	173467	tl	507	tl	99585
	L125.can	tl	1495	tl	66494	tl	15705	tl	24735
	L125.gre	tl	492	tl	28888
	L125.lop163	tl	346	tl	25323
	L125.dwt	tl	11848	tl	55178
	L125.can	tl	2430	tl	45321
	west0132	41.57	12	tl	335734	110.40	269	tl	225030
	rw136	tl	102	tl	33405	tl	274	tl	14098
	solved	4/13		0/13		3/9		0/9
	L80.cavity01	tl	1	4.96	2107	tl	1	4.41	1189
	L80.wm1	85.64	1	0.40	39
	L100.cavity01	tl	1	5.50	2093	tl	1	5.74	641
	L100.wm1	tl	1	1.49	215
	L100.wm3	tl	12	4.21	1528
	L120.cavity01	tl	1	5.44	542	tl	1	8.04	1163
	L120.wm2	tl	1	0.71	0	tl	1	46.99	17695
	solved	1/7		7/7		0/4		4/4

Table 5 :

 5 Formulation performance comparison on the Intersection Graph Instances (k = 15 and k = 20) reduction can solve 5 out of 16 instances and is the fastest method in 4 cases; 5 instances are solved by Branch and Price while Cplex + reduction fails, 4 instances are solved by Cplex + reduction while Branch and Price fails. For the solved instances, the number of nodes explored by the Branch and Price can be as large as 50711, while Cplex + reduction can need one order of magnitude additional nodes for solved instances.

k = 5, the generic cuts embedded in the cplex MIP solver compensate the poor quality of the linear relaxation, while starting from k = 10 the increasing lp gap cannot be effectively reduced and Cplex + reduction struggles in solving the associated instances.

Computational performance on Intersection Graph instances. For the Intersection Graph instances from [START_REF] Souza | The vertex separator problem: algorithms and computations[END_REF] we concentrate on the values of k = 15, 20, where, according to the results of the previous section, the use of the Branch-and-Price algorithm showed to be more advisable. Results are summarized in Table 5 where we report, for Branch and Price and Cplex + reduction, the CPU time is seconds (tl for time limit) and the associated number of explored nodes. For each instance and for each value of k, we report in bold the fastest method. Missing lines correspond to infeasible instances.

• For k = 15 we considered 27 Intersection Graph instances in total. For 10 instances, no method can find the optimal solution within time limit; the Branch and Price can solve 11 out of 27 instances and is the fastest method in 9 cases; the Cplex + reduction can solve 11 out of 27 instances and is the fastest method in 10 cases; 7 instances are solved by Branch and Price while Cplex + reduction fails; 7 instances are solved by Cplex + reduction while Branch and Price fails. For the solved instances, the number of nodes explored by the Branch and Price is not larger than 6069. Cplex + reduction needs to explore on average several thousands of nodes.

• For k = 20, there are 16 feasible Intersection Graph instances. For 6 instances, no method can find the optimal solution within time limit; the Branch and Price can solve 6 out of 16 instances and is the fastest method in all the 6 cases; the Cplex + the formulation ILP E is characterized by a much stronger linear programming relaxation, although the gap appears to be increasing with the value of k. The strong linear programming relaxation explains the fact that Branch and Price explores on average a much smaller number of nodes, and justifies the computational effort spent in column generation. Again, the quality of the lp gap of ILP C deteriorates when k increases, but instances with a lp gap as large as 63.07% can still be solved to optimality, thanks to the capability of the cplex MIP solver to process a large number of nodes in short computing time.

Conclusions

In this paper we considered the minimum vertex k-cut problem, a variant of graph partitioning which consists in finding a vertex k-cut of minimum cardinality. We studied two alternative ILP formulations and analysed their properties in terms of linear programming relaxation. The first formulation is a natural compact formulation while the second one is an exponential-size formulation which requires Column Generation techniques to be effectively solved. We proposed a Branch-and-Price algorithm and we showed how to solve the Linear Programming relaxation of the exponential-size formulation in polynomial time via a series Appendix 6.0.1 Pricing as submodular function minimization

The PP∪∅ (i.e., the relaxation of the PP where also the empty set is admitted as solution) can also be tackled as the minimization of a submodular function and hence is polynomial-time solvable [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]. A list of submodular functions is reported in a list in [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF] (section 44.1a).