Skip to Main content Skip to Navigation
Conference papers

Mathematical Formulations for the Balanced Vertex k-Separator Problem

Abstract : Given an indirected graph G = (V, E), a Vertex k-Separator is a subset of the vertex set V such that, when the separator is removed from the graph, the remaining vertices can be partitioned into k subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced Vertex k-Separator Problem, i.e., the problem of finding a minimum cardinality separator such that the sizes of the resulting disconnected subsets are balanced. We present a compact Integer Linear Programming formulation for the problem, and present a polyhedral study of the associated polytope. We also present an Exponential-Size formulation, for which we derive a column generation and a branching scheme. Preliminary computational results are reported comparing the performance of the two formulations on a set of benchmark instances.
Mots-clés : graph theory
Document type :
Conference papers
Complete list of metadata
Contributor : Catherine Angevelle <>
Submitted on : Thursday, February 4, 2016 - 4:10:09 PM
Last modification on : Wednesday, December 9, 2020 - 10:26:07 AM


  • HAL Id : hal-01267625, version 1


Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, A. Ridha Mahjoub, et al.. Mathematical Formulations for the Balanced Vertex k-Separator Problem. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.176-181. ⟨hal-01267625⟩



Record views