文章基本信息

标题：On the Hardness of Approximating the $k$-Way Hypergraph Cut problem
本地全文：下载
作者：Chandra Chekuri ; Shi Li
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2020
卷号：16
期号：1
页码：1-8
DOI：10.4086/toc.2020.v016a014
语种：English
出版社：University of Chicago
摘要：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