{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-04","reactions":{}}