Revised: August 29, 2020
Published: December 7, 2020
Abstract: [Plain Text Version]
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).