The Capacitated Vertex Separator Problem

S. Anglada, M. C. Galé Pola, J. J. Salazar González

Graph disconnection problems are well-known optimization problems in Graph Theory and many variants exist. One way to achieve graph disconnection is by removing vertices, where the removal of a vertex entails eliminating the vertex itself and all edges incident to it. One such problem is the Capacitated Vertex Separator Problem (CVSP). Given an undirected graph and two natural numbers, q and b, the CVSP looks for a mínimum-cardinality vertex subset, called separator, such that the subgraph induced by removing this subset results in at most q disjoint groups, referred to as shores. Each shore contains no more than b vertices and no edges exist between vertices belonging to different shores. We propose different mathematical formulations and analyse computational results comparing formulation's performance on graphs of varying sizes and for arbitrary values of q and b.

Keywords: Graph disconnection, vertex removal, Capacitated Vertex Separator Problem

Location(GELOCA1)
June 11, 2025  3:30 PM
Mr 2

V. Blanco Izquierdo, I. Espejo Miranda, R. Páez Jiménez, A. M. Rodriguez Chía

P. Segura Martínez, A. Marín

F. Temprano Garcia, L. Mallozzi, J. Puerto

V. Blanco