Mathematical formulations for the Balanced Vertex k-Separator Problem

Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien

Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014), Mathematical formulations for the Balanced Vertex k-Separator Problem, 2014 International Conference on Control, Decision and Information Technologies (CoDIT), IEEE : Piscataway, NJ, p. 176-181. 10.1109/CoDIT.2014.6996889

Type

Communication / Conférence

Date

2014

Book title

2014 International Conference on Control, Decision and Information Technologies (CoDIT)

Publisher

IEEE

Published in

Piscataway, NJ

ISBN

978-1-4799-6773-5

Pages

176-181

Abstract (EN)

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.

Subjects / Keywords

graph theory