Instead of explicitly assigning every surviving vertex to a partition, let an adversarial second player expose the connectivity violations. The resulting structure produces inequalities directly in the vertex-deletion variables.
01 / THE PROBLEM
How few vertices must we remove?
Given an undirected graph, remove a minimum-cardinality vertex set so that the remaining vertices can be divided into at most k disconnected shores, each containing at most b vertices. The components must not only be small: they must also fit into the available shores.
Conceptual illustration of vertex interdiction and disconnected shores; not an original paper figure.
02 / THE INSIGHT
A graph problem hides a Stackelberg game
Chooses the vertices to delete.
Examines the remaining network for forbidden connected structures.
Uses the follower’s response to add inequalities and refine the decision.
The bilevel interpretation is not merely a different story for the same model. It becomes a systematic way to derive strong valid inequalities in the natural variable space, while retaining an exact method.
03 / CONTRIBUTIONS
What changes mathematically?
An interdiction-based interpretation of the capacitated vertex separator problem.
New inequalities exploiting the graph structure, with polynomial-time separation results.
A cutting-plane framework that avoids carrying explicit shore-assignment decisions throughout the model.
An extension to a min–max problem involving the largest surviving component.
The full manuscript develops the precise inequalities, theoretical relationships, and separation algorithms.
04 / COMPUTATIONAL RESULTS
What do the experiments tell us?
On the reported 1,397 benchmark instances, the combination of component and cover inequalities (C+CV) is the best of the tested variants in that family, closing 940 instances within the 30-minute time limit.
Comparison against existing exact methods
| Instance group | CPLEX | Branch-and-price | C+CV |
|---|---|---|---|
| DIMACS | 124 | 164 | 182 |
| MIPLIB | 73 | 109 | 138 |
| Netlib | 237 | 351 | 354 |
| Random | 168 | 322 | 266 |
| All 1,397 | 602 | 946 | 940 |
Numbers of instances solved to proven optimality, from the paper’s computational study. Results depend on the benchmark, computing platform and time limit.
The key finding is complementarity rather than universal dominance: the new method performs especially well on DIMACS and MIPLIB, while branch-and-price remains much stronger on the Random group.
Beyond the original CVSP
For the related min–max extension, the specialized branch-and-cut solves 290 of 564 benchmark instances, compared with 161 and 164 for two alternative formulations.
05 / WHY READ THE PAPER?
The lesson goes beyond graph separation.
If you work on mixed-integer programming, interdiction or graph modification, the most interesting part is the route from an unexpected leader–follower interpretation to exact inequalities that are both theoretically meaningful and computationally useful.
Explore the full paper ↗See the code ↗06 / SUBSEQUENT RESEARCH
Impact in peer-reviewed research
Only direct follow-up papers published in leading journals or recognized scientific conferences will be listed here. No qualifying citing study has yet been verified for this selection.
LAGOS 2025 · Procedia Computer Science (2025)
Generalized Capacitated Vertex Separator Problem: Models and Algorithms ↗
Direct generalization of the CVSP from unit vertex-removal costs and cardinalities to heterogeneous costs and vertex weights; develops and tests new mathematical formulations.
European Journal of Operational Research (2023)
Mathematical programming formulations for the Collapsed k-Core Problem ↗
Cites the graph-interdiction formulation literature and develops two new bilevel models for a different graph-deletion problem. This is a related methodological direction, not a reuse of the specific CVSP cuts.
Journal of Computer and System Sciences (2022)
Complexity of the Multilevel Critical Node Problem ↗
References the related bilevel graph-separation manuscript when studying structural complexity of multilevel critical-node interdiction. The use is background for graph interdiction, not an implementation of CVSP inequalities.