Authors Chandra Chekuri, Shi Li,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8
www.theoryofcomputing.org
NOTE
On the Hardness of Approximating the
k-WAY H YPERGRAPH C UT Problem
Chandra Chekuri∗ Shi Li†
Received July 25, 2019; Revised August 29, 2020; Published December 7, 2020
Abstract. We consider the approximability of the k- WAY H YPERGRAPH C UT 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 H YPERGRAPH C UT implies an α 2 -approximation for the
D ENSEST `-S UBGRAPH problem. Our reduction combined with the hardness result of
(Manurangsi, STOC’17) implies that under the Exponential Time Hypothesis (ETH), there
c
is no n1/(log log n) -approximation for k- WAY H YPERGRAPH C UT where c > 0 is a universal
constant and n is the number of nodes.
k- WAY H YPERGRAPH C UT is a special case of k- WAY S UBMODULAR 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).
ACM Classification: F.2.2, G.2.0
AMS Classification: 68Q17
Key words and phrases: hardness of approximation, k-way Hypergraph Cut
∗ Supported in part by NSF grants CCF-1526799 and CCF-1907937.
† Supported in part by NSF grants CCF-1566356, CCF-1717134 and CCF-1844890.
© 2020 Chandra Chekuri and Shi Li
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2020.v016a014
C HANDRA C HEKURI AND S HI L I
1 Introduction
We consider the following problem.
k- WAY H YPERGRAPH C UT: Let G = (V, E) be a hypergraph with edge weights given by w : E → R+ .
Given an integer k, find a min-weight subset of edges E0 ⊆ E such that G − E0 has at least k connected
components. Equivalently, find a partition of V into k non-empty sets V1 ,V2 , . . . ,Vk such that the weight
of the hyperedges that cross the partition1 is minimized.
k- WAY H YPERGRAPH C UT is known as the k-C UT problem when the input is a graph and is one of
the well-studied graph partitioning problems. k- WAY H YPERGRAPH C UT is a special case of a more
general submodular partitioning problem defined below.2
k-WAY S UBMODULAR PARTITION (k- WAY S UB -MP): Let f : 2V → R+ be a non-negative submodular
set function3 over a finite ground set V . The k-way submodular partition problem is to find a partition
V1 , . . . ,Vk of V to minimize ∑ki=1 f (Vi ) under the condition that each part Vi 6= 0.
/ An important special
case is when f is symmetric and we refer to it as k- WAY S YM -S UB -MP.
Throughout the paper we will assume that the parameter k is part of the input and can be a function of
the other input parameters such as the size of the hypergraph. Several of the problems are also interesting
when k is fixed to some absolute constant. In this case we will explicitly use the terminology “fixed
k” to distinguish it from the general case. The result in this paper is on the hardness of approximating
k- WAY H YPERGRAPH C UT when k is part of the input; we note that if k is a fixed constant there is
a polynomial-time algorithm for k- WAY H YPERGRAPH C UT due to recent work [4, 3]. We seek to
establish a hardness factor for k- WAY H YPERGRAPH C UT that is polynomial in the number of nodes
of the underlying hypergraph; this is only feasible for instances in which k is also polynomial in the
hypergraph size. This will be implicit in the reduction.
We refer the reader to [14, 5] to see why k- WAY H YPERGRAPH C UT is a special case of k- WAY
S UB -MP. The k-C UT problem is not only a special case of k- WAY H YPERGRAPH C UT but it is also a
special case of k- WAY S YM -S UB -MP. When k is part of the input, k-C UT is NP-Hard [8] and hence
all the problems we discussed so far are also NP-Hard. k- WAY S YM -S UB -MP admits a 2(1 − 1/k)-
approximation [15, 19] and hence also k-C UT [17]. For k- WAY H YPERGRAPH C UT a 2∆(1 − 1/k)-
approximation easily follows from the 2(1 − 1/k)-approximation for k-C UT; here ∆ is the rank of the
hypergraph (the maximum size of any hyperedge). On the other hand, in the general case, the known
approximation algorithms for k- WAY H YPERGRAPH C UT and k- WAY S UB -MP provide an approximation
ratio of (k − 1) [19]. Despite a claim of APX-Hardness for k-C UT in [17] (attributed to Papadimitriou),
no proof has been published in the literature; Manurangsi [13] showed that k-C UT does not admit a
(2 − ε)-factor approximation for any fixed ε > 0 under the Small Set Expansion Hypothesis. As far as
we are aware, prior to our work, no better hardness result was known for k- WAY H YPERGRAPH C UT.
1 A hyperedge e crosses a partition of the vertex set if e properly intersects at least two parts of the partition.
2 The names of several problems in this paper such as k- WAY H YPERGRAPH C UT and k-C UT include k as a prefix while k
also is an input parameter. Although there is some scope for confusion due to this notational overload, we stick to it for historical
reasons and believe that it is not hard to disambiguate based on the context.
3 A set function f : 2V → R is submodular if f (A) + f (B) ≥ f (A ∩ B) + f (A ∪ B) for all A, B ⊆ V . Moreover, f is symmetric
if f (A) = f (V − A) for all A ⊆ V .
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 2
O N THE H ARDNESS OF A PPROXIMATING THE k- WAY H YPERGRAPH C UT P ROBLEM
In this note we show that a good approximation for k- WAY H YPERGRAPH C UT would imply a good
approximation for the D ENSEST `-S UBGRAPH problem4 which has been extensively investigated and has
been shown to be conditionally hard.
D ENSEST `-S UBGRAPH: Given a graph G = (V, E) and an integer `, find a subset S ⊆ V of ` nodes to
maximize the number of edges in the induced subgraph G[S].
The current best polynomial-time approximation ratio for D ENSEST `-S UBGRAPH is O(n1/4+ε ) [1];
note that an `-approximation is easy. Although the problem is expected to be quite hard to approximate,
the known hardness results are weak; a PTAS for D ENSEST `-S UBGRAPH can be ruled out only under
ε
the assumption that NP 6⊆ ε>0 BPTIME(2n ) [11]. Polynomial-factor integrality gaps for several strong
T
SDP relaxations are known [2]. In a breakthrough result, Manurangsi [12] showed that under the
Exponential Time Hypothesis (ETH), D ENSEST `-S UBGRAPH is hard to approximate to a factor better
c
than n1/(log log n) where n is the number of nodes in the input graph and c > 0 is a universal constant. We
state his result more precisely in the theorem below.
Theorem 1.1 (Manurangsi). There exists a constant c > 0 such that the following holds, assuming
ETH. No polynomial-time algorithm can, given a graph G with n vertices and a positive integer ` ≤ n,
distinguish between the following two cases:
• G contains an `-clique as a subgraph.
` 1/(log log n)c edges.
• Every `-node subgraph of G has at most 2 /n
To formally state our result it is more convenient to relate the approximation ratio to the parameter s
of a given graph (or hypergraph) which is the sum of the number of nodes and edges (or hyperedges).
c0
The above theorem gives an s1/(log log s) -hardness for D ENSEST `-S UBGRAPH for some c0 > 0, since s
and n are polynomially related for graphs. On the other hand, the tight instances for the algorithm of [1]
for D ENSEST `-S UBGRAPH have |E| = Θ(|V |3/2 ). For these instances, it is not known how to obtain an
approximation ratio better than O(|V |1/4 ) = O(s1/6 ). Our main result is the following.
Theorem 1.2. Let α : N → R+ be a function. A polynomial-time α(s)-approximation algorithm for
k- WAY H YPERGRAPH C UT, where s is the size of the input hypergraph, implies a polynomial-time
2(α(t + 1))2 -approximation algorithm for D ENSEST `-S UBGRAPH where t is size of the input graph.
c
Corollary 1.3. Assuming ETH, there is no s1/(log log s) -approximation for k- WAY H YPERGRAPH C UT,
where c > 0 is a universal constant and s is size of the input hypergraph. In particular, assuming ETH,
c
there is no n1/(log log n) -approximation for k- WAY H YPERGRAPH C UT, where c > 0 is some universal
constant and n is the number of nodes in the input hypergraph.
Proof. The first part follows by combining the preceding theorem with Theorem 1.1. For the second part
we observe that the reduction in the proof of Theorem 1.2 creates instances of k- WAY H YPERGRAPH C UT
in which s is not greater than a fixed polynomial in n where n is the number of nodes of the hypergraph.
The second part follows from this.
4 D ENSEST `-S UBGRAPH problem is typically referred to as the D ENSEST k-S UBGRAPH problem. We use ` since k is
already used for k- WAY H YPERGRAPH C UT and several related problems.
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 3
C HANDRA C HEKURI AND S HI L I
When k is a fixed constant, one can reduce k- WAY H YPERGRAPH C UT and k- WAY S UB -MP to solving
O(nk−1 ) instances of the “terminal” version of these problems which have a 2(1 − 1/k) approximation.
We refer the readers to [5, 7] for more details on these related problems.
2 Proof of Theorem 1.2
Let (G = (V, E), `) be an instance of D ENSEST `-S UBGRAPH. We construct a hypergraph H = (A, F)
as follows. For each edge e ∈ E we create a node ae and add it to A. Moreover we add a new special
node r to A. Thus A = {r} ∪ {ae | e ∈ E}. For each node v ∈ V we add a hyperedge fv to F where
fv = {r} ∪ {ae | e ∈ δG (v)} where δG (v) is the set of edges in E that are incident to v in G. Thus H is
basically the hypergraph obtained from G by flipping the role of nodes and edges and then adding the
extra node r to each hyperedge. We also observe that |A| + |F| = 1 + |V | + |E| = s + 1.
For a subset S ⊆ V , we let EG (S) denote the set of edges in E with both endpoints in S. The following
is a simple but useful claim about the relationship between G and H.
Claim 2.1. For any 1 ≤ q ≤ |V |, if there is a set S ⊆ V with |S| = q and |EG (S)| = Q − 1 then the k- WAY
H YPERGRAPH C UT instance on H with k = Q has a cut of value at most q. Moreover, given any F ⊆ F
of size |F| = q0 such that H − F has Q0 connected components, there is a subset S0 ⊆ V such that |S0 | = q0
and |EG (S0 )| = Q0 − 1.
Proof. Consider a set F ⊆ F of hyperedges in H. Suppose we remove them from H. Let VF = {v ∈ V |
fv ∈ F} be the nodes in G that correspond to the hyperedges in F. Then a node ae ∈ A corresponding to
an edge e = uv is separated from r in H iff both u, v ∈ VF ; in this case the node ae becomes an isolated
node in H − F. Thus the number of connected components in H − F is precisely equal to |EG (VF )| + 1.
This correspondence proves both parts of the claim.
Suppose we have an α(s)-approximation for k- WAY H YPERGRAPH C UT. We obtain an approximation
for D ENSEST `-S UBGRAPH as follows. Let (G, `) be a given instance of D ENSEST `-S UBGRAPH. First
assume that we know the optimum solution value L for the given instance. We construct the hypergraph
H as described earlier, and give H and k = L + 1 to the α(s)-approximation algorithm for k- WAY
H YPERGRAPH C UT. By Claim 2.1 there is an optimum solution to the k- WAY H YPERGRAPH C UT
instance on H of value at most `.
Thus, the approximation algorithm will output a set F ⊆ F such that |F| ≤ α(s + 1) · ` such that
H − F has at least L + 1 connected components. For simplicity, we let α = α(s + 1). By the second part
of the claim we can obtain a set S0 ⊆ V such that |S0 | ≤ α · ` and |EG (S0 )| ≥ L. Then we shall output
a random subset S0 ⊆ S of size ` as the solution for the D ENSEST `-S UBGRAPH problem. Then, the
expected number of edges induced by S is
0 ` `−1 ` `−1 L 1 1 − 1/α
|EG (S )| · 0 · 0 ≥ L· · = −
|S | |S | − 1 α ·` α ·`−1 α α α` − 1
L 1 1 `−2 L
≥ − = · .
α α α` − α ` − 1 α2
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 4
O N THE H ARDNESS OF A PPROXIMATING THE k- WAY H YPERGRAPH C UT P ROBLEM
In the above sequence, we used α ≥ 1 and assumed ` ≥ 2. One can indeed efficiently and deterministically
find a set S ⊆ V of size ` such that |EG (S)| ≥ `−2 L
`−1 · α 2 , using the method of conditional expectations. This
holds since conditioned on the event that S contains a given set of vertices, the expectation of |EG (S)| can
be computed easily. Since L is the optimum value for the given instance of D ENSEST `-S UBGRAPH, we
obtain the desired `−1 2 `−1 2
`−2 · α = `−2 · (α(s + 1)) -approximation. The assumption that the algorithm knows
the value L can be easily removed by trying all possible values of L from 0 to |E(G)|. This completes the
proof of Theorem 1.2.
3 Discussion and open problems
We proved conditional hardness of k- WAY H YPERGRAPH C UT. An important open question is to obtain
hardness of approximation for k- WAY H YPERGRAPH C UT under the standard P 6= NP assumption. At
this point we do not even have APX-Hardness. For k- WAY S YM -S UB -MP Santiago [16] has shown an
exponential lower bound on the number of value oracle queries required to obtain an approximation
ratio strictly below 2. Can one show exponential query lower bounds for k- WAY S UB -MP even for
super-constant approximation factors? This question was raised in [16] based on the result in this paper.
For any fixed constant k, k-C UT in graphs can be solved in polynomial time [8]; there are several
different algorithms for this problem by now and we refer the reader to [6, 10] for a discussion of recent
work and other pointers. It was an open problem whether k- WAY H YPERGRAPH C UT can be solved in
polynomial time when k is a fixed constant. A randomized polynomial-time algorithm was developed
in [4], and recently a deterministic algorithm was obtained in [3]. The complexity status of k- WAY
S UB -MP is open for any fixed k > 3; for k ≤ 3 there is a polynomial-time algorithm [14] building upon
[18]. For k- WAY S YM -S UB -MP a polynomial-time algorithm is known for k ≤ 4 [9] and the complexity
status is open for any fixed k > 4.
Acknowledgements. We thank Laci Babai for suggestions that improved the clarity of the presentation.
References
[1] A DITYA B HASKARA , M OSES C HARIKAR , E DEN C HLAMTÁC , U RIEL F EIGE , AND A RAVIN -
DAN V IJAYARAGHAVAN : Detecting high log-densities: An O(n1/4 ) approximation for densest
k-subgraph. In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719,
arXiv:1001.2891] 3
[2] A DITYA B HASKARA , M OSES C HARIKAR , V ENKATESAN G URUSWAMI , A RAVINDAN V IJA -
YARAGHAVAN , AND Y UAN Z HOU : Polynomial integrality gaps for strong SDP relaxations of
densest k-subgraph. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp.
388–405. ACM Press, 2012. [doi:10.1137/1.9781611973099.34, arXiv:1110.1360] 3
[3] K ARTHEKEYAN C HANDRASEKARAN AND C HANDRA C HEKURI: Hypergraph k-cut for fixed k in
deterministic polynomial time. In Proc. 61st FOCS, pp. 810–821. IEEE Comp. Soc. Press, 2020.
[doi:10.1109/FOCS46700.2020.00080, arXiv:2009.12442] 2, 5
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 5
C HANDRA C HEKURI AND S HI L I
[4] K ARTHEKEYAN C HANDRASEKARAN , C HAO X U , AND X ILIN Y U: Hypergraph k-cut in ran-
domized polynomial time. Math. Programming, 2019:1–29. Preliminary version in SODA’18.
[doi:10.1007/s10107-019-01443-7] 2, 5
[5] C HANDRA C HEKURI AND A LINA E NE: Approximation algorithms for submodular multiway parti-
tion. In Proc. 52nd FOCS, pp. 807–816. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.34,
arXiv:1105.2048] 2, 4
[6] C HANDRA C HEKURI , K ENT Q UANRUD , AND C HAO X U: LP relaxation and tree packing for
minimum k-cut. SIAM J. Discrete Math., 34(2):1334–1353, 2020. Preliminary version in SOSA’19.
[doi:10.1137/19M1299359, arXiv:1808.05765] 5
[7] A LINA E NE , JAN VONDRÁK , AND Y I W U: Local distribution and the symmetry gap: Approximabil-
ity of multiway partitioning problems. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA’13), pp. 306–325. ACM Press, 2013. [doi:10.1137/1.9781611973105.23, arXiv:1503.03905]
4
[8] O LIVIER P. G OLDSCHMIDT AND D ORIT S. H OCHBAUM: A polynomial algorithm for the k-cut
problem for fixed k. Math. Oper. Res., 19(1):24–37, 1994. [doi:10.1287/moor.19.1.24] 2, 5
[9] F LAVIO G UÍÑEZ AND M AURICE Q UEYRANNE: The size-constrained submodular k-partition
problem. Unpublished manuscript. Available on Google Docs. See also slides on author’s home
page, 2012. 5
[10] A NUPAM G UPTA , DAVID G. H ARRIS , E UIWOONG L EE , AND JASON L I: Optimal bounds for the
k-cut problem, 2020. [arXiv:2005.08301] 5
[11] S UBHASH K HOT: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipar-
tite clique. SIAM J. Comput., 36(4):1025–1071, 2006. Preliminary version in FOCS’04.
[doi:10.1137/S0097539705447037] 3
[12] PASIN M ANURANGSI: Almost-polynomial ratio ETH-hardness of approximating densest k-
subgraph. In Proc. 49th STOC, pp. 954–961. ACM Press, 2017. [doi:10.1145/3055399.3055412,
arXiv:1611.05991] 3
[13] PASIN M ANURANGSI: Inapproximability of maximum biclique problems, minimum k-cut and
densest at-least-k-subgraph from the Small Set Expansion Hypothesis. Algorithms, 11(1):1–10,
2018. Preliminary version in ICALP’17. [doi:10.3390/a11010010] 2
[14] K AZUMASA O KUMOTO , TAKURO F UKUNAGA , AND H IROSHI NAGAMOCHI: Divide-and-conquer
algorithms for partitioning hypergraphs and submodular systems. Algorithmica, 62(3):787–806,
2012. Preliminary version in ISAAC’09. [doi:10.1007/s00453-010-9483-0] 2, 5
[15] M AURICE Q UEYRANNE: On optimum size-constrained set partitions. In Abstracts, Combinatorial
Optimization Workshop, AUSSOIS, 1999. AUSSOIS. 2
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 6
O N THE H ARDNESS OF A PPROXIMATING THE k- WAY H YPERGRAPH C UT P ROBLEM
[16] R ICHARD S ANTIAGO: Multi-Agent Submodular Optimization: Variations and Generalizations.
Ph. D. thesis, McGill University, 2019. LINK at eScholarship@McGill. 5
[17] H UZUR S ARAN AND V IJAY V. VAZIRANI: Finding k-cuts within twice the optimal. SIAM J. Com-
put., 24(1):101–108, 1995. Preliminary version in FOCS’91. [doi:10.1137/S0097539792251730]
2
[18] M INGYU X IAO: Finding minimum 3-way cuts in hypergraphs. Inform. Process. Lett., 110(14-
15):554–558, 2010. Preliminary version in TAMC’08. [doi:10.1016/j.ipl.2010.05.003] 5
[19] L IANG Z HAO , H IROSHI NAGAMOCHI , AND T OSHIHIDE I BARAKI: Greedy splitting algorithms
for approximating multiway partition problems. Math. Programming, 102(1):167–183, 2005.
[doi:10.1007/s10107-004-0510-2] 2
AUTHORS
Chandra Chekuri
Professor
Department of Computer Science
University of Illinois
Urbana, IL 61801
chekuri illinois edu
http://chekuri.cs.illinois.edu
Shi Li
Assistant professor
Department of Computer Science and Engineering
University at Buffalo
Buffalo, NY 14260
shil buffalo edu
https://www.cse.buffalo.edu/~shil/
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 7
C HANDRA C HEKURI AND S HI L I
ABOUT THE AUTHORS
C HANDRA C HEKURI received his B. Tech in Computer Science and Engineering from
Indian Institute of Technology, Madras (now Chennai) in 1993 and received his Ph. D. in
Computer Science from Stanford University in 1998 under the supervision of the late
Rajeev Motwani. After finishing his Ph. D. he worked eight formative years at Lucent
Bell Labs before moving to the University of Illinois. He is interested in many topics but
mainly works in algorithm design, combinatorial optimization, graphs, and mathematical
programming. He has very much enjoyed teaching since he was in middle school. His
childhold was spent mostly in the town of Rajahmundry on the banks of the beautiful
river Godavari where his parents still live and his children like to visit.
S HI L I received his Ph. D. in 2013 from the Department of Computer Science at Princeton
University, under the supervision of Moses Charikar. From 2013 to 2015, he was a
research assistant professor at the Toyota Technological Institute at Chicago. His research
interest is algorithm design.
T HEORY OF C OMPUTING, Volume 16 (14), 2020, pp. 1–8 8