Volume 16 (2020) Article 14 pp. 1-8 [Note]

On the Hardness of Approximating the $k$-Way Hypergraph Cut problem

by Chandra Chekuri and Shi Li

Received: July 25, 2019
Revised: August 29, 2020
Published: December 7, 2020

$ \def\kHMC{\textsf{$k$-way Hypergraph Cut}} \def\DKS{\textsf{Densest $\ell$-Subgraph}} \def\kSMP{\textsf{$k$-way Submodular Partition}} $

We consider the approximability of the $\kHMC$ problem: the input is an edge-weighted hypergraph $G=(V,\mathcal{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 $\alpha$-approximation for $\kHMC$ implies an $\alpha^2$-approximation for the $\DKS$ problem. Our reduction combined with the hardness result of (Manurangsi STOC'17) implies that under the Exponential Time Hypothesis (ETH), there is no $n^{1/(\log \log n)^c}$-approximation for $\kHMC$ where $c > 0$ is a universal constant and $n$ is the number of nodes.

$\kHMC$ is a special case of $\kSMP$ 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).

DOI: 10.4086/toc.2020.v016a014

© 2020 Chandra Chekuri and Shi Li
Licensed under a Creative Commons Attribution License (CC-BY)