The vertex k-cut problem

Abstract Given an undirected graph G = ( V , E ) , a vertex k -cut of G is a vertex subset of V the removing of which disconnects the graph in at least k components. Given a graph G and an integer k ≥ 2 , the vertex k -cut problem consists in finding a vertex k -cut of G of minimum cardinality. We first prove that the problem is NP-hard for any fixed k ≥ 3 . We then present a compact formulation, and an extended formulation from which we derive a column generation and a branching scheme. Extensive computational results prove the effectiveness of the proposed methods.