Branch-and-price strikes back for the k k -vertex cut problem

Fabio Ciccarelli, Fabio Furini, Christopher Hojny, Marco Lübbecke · 2026

Read Branch-and-price strikes back for the k k -vertex cut problem by Fabio Ciccarelli, Fabio Furini, Christopher Hojny, Marco Lübbecke (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-04984.txt.

Description

Fabio Ciccarelli and 3 co-authors wrote this 2026 optimization paper on the k-vertex cut problem. Given a network, the task is to remove the cheapest set of vertices so that what remains splits into at least k separate pieces. The problem matters for protecting infrastructure and for containing epidemics, since cutting the right vertices can fragment a network on purpose.

The authors present a new integer programming formulation that unifies and strengthens earlier models. They prove its relaxations dominate all previous ones, then build a branch-and-price algorithm around it, with custom branching rules, extra inequalities, and symmetry handling. In extensive tests against leading methods, the new approach solved more instances to proven optimality and ran faster. The title's claim is that a classic technique, properly rebuilt, strikes back.

Catalog record

CREATORFabio Ciccarelli, Fabio Furini, Christopher Hojny, Marco Lübbecke
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-04984

Browse the full library · About the Tower of Babel