TY - JOUR
T1 - On the hardness of approximating the k-way hypergraph cut problem
AU - Chekuri, Chandra
AU - Li, Shi
N1 - Publisher Copyright:
© 2020 Chandra Chekuri and Shi Li.
PY - 2020
Y1 - 2020
N2 - We consider the approximability of the k-WAY HYPERGRAPH CUT problem: the input is an edge-weighted hypergraph G = (V, 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 α-approximation for k-WAY HYPERGRAPH CUT implies an α2-approximation for the DENSEST ℓ-SUBGRAPH problem. Our reduction combined with the hardness result of (Manurangsi, STOC’17) implies that under the Exponential Time Hypothesis (ETH), there is no n1/(loglogn)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).
AB - We consider the approximability of the k-WAY HYPERGRAPH CUT problem: the input is an edge-weighted hypergraph G = (V, 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 α-approximation for k-WAY HYPERGRAPH CUT implies an α2-approximation for the DENSEST ℓ-SUBGRAPH problem. Our reduction combined with the hardness result of (Manurangsi, STOC’17) implies that under the Exponential Time Hypothesis (ETH), there is no n1/(loglogn)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).
KW - Hardness of approximation
KW - K-way Hypergraph Cut
UR - http://www.scopus.com/inward/record.url?scp=85103517727&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103517727&partnerID=8YFLogxK
U2 - 10.4086/TOC.2020.V016A014
DO - 10.4086/TOC.2020.V016A014
M3 - Comment/debate
AN - SCOPUS:85103517727
SN - 1557-2862
VL - 16
JO - Theory of Computing
JF - Theory of Computing
M1 - 14
ER -