Skip to content CVSP — Paper guide | Fabio Furini Skip to content

PAPER GUIDE · OPERATIONS RESEARCH · 2022

When deleting vertices becomes a two-player game

The hidden bilevel structure of the Capacitated Vertex Separator Problem—and how it leads to stronger exact optimization methods.

Fabio Furini · Ivana Ljubić · Enrico Malaguti · Paolo Paronuzzi

Original graphDisconnected shoresinterdict
Conceptual illustration of the paper's methodology; drawn for this page, not reproduced from the published article.
THE CENTRAL IDEA

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.

Original graph Shore 1Shore 2Shore 3

Conceptual illustration of vertex interdiction and disconnected shores; not an original paper figure.

02 / THE INSIGHT

A graph problem hides a Stackelberg game

01The leader

Chooses the vertices to delete.

02The follower

Examines the remaining network for forbidden connected structures.

03The algorithm

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?

A bilevel formulation

An interdiction-based interpretation of the capacitated vertex separator problem.

Cut generation

New inequalities exploiting the graph structure, with polynomial-time separation results.

A natural-space exact algorithm

A cutting-plane framework that avoids carrying explicit shore-assignment decisions throughout the model.

A broader formulation

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.

940 / 1,397Instances solved by C+CV
+15Versus component cuts alone

Comparison against existing exact methods

Instance groupCPLEXBranch-and-priceC+CV
DIMACS124164182
MIPLIB73109138
Netlib237351354
Random168322266
All 1,397602946940

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.