Optimization Online


The Vertex k-cut Problem

Denis Cornaz(denis.cornaz***at***dauphine.fr)
Fabio Furini(fabio.furini***at***dauphine.fr)
Mathieu Lacroix(mathieu.lacroix***at***lipn.univ-paris13.fr)
Enrico Malaguti(enrico.malaguti***at***unibo.it)
A. Ridha Mahjoub(mahjoub***at***lamsade.dauphine.fr)
Sébastien Martin(sebastien.martin***at***univ-lorraine.fr)

Abstract: Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex k-cut problem consists in finding a vertex k-cut of G of minimum cardinality. We first prove that the problem is NP-hard for any fixed k greater than or equal to three. We then present a compact formulation, and an extended formulation from which we derive a column generation and a branching scheme. Extensive computational results prove the effectiveness of the proposed methods.

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

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Integer Programming


Download: [PDF]

Entry Submitted: 09/21/2017
Entry Accepted: 09/22/2017
Entry Last Modified: 09/21/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society