On the Polytope of the Vertex Separator Problem

I Diarrassouba (1) , M Didi Biha (2) , C Joncour (1) , S Michel (1)

1 LMAH - Laboratoire de Mathématiques Appliquées du Havre
2 LMNO - Laboratoire de Mathématiques Nicolas Oresme

Given G = (V, E) a connected undirected graph and a positive integer β(|V |), the vertex separator problem is to find a partition of V into three nonempty subsets A, B, C such that (i) there is no edge between the nodes of A and those of B, (ii) max{|A|, |B|} ≤ β(|V |) and (iii) |C| is minimum. In this paper, we consider the problem from a polyhedral point of view. We first propose a new integer programming formulation for the problem. Then we provide several valid inequalities for the polytope which generalize those introduced by Balas and De Souza [1], and give conditions under which these inequalities define facets.

Mots clés: graph partitioning vertex separator polyhedral approach; graph partitioning; vertex separator; polyhedral approach

Domaines: Recherche opérationnelle [math.OC]; Mathématiques [math]

I Diarrassouba, M Didi Biha, C Joncour, S Michel. On the Polytope of the Vertex Separator Problem. 2022. ⟨hal-03885692⟩