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
Choose representatives of k mutually disconnected vertex subsets in the surviving network.
A leader deletes vertices; a follower constructs connected components in the remaining graph.
Join strengthening inequalities from the two formulations in a single exact approach.
03 / ORIGINAL CONTRIBUTIONS
Why the combination matters
One relies on representatives; the other arises from a two-phase Stackelberg interpretation.
Both models feature exponentially many constraints with polynomial-time separation procedures.
The formulations are turned into exact algorithms rather than left as modelling alternatives.
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.