Theory of Computing ------------------- Title : On the Hardness of Approximating the $k$-Way Hypergraph Cut problem Authors : Chandra Chekuri and Shi Li Volume : 16 Number : 14 Pages : 1-8 URL : https://theoryofcomputing.org/articles/v016a014 Abstract -------- We consider the approximability of the $k$-way Hypergraph Cut 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. Comp. 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 $k$-way Hypergraph Cut implies an $\alpha^2$-approximation for the Densest $\ell$-Subgraph 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 $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).