Minimum vertex removal in graph partitioning under cardinality constraints

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

Graph partitioning is an area of graph theory concerned with dividing vertices into disjoint subgraphs. In this work, we consider an undirected graph for which the partitioning is subject to two cardinality constraints, defined by the parameters, q and b. The objective is to identify a minimum-size vertex subset whose removal partitions the remaining graph into no more than q subgraphs, each of which contains no more than b vertices. This combinatorial optimization problem is closely related to vertex separation problems, network interdiction, critical node problems and matrix decomposition. After reviewing the literature across these fields, we introduce two versatile families of compact mixed-integer linear programming models. We explore these model families, examining dominance relations, addressing symmetry challenges, and presenting techniques to strengthen their linear programming relaxations. Finally, we analyze computational results obtained from standard benchmark instances.

Keywords: Graph partitioning, Compact formulations, Cardinality constraints

GT GELOCA II: Optimization Models for Network Analysis and Classification
September 4, 2026  9:00 AM
Aula B

I. Espejo Miranda, J. Peiró, M. Landete

V. Blanco, R. Gázquez, J. F. Ocaña-Rivas

V. Blanco, M. Martínez Antón, J. Puerto

F. Temprano Garcia, J. Puerto, S. Benati