TY - JOUR

T1 - Hypergraph k-cut in randomized polynomial time

AU - Chandrasekaran, Karthekeyan

AU - Xu, Chao

AU - Yu, Xilin

N1 - Publisher Copyright:
© 2019, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2021/3

Y1 - 2021/3

N2 - For a fixed integer k≥ 2 , the hypergraph k-cut problem asks for a smallest subset of hyperedges whose removal leads to at least k connected components in the remaining hypergraph. While graph k-cut is solvable efficiently (Goldschmidt and Hochbaum in Math. Oper. Res. 19(1):24–37, 1994), the complexity of hypergraph k-cut has been open. In this work, we present a randomized polynomial time algorithm to solve the hypergraph k-cut problem. Our algorithmic technique extends to solve the more general hedge k-cut problem when the subgraph induced by every hedge has a constant number of connected components. Our algorithm is based on random contractions akin to Karger’s min cut algorithm. Our main technical contribution is a non-uniform distribution over the hedges (hyperedges) so that random contraction of hedges (hyperedges) chosen from the distribution succeeds in returning an optimum solution with large probability. In addition, we present an alternative contraction based randomized polynomial time approximation scheme for hedge k-cut in arbitrary hedgegraphs (i.e., hedgegraphs whose hedges could have a large number of connected components). Our algorithm and analysis also lead to bounds on the number of optimal solutions to the respective problems.

AB - For a fixed integer k≥ 2 , the hypergraph k-cut problem asks for a smallest subset of hyperedges whose removal leads to at least k connected components in the remaining hypergraph. While graph k-cut is solvable efficiently (Goldschmidt and Hochbaum in Math. Oper. Res. 19(1):24–37, 1994), the complexity of hypergraph k-cut has been open. In this work, we present a randomized polynomial time algorithm to solve the hypergraph k-cut problem. Our algorithmic technique extends to solve the more general hedge k-cut problem when the subgraph induced by every hedge has a constant number of connected components. Our algorithm is based on random contractions akin to Karger’s min cut algorithm. Our main technical contribution is a non-uniform distribution over the hedges (hyperedges) so that random contraction of hedges (hyperedges) chosen from the distribution succeeds in returning an optimum solution with large probability. In addition, we present an alternative contraction based randomized polynomial time approximation scheme for hedge k-cut in arbitrary hedgegraphs (i.e., hedgegraphs whose hedges could have a large number of connected components). Our algorithm and analysis also lead to bounds on the number of optimal solutions to the respective problems.

KW - Hedgegraph-k-cut

KW - Hypergraph-k-cut

KW - Randomized algorithm

UR - http://www.scopus.com/inward/record.url?scp=85075213574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075213574&partnerID=8YFLogxK

U2 - 10.1007/s10107-019-01443-7

DO - 10.1007/s10107-019-01443-7

M3 - Article

AN - SCOPUS:85075213574

SN - 0025-5610

VL - 186

SP - 85

EP - 113

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -