The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019), The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut, Discrete Applied Mathematics, 256, 1, p. 11-37. 10.1016/j.dam.2018.10.005
Type
Article accepté pour publication ou publiéDate
2019Journal name
Discrete Applied MathematicsVolume
256Number
1Publisher
Elsevier
Pages
11-37
Publication identifier
Metadata
Show full item recordAuthor(s)
Cornaz, DenisLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Magnouche, Youcef
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Martin, Sébastien

Laboratoire de Conception, Optimisation et Modélisation des Systèmes [LCOMS]
Abstract (EN)
In this paper we consider a variant of the k-separator problem. Given a graph G=(V∪T,E) with V∪T the set of vertices, where T is a set of k terminals, the multi-terminal vertex separator problem consists in partitioning V∪T into k+1 subsets {S,V1,...,Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study.Subjects / Keywords
Vertex separator problem; Integer programming; Polytope; Facet; Branch-and-Cut algorithm; Complexity; Separation algorithmRelated items
Showing items related by title and author.
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2015) Communication / Conférence
-
Lacroix, Mathieu; Mahjoub, Ali Ridha; Martin, Sébastien (2012) Communication / Conférence
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié