Id: arxiv/2602.04984 Url: https://arxiv.org/abs/2602.04984 Tags: math.OC Score: 0 Title: Branch-and-price strikes back for the k-vertex cut problem Domain: math.OC Source: arxiv Authors: Fabio Ciccarelli, Fabio Furini, Christopher Hojny, Marco Lübbecke Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-04 Page: https://delphi.science/r/arxiv/2602.04984 Given an undirected graph, the k-vertex cut problem (k-VCP) asks for a minimum-cost set of vertices whose removal yields at least k connected components in the resulting graph. The k-VCP is an important problem in network optimization, with applications in infrastructure protection and epidemic containment. We present a new extended integer linear programming (ILP) formulation that unifies and strengthens existing models and serves as the foundation for a new branch-and-price algorithm for the k-VCP. An in-depth theoretical study enables us to devise algorithmic components such as tailored…