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

PAPER GUIDE · MATHEMATICAL PROGRAMMING COMPUTATION · 2020

Two ways to cut a network into k components

Representative formulations, a Stackelberg interdiction model, and a hybrid branch-and-cut for the weighted k-vertex cut problem.

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

Representativeformulationvalid inequalitiesBilevelformulationvalid inequalitiesHybridbranch-and-cut
Conceptual illustration of the paper's methodology; drawn for this page, not reproduced from the published article.
THE CENTRAL IDEA

Two different models reveal different aspects of the same connectivity problem. Their valid inequalities become more effective when combined in a hybrid branch-and-cut.

01 / THE PROBLEM

How much must we delete to split a network?

For an undirected graph with positive vertex weights and an integer k ≥ 2, find a minimum-weight set of vertices whose removal produces at least k connected components. The problem is related to identifying critical nodes in networks and to decomposing sparse systems for parallel computation.

02 / TWO VIEWS OF CONNECTIVITY

Representatives versus interdiction

01Representative model

Choose representatives of k mutually disconnected vertex subsets in the surviving network.

02Leader–follower model

A leader deletes vertices; a follower constructs connected components in the remaining graph.

03Hybrid model

Join strengthening inequalities from the two formulations in a single exact approach.

03 / ORIGINAL CONTRIBUTIONS

Why the combination matters

Two new MILP formulations

One relies on representatives; the other arises from a two-phase Stackelberg interpretation.

Exact separation

Both models feature exponentially many constraints with polynomial-time separation procedures.

Dedicated branch-and-cut

The formulations are turned into exact algorithms rather than left as modelling alternatives.

Hybrid strengthening

The paper brings together complementary valid inequalities, improving computational performance.

04 / COMPUTATIONAL EVIDENCE

The hybrid is more than the sum of its parts

The paper's computational study reports that the hybrid formulation significantly outperforms the exact approaches from the literature on the benchmark set considered. The detailed performance by graph family and number of components is available in Section 6 of the manuscript.

This account follows the original paper's theoretical and computational sections. No unverified timing or solved-instance counts have been introduced.

05 / GO DEEPER

Explore the inequalities and separation proofs.

The most important technical part is how the representative and bilevel approaches yield distinct strengthening inequalities that can be combined.

Read the paper ↗Implementation ↗

Selected citing literature reviewed on 9 October 2026; examples are not ranked by citation counts.

06 / SUBSEQUENT RESEARCH

How this work has been used or discussed

Selected citing research, with an explanation of the documented relationship to this paper.

A selective set of verified examples, not a complete Google Scholar citing-articles list. Where the later work only discusses the original paper, this is explicitly distinguished from adopting its method.

Related problem / bibliographic citation

The k-way vertex cut problem on bipartite graphs: Complexity results and algorithms (2025) ↗

Published in Discrete Optimization (2025). This paper investigates a related k-way vertex-cut variant on bipartite graphs, proves NP-completeness for bipartite graphs, and develops polynomial-time dynamic programming for bipartite-permutation graphs. It is a related research direction, not a reuse of the original hybrid branch-and-cut.

NeurIPS, Datasets and Benchmarks (2023)

Lo-Hi: Practical ML Drug Discovery Benchmark ↗

Introduces a molecular dataset splitting method based on a balanced minimum vertex k-cut model, using integer programming and heuristic graph coarsening. Cites the k-vertex-cut algorithmic literature; a downstream application in machine-learning benchmark design, not direct adoption of the original cuts.

European Journal of Operational Research (2023)

Mathematical Programming Formulations for the Collapsed k-Core Problem ↗

Cites the 2020 k-vertex cut paper in its network-interdiction literature. Develops two bilevel and one time-indexed model for a different graph fragmentation metric; a related modelling extension, not a direct adaptation of its hybrid algorithm.