Skip to Main content Skip to Navigation
Journal articles

The vertex k-cut problem

Abstract : Given an undirected graph G=(V, E), a vertex k-cut of G is a vertex subset of the removing of which disconnects the graph in at least components. Given a graph and an integer k≥2, the vertex k-cut problem consists in finding a vertex k-cut of of G 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Accord Elsevier Ccsd Connect in order to contact the contributor
Submitted on : Friday, October 22, 2021 - 11:08:24 AM
Last modification on : Wednesday, November 17, 2021 - 12:27:16 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License



Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, A. Ridha Mahjoub, et al.. The vertex k-cut problem. Discrete Optimization, Elsevier, 2019, 31, pp.8-28. ⟨10.1016/j.disopt.2018.07.003⟩. ⟨hal-02152319⟩



Les métriques sont temporairement indisponibles