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 : http://www.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).