The vertex k-cut problem

被引：12

作者：

Cornaz, Denis ^{[1
]}

Furini, Fabio ^{[1
]}

Lacroix, Mathieu ^{[2
]}

Malaguti, Enrico ^{[3
]}

Mahjoub, A. Ridha ^{[1
]}

Martin, Sebastien ^{[4
]}

机构：

[1] Univ Paris 09, PSL, CNRS, LAMSADE UMR 7243, F-75775 Paris 16, France

[2] Univ Paris 13, Sorbonne Paris Cite, LIPN, CNRS,UMR 7030, Ave JB Clement, F-93430 Villetaneuse, France

[3] Univ Bologna, DEI, Viale Risorgimento 2, I-40136 Bologna, Italy

[4] Univ Lorraine, LCOMS, F-57045 Metz, France

来源：

DISCRETE OPTIMIZATION | 2019年 / 31卷

关键词：

Vertex cut; Mixed-integer programming models; Branch and Price; Exact algorithms; SEPARATOR PROBLEM; ALGORITHM; COMPLEXITY;

D O I：

10.1016/j.disopt.2018.07.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：8 / 28

页数：21

共 50 条

[1] Optimal Bounds for the k-cut Problem
Gupta, Anupam
Harris, David G.
Lee, Euiwoong
Li, Jason
JOURNAL OF THE ACM, 2022, 69 (01)
[2] On integer and bilevel formulations for the k-vertex cut problem
Furini, Fabio
Ljubic, Ivana
Malaguti, Enrico
Paronuzzi, Paolo
MATHEMATICAL PROGRAMMING COMPUTATION, 2020, 12 (02) : 133 - 164
[3] An Optimal Algorithm for Tree Geometrical k-cut Problem
Cho, Sang-Young
Kim, Hee-Chul
MACMESE 2008: PROCEEDINGS OF THE 10TH WSEAS INTERNATIONAL CONFERENCE ON MATHEMATICAL AND COMPUTATIONAL METHODS IN SCIENCE AND ENGINEERING, PTS I AND II, 2008, : 280 - +
[4] Geometrical k-cut problem and an optimal solution for hypercubes
Cho, Sang-Young
APPLIED MATHEMATICS FOR SCIENCE AND ENGINEERING, 2007, : 217 - +
[5] Hypergraph k-Cut in Randomized Polynomial Time
Chandrasekaran, Karthekeyan
Xu, Chao
Yu, Xilin
SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 1426 - 1438
[6] A Parameterized Approximation Scheme for Min k-Cut
Lokshtanov, Daniel
Saurabh, Saket
Surianarayanan, Vaishali
2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020), 2020, : 798 - 809
[7] Hypergraph k-cut in randomized polynomial time
Chandrasekaran, Karthekeyan
Xu, Chao
Yu, Xilin
MATHEMATICAL PROGRAMMING, 2021, 186 (1-2) : 85 - 113
[8] Faster Minimum k-cut of a Simple Graph
Li, Jason
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, : 1056 - 1077
[9] Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
Chandrasekaran, Karthekeyan
Chekuri, Chandra
MATHEMATICS OF OPERATIONS RESEARCH, 2022, 47 (04) : 3380 - 3399
[10] On integer and bilevel formulations for the k-vertex cut problem
Fabio Furini
Ivana Ljubić
Enrico Malaguti
Paolo Paronuzzi
Mathematical Programming Computation, 2020, 12 : 133 - 164

← 1 2 3 4 5 →