On the hardness of approximating the k-way hypergraph cut problem

Research output: Contribution to journalComment/debatepeer-review


We consider the approximability of the k-WAY HYPERGRAPH CUT problem: the input is an edge-weighted hypergraph G = (V, E) and an integer k and the goal is to remove a min-weight subset of the edges such that the residual hypergraph has at least k connected components. When G is a graph this problem admits a 2(1 − 1/k)-approximation (Saran and Vazirani, SIAM J. Comput. 1995). However, there has been no non-trivial approximation ratio for general hypergraphs. In this note we show, via a very simple reduction, that an α-approximation for k-WAY HYPERGRAPH CUT implies an α2-approximation for the DENSEST ℓ-SUBGRAPH problem. Our reduction combined with the hardness result of (Manurangsi, STOC’17) implies that under the Exponential Time Hypothesis (ETH), there is no n1/(loglogn)c -approximation for k-WAY HYPERGRAPH CUT where c > 0 is a universal constant and n is the number of nodes. k-WAY HYPERGRAPH CUT is a special case of k-WAY SUBMODULAR PARTITION and hence our hardness applies to this latter problem as well. These hardness results are in contrast to a 2-approximation for closely related problems where the goal is to separate k given terminals (Chekuri and Ene, FOCS’11), (Ene et al., SODA’13).

Original languageEnglish (US)
Article number14
JournalTheory of Computing
StatePublished - 2020


  • Hardness of approximation
  • K-way Hypergraph Cut

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'On the hardness of approximating the k-way hypergraph cut problem'. Together they form a unique fingerprint.

Cite this