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

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

Licensed under a Creative Commons Attribution License (CC-BY)