Hypergraph k-cut in randomized polynomial time

Karthekeyan Chandrasekaran, Chao Xu, Xilin Yu

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)85-113
Number of pages29
JournalMathematical Programming
Volume186
Issue number1-2
DOIs
StatePublished - Mar 2021

Keywords

  • Hedgegraph-k-cut
  • Hypergraph-k-cut
  • Randomized algorithm

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Hypergraph k-cut in randomized polynomial time'. Together they form a unique fingerprint.

Cite this