摘要：Abstract. We consider the approximability of the k - WAY H YPERGRAPH C UT problem: theinput is an edge-weighted hypergraph G = (V,E) and an integer k and the goal is to removea min-weight subset of the edges such that the residual hypergraph has at least k connectedcomponents. When G is a graph this problem admits a 2(1−1/k) -approximation (Saran andVazirani, SIAM J. Comput. 1995). However, there has been no non-trivial approximationratio for general hypergraphs. In this note we show, via a very simple reduction, thatan α -approximation for k - WAY H YPERGRAPH C UT implies an α 2 -approximation for theD ENSEST ‘ -S UBGRAPH problem. Our reduction combined with the hardness result of(Manurangsi, STOC’17) implies that under the Exponential Time Hypothesis (ETH), thereis no n 1/(loglogn)c -approximation fork - WAY H YPERGRAPH C UT where c > 0 is a universalconstant and n is the number of nodes.k - WAY H YPERGRAPH C UT is a special case of k - WAY S UBMODULAR P ARTITION andhence our hardness applies to this latter problem as well. These hardness results are incontrast to a 2 -approximation for closely related problems where the goal is to separate kgiven terminals (Chekuri and Ene, FOCS’11), (Ene et al., SODA’13).
关键词：hardness of approximation; $k$-way Hypergraph Cut
