Authors Anand Louis, Yury Makarychev,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2014
Approximation Algorithms for
Hypergraph Small-Set Expansion and
Small-Set Vertex Expansion
Anand Louis∗ Yury Makarychev†
Received March 31, 2015; Revised September 20, 2016; Published October 30, 2016
Abstract: The expansion of a hypergraph, a natural extension of the notion of expansion in
graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of
the hyperedges cut to the size of the smaller side of the cut. We study the Hypergraph Small-
Set Expansion problem, which, for a parameter δ ∈ (0, 1/2], asks to compute the cut having
the least expansion while having at most δ fraction of the vertices on the smaller side of the
cut. We present two algorithms. Our first algorithm gives anp e −1 √log n)–approximation.
O(δ
The second algorithm finds a set with expansion O(δ e −1 ( dmax r−1 log r φ ∗ + φ ∗ )) in an
r–uniform hypergraph with maximum degree dmax (where φ ∗ is the expansion of the optimal
solution). Using these results, we also obtain algorithms for the Small-Set Vertex Expansion
A conference version of this paper appeared in the Proceedings of the 17th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX’2014) [18].
∗ The author was supported by the Simons Collaboration on Algorithms and Geometry while he was affiliated with Princeton
University. Part of work done while the author was a student at Georgia Tech and supported by Santosh Vempala’s NSF award
CCF-1217793.
† Supported by NSF CAREER award CCF-1150062 and NSF award IIS-1302662.
ACM Classification: F.2.2, G.1.6
AMS Classification: 68W25
Key words and phrases: approximation algorithms, hypergraph expansion, small-set expansion
© 2016 Anand Louis and Yury Makarychev
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2016.v012a017
A NAND L OUIS AND Y URY M AKARYCHEV
e −1 √log n)–approximation algorithm and an algorithm that finds a
problem: we get an O(δ
set with vertex expansion
p
Oe δ −1 φ V log dmax + δ −1 φ V
(where φ V is the vertex expansion of the optimal solution).
For δ = 1/2, Hypergraph Small-Set Expansion is equivalent to the hypergraph expansion
√
problem. In this case, our approximation factor of O( log n) for expansion in hypergraphs
matches the corresponding approximation factor for expansion in graphs due to Arora, Rao,
and Vazirani (JACM 2009).
1 Introduction
The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as
follows.
Definition 1.1 (Hypergraph Expansion). Given a hypergraph H = (V, E) on n vertices (each edge e ∈ E
of H is a subset of vertices), we say that an edge e ∈ E is cut by a set S if e ∩ S 6= ∅ and e ∩ S̄ 6= ∅ (i. e.,
some vertices in e lie in S and some vertices lie outside of S). We denote the set of edges cut by S by
Ecut (S). The expansion φ (S) of a set S ⊂ V (S 6= ∅, S 6= V ) in a hypergraph H = (V, E) is defined as
|Ecut (S)|
φ (S) = .
min(|S|, |S̄|)
Hypergraph expansion and related hypergraph partitioning problems are of immense practical impor-
tance, having applications in parallel and distributed computing [6], VLSI circuit design and computer
architecture [13], scientific computing [10] and other areas. In spite of this, there has not been much
theoretical work on hypergraph partitioning problems. In this paper, we study a generalization of the
Hypergraph Expansion problem, namely the Hypergraph Small-Set Expansion problem.
Problem 1.2 (Hypergraph Small-Set Expansion Problem). Given a hypergraph H = (V, E) and a pa-
rameter δ ∈ (0, 1/2], the Hypergraph Small-Set Expansion problem (H-SSE) is to find a set S ⊂ V of
size at most δ n that minimizes φ (S). The value of the optimal solution to H-SSE is called the small-set
expansion of H. That is, for δ ∈ (0, 1/2], the small-set expansion φH,δ∗ of a hypergraph H = (V, E) is
defined as
∗
φH,δ = min φ (S) .
S⊂V
0<|S|≤δ n
Note that for δ = 1/2, the Hypergraph Small-Set Expansion Problem is the Hypergraph Expansion
Problem.
We note that H-SSE can be reduced to SSE (small-set expansion in graphs) if all hyperedges have
bounded size. Let r be the size of the largest hyperedge in H. Construct an auxiliary (weighted) graph
F on V as follows: pick a vertex in each hyperedge e and connect it in F to all other vertices of e (i. e.,
replace e with a star); let the weight of an edge f in F be the total weight of the hyperedges e ∈ E for
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 2
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
which f is part of the representative star of e. Then solve SSE in the graph F. It is easy to see that if
we solve SSE using an p α–approximation algorithm, then we get (r − 1)α–approximation for H-SSE.
This approach gives O( log n log(1/δ
p ))–approximation if r is bounded. However, if H is an arbitrary
hypergraph, we only get an O(n log n log(1/δ ))–approximation. The goal of this paper is to give an
approximation guarantee valid for hypergraphs with hyperedges of arbitrary size.
Related work. Small-Set Expansion in graphs has attracted a lot of attention recently. The problem
was introduced by Raghavendra and Steurer [22], who showed that it is closely related to the Unique
Games problem. Raghavendra, Steurer and Tetali [23] designed an algorithm for SSE that finds a set
of size O(δ n) with expansion O( φ ∗ d log(1/δ )) in d regular graphs (where φ ∗ is the expansion of the
p
optimal solution).
p Later Bansal, Feige, Krauthgamer, Makarychev, Nagarajan, Naor, and Schwartz [5]
gave a O( log n log(1/δ ))–approximation algorithm for the problem. In a different direction, Louis [16]
and Chan, Louis, Tang and Zhang [7] studied a heat (Markov) operator for hypergraphs and showed
connections between its spectrum and some combinatorial properties of hypergraphs. In particular, they
used some tools developed in this paper to show connections between the small-set expansion of a
hypergraph and higher eigenvalues of its heat operator.
Our results. We present analogs of the results by Bansal et al. [5] and Raghavendra, Steurer and
Tetali [23] for hypergraphs.
Theorem 1.3. There is a randomized polynomial-time approximation algorithm for the Hypergraph Small-
Set Expansion problem that, given a hypergraph H = (V, E) and parameters ε ∈ (0, 1) and δ ∈ (0, 1/2),
finds a set S ⊂ V of size at most (1 + ε)δ n such that
φ (S) ≤ Oε δ −1 log δ −1 log log δ −1 · log n · φH,δ
∗ eε δ −1 log n φ ∗
p p
=O H,δ ,
(where the constant in the O notation depends polynomially on 1/ε). That is, the algorithm gives
√
O( log n)–approximation when δ and ε are fixed.
We state our second result, Theorem 1.4, for r-uniform hypergraphs. We present and prove a more general
Theorem 6.3 that applies to any hypergraphs in Section 6.
Theorem 1.4. There is a randomized polynomial-time algorithm for the Hypergraph Small-Set Expansion
problem that, given an r–uniform hypergraph H = (V, E) with maximum degree dmax and parameters
ε ∈ (0, 1) and δ ∈ (0, 1/2), finds a set S ⊂ V of size at most (1 + ε)δ n such that
r !!
−1 log r ∗
φ (S) ≤ Oeε δ dmax φ ∗ + φH,δ .
r H,δ
Our algorithms for H-SSE are bi-criteria approximation algorithms in that they output a set S of size
at most (1 + ε)δ n. We note that this is similar to the algorithm by Bansal et al. [5] for SSE, which also
finds a set of size at most (1 + ε)δ n rather than a set of size at most δ n. The algorithm by Raghavendra,
Steurer and Tetali [23] finds a set of size O(δ n). The approximation factor of our first algorithm does
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 3
A NAND L OUIS AND Y URY M AKARYCHEV
not depend on the size of hyperedges in the input hypergraph. It has the same dependence on n as the
algorithm by Bansal et al. [5] for SSE. However, the dependence on 1/δ is quasi-linear; whereas it is
logarithmic in the algorithm by Bansal et al. [5]. In fact, we show that the integrality gap of the standard
SDP relaxation for H-SSE is at least linear in 1/δ (Theorem 7.1). The approximation guarantee of our
second algorithm is analogous to that of the algorithm by Raghavendra, Steurer and Tetali [23].
Small-Set Vertex Expansion. Our techniques can also be used to obtain an approximation algorithm
for Small-Set Vertex Expansion (SSVE) in graphs.
Problem 1.5 (Small-Set Vertex Expansion Problem). Given graph G = (V, E), the vertex expansion of a
set S ⊂ V is defined as
|{u ∈ S̄ : ∃ v ∈ S such that {u, v} ∈ E}|
φ V (S) = .
|S|
Given a parameter δ ∈ (0, 1/2], the Small-Set Vertex Expansion problem (SSVE) is to find a set S ⊂ V of
size at most δ n that minimizes φ V (S). The value of the optimal solution to SSVE is called the small-set
vertex expansion of G. That is, for δ ∈ (0, 1/2], the small-set expansion φG,δV of a graph G = (V, E) is
defined as
V
φG,δ = min φ V (S) .
S⊂V
0<|S|≤δ n
Small-Set Vertex Expansion recently gained attention thanks to its connection to obtaining sub-
exponential-time, constant-factor approximation algorithms for several combinatorial problems like
Sparsest Cut and Graph Coloring [2, 19]. Using a reduction from vertex expansion in graphs to hypergraph
expansion, we can get an approximation algorithm for SSVE having the same approximation guarantee
as that for H-SSE.
Theorem 1.6 (“Graph to Hypergraph Theorem,” informal statement). There exist absolute constants
c1 , c2 ∈ R+ such that for every graph G = (V, E), there exists a polynomial-time computable hypergraph
H = (V 0 , E 0 ) such that c1 φH,δ
∗ ≤ φ V ≤ c φ ∗ . Furthermore, the algorithm for H-SSE from Theorem 6.3
G,δ 2 H,δ
applies to H.
A detailed version of this statement appears as Theorem 8.2 in Section 8.
From this theorem, Theorem 1.3 and Theorem 6.3 we immediately get algorithms for SSVE.
Theorem 1.7 (Corollary to Theorem 1.3 and Theorem 8.2). There is a randomized polynomial-time
approximation algorithm for the Small-Set Vertex Expansion problem that, given a graph G = (V, E) and
parameters ε ∈ (0, 1) and δ ∈ (0, 1/2)), finds a set S ⊂ V of size at most (1 + ε)δ n such that
p
φ V (S) ≤ Oε log n δ −1 log δ −1 log log δ −1 · φG,δ
V
.
√
That is, the algorithm gives O( log n)–approximation when δ and ε are fixed.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 4
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
Theorem 1.8 (Corollary to Theorem 6.3 and Theorem 8.2). There is a randomized polynomial-time
algorithm for the Small-Set Vertex Expansion problem that, given a graph G = (V, E) of maximum degree
dmax and parameters ε ∈ (0, 1) and δ ∈ (0, 1/2), finds a set S ⊂ V of size at most (1 + ε)δ n such that
q
V V −1 −1 −1 −1 V
φ (S) ≤ Oε φG,δ log dmax · δ log δ log log δ + δ φG,δ
q
=O eε δ −1 φ V log dmax + δ −1 φ V .
G,δ G,δ
We note that the Small-Set Vertex Expansion problem for δ = 1/2 is just the Vertex Expansion
problem. In that case, Theorem 1.7 gives the same approximation guarantee as the algorithm by Feige,
Hajiaghayi, and Lee [12] (see also [1]); Theorem 1.8 gives the same approximation guarantee as the
algorithm by Louis, Raghavendra, and Vempala [20]. To the best of our knowledge, Theorem 1.7 and
Theorem 1.8 are the first non-trivial approximation algorithms for SSVE. We mention that Chuzhoy
et al. [9] considered a bipartite variant of SSVE (which is somewhat similar but not equivalent to the
problem we study in this paper) and proved a hardness result for it in the regime where δ is polynomially
small.
Remark 1.9. We note that the notion of hypergraph expansion is not directly related to the notion of
coboundary expansion of simplicial complexes [15, 14, 11]. Aside from an obvious distinction that
the former applies to hypergraphs and the latter applies to simplicial complexes, these two types of
expansion measure very different parameters of hypergraphs/simplicial complexes. For instance, consider
an r-uniform hypergraph H = (V, E) (with r ≥ 3), in which every two hyperedges intersect in at most
r − 2 vertices, and the corresponding simplicial complex X = {σ ⊂ e : e ∈ E} over F2 .
Then, the hypergraph expansion of H may be more or less arbitrary, while the coboundary expansion
of X in dimension r is equal to 1.
Techniques. Our general approach to solving H-SSE is similar to the approach of Bansal et al. [5]. We
recall how the algorithm by Bansal et al. [5] for (graph) SSE works. The algorithm solves a semidefinite
programming relaxation for SSE and gets an SDP solution. The SDP solution assigns a vector ū to each
vertex u. Then the algorithm generates an orthogonal separator. Informally, an orthogonal separator S
with distortion D is a random subset of vertices such that the following hold.
(a) If ū and v̄ are close to each other then the probability that u and v are separated by S is small;
namely, it is at most αDkū − v̄k2 , where α is a normalization factor such that Pr (u ∈ S) = αkūk2 .
(b) If the angle between ū and v̄ is larger than a certain threshold, then the probability that both u and v
are in S is much smaller than the probability that one of them is in S.
Bansal et al. [5] showed that condition (b) together with SDP constraints implies that S is of size at most
(1 + ε)δ n with sufficiently high probability. Then condition (a) implies that the expected number of cut
edges is at most D times the SDP value. That means that S is a D–approximate solution to SSE.
If we run this algorithm on an instance of H-SSE, we will still find a set of size at most (1 + ε)δ n,
but the cost of the solution might be very high. Indeed, consider a hyperedge e. Even though every two
vertices u and v in e are unlikely to be separated by S, at least one pair out of |e|
2 pairs of vertices is quite
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 5
A NAND L OUIS AND Y URY M AKARYCHEV
likely to be separated by S; hence, e is quite likely to be cut by S. To deal with this problem, we develop
hypergraph orthogonal separators. In the definition of a hypergraph orthogonal separator, we strengthen
condition (a) by requiring that a hyperedge e is cut by S with small probability if all vertices in e are close
to each other. Specifically, we require that
Pr (e is cut by S) ≤ αD max kū − v̄k2 . (1.1)
u,v∈e
√
We show that there is a hypergraph orthogonal separator with distortion proportional to log n (the
distortion also depends on parameters of the orthogonal separator). Plugging this hypergraph orthogonal
separator in the algorithm by Bansal et al. [5], we get Theorem 1.3. We also develop another variant
of hypergraph orthogonal separators, `2 –`22 orthogonal separators. An `2 –`22 orthogonal separator with
`2 –distortion D`2 (r) and `22 –distortion D`2 satisfies the following condition.1
2
Pr (e is cut by S) ≤ αD`2 (|e|) · min kw̄k · max kū − v̄k + αD`2 · max kū − v̄k2 . (1.2)
w∈E u,v∈e 2 u,v∈e
We show that there is an `2 -`22 hypergraph orthogonal separator whose `2 and `22 distortions do not depend
on n. (In contrast, there is no hypergraph orthogonal separator whose distortion does not depend on n.)
This result yields Theorem 1.4.
We now give a brief conceptual overview of our construction of hypergraph orthogonal separators.
We use the framework developed by Chlamtáč et al. [8, Section 4.3] for (graph) orthogonal separators.
For simplicity, we ignore vector normalization steps in this overview; we do not explain how we take
into account vector lengths. Note, however, that these normalization steps are crucial. We first design a
procedure that partitions the hypergraph into two pieces (the procedure labels every vertex with either
0 or 1). In a sense, each set S in the partition is a “very weak” hypergraph orthogonal separator. It
√
satisfies property (1.1) with D0 ∼ log n log log(1/δ ) and α0 = 1/2 and a weak variant of property (b):
if the angle between vectors ū and v̄ is larger than the threshold then events u ∈ S and v ∈ S are “almost”
independent. We repeat the procedure l = log2 (1/δ ) + O(1) times and obtain a partition of graph into
2l = O(1/δ ) pieces. Then we randomly choose one set S among them; this set S is our hypergraph
orthogonal separator. Note that by running the procedure many times we decrease exponentially in l the
probability that two vertices, as in condition (b), belong to S. So condition (b) holds for S. Also, we effect
the distortion in (1.1) in two ways. First, the probability that the edge is cut increases by a factor of l.
That is, we get
Pr (e is cut by S) ≤ l × α0 D0 max kū − v̄k2 .
u,v∈e
1 It may look strange that we have two terms in the bound. One may expect that we can either have only term
D`2 max kū − v̄k2
2 u,v∈e
(as in the previous definition) or only term
D`2 (|e|) · min kw̄k · max kū − v̄k .
w∈E u,v∈e
However, the latter is not possible—there is no `2 –`22 separator with D`2 = 0.
2
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 6
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
minimize ∑ max kū − v̄k2 (2.1)
u,v∈e
e∈E
subject to:
∑ hū, v̄i ≤ δ n · kūk2 for every u ∈ V , (2.2)
v∈V
∑ kūk2 = 1 , (2.3)
u∈V
kū − v̄k2 + kv̄ − w̄k2 ≥ kū − w̄k2 for every u, v, w ∈ V , (2.4)
2
0 ≤ hū, v̄i ≤ kūk for every u, v ∈ V . (2.5)
Figure 1: SDP relaxation for H-SSE.
Second, the probability that we choose a vertex u goes down from kūk2 /2 to Ω(δ )kūk2 since roughly
speaking we choose one set S among O(1/δ ) possible sets. That is, the parameter α of S is Ω(δ ).
Therefore,
Pr (e is cut by S) ≤ α(α0 lD0 /α) max kū − v̄k2 .
u,v∈e
That is, we get a hypergraph orthogonal separator with distortion (α0 lD0 /α) ∼ O(δe −1 √log n). The
construction of `2 –`22 orthogonal separators is similar but a bit more technical.
Organization. We present our SDP relaxation and introduce our main technique, hypergraph orthogonal
separators, in Section 2. We describe our first algorithm for H-SSE in Section 3, and then describe an
algorithm that generates hypergraph orthogonal separators in Section 4. We define `2 –`22 hypergraph
orthogonal separators, give an algorithm that generates them, and then present our second algorithm for
H-SSE in Sections 5 and 6. Finally, we show a simple SDP integrality gap for H-SSE in Section 7. This
integrality gap also gives a lower bound on the quality of m-orthogonal separators. We give a proof of
Theorem 8.2 in Section 8.
2 Preliminaries
2.1 SDP relaxation for Hypergraph Small-Set Expansion
We use the SDP relaxation for H-SSE shown in Figure 1. There is an SDP variable ū for every vertex
u ∈ V . Our spreading constraint (2.2) is a standard spreading constraint used to ensure that only a small
number of vectors have “large” norms [23,p5, 17]. An illustrative example is the SDP solution obtained
by fixing a set S ⊂ V , and defining ū = a/ |S|, if u ∈ S; ū = 0, otherwise, where a is a fixed unit vector.
This solution will satisfy the spreading constraint (2.2) only if |S| ≤ δ n.
p combinatorial solution S (with |S| ≤ δ n) defines the corresponding (intended) SDP solution:
Every
ū = a/ |S|, if u ∈ S; ū = 0, otherwise, where a is a fixed unit vector. It is easy to see that this solution
satisfies all SDP constraints. Note that maxu,v∈e kū − v̄k2 is equal to 1/|S|, if e is cut, and to 0, otherwise.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 7
A NAND L OUIS AND Y URY M AKARYCHEV
Therefore, the objective function equals
1 Ecut (S)
∑ max kū − v̄k2 = ∑ = = φ (S) .
e∈E
u,v∈e
e∈Ecut (S)
|S| S
Thus our SDP for H-SSE is indeed a relaxation. We denote the value of the optimal SDP solution by
sdpcost.
2.2 Hypergraph orthogonal separators
The main technical tool for proving Theorem 1.3 is hypergraph orthogonal separators. Orthogonal
separators were introduced by Chlamtáč, Makarychev, and Makarychev [8] (see also [5, 17, 21]) and
were previously used for solving Unique Games and various graph partitioning problems. In this paper,
we extend the technique of orthogonal separators to hypergraphs and introduce hypergraph orthogonal
separators. We then use hypergraph orthogonal separators to solve H-SSE. In Section 5, we introduce
another version of hypergraph orthogonal separators, `2 –`22 hypergraph orthogonal separators, and then
use them to prove Theorems 1.4 and 6.3.
Definition 2.1 (Hypergraph Orthogonal Separators). Let {ū : u ∈ V } be a set of vectors in the unit ball
that satisfy `22 –triangle inequalities (2.4) and (2.5). We say that a random set S ⊂ V is a hypergraph
m-orthogonal separator with distortion D ≥ 1, probability scale α > 0, and separation threshold β ∈ (0, 1)
if it satisfies the following properties.
1. For every u ∈ V , Pr(u ∈ S) = αkūk2 .
2. For every u and v such that kū − v̄k2 ≥ β min(kūk2 , kv̄k2 ),
min(kūk2 , kv̄k2 )
Pr (u ∈ S and v ∈ S) ≤ α .
m
3. For every e ⊂ V , Pr (e is cut by S) ≤ αD maxu,v∈e kū − v̄k2 .
The definition of a hypergraph m-orthogonal separator is similar to that of a (graph) m-orthogonal
separator: a random set S is an m-orthogonal separator if it satisfies properties 1, 2, and property 30 , which
is property 3 restricted to edges e of size 2.
30 . For every (u, v), Pr (e is cut by S) ≤ αDkū − v̄k2 .
In this paper, we design an algorithm that generates a hypergraph m-orthogonal separator with distortion
√
Oβ ( log n · m log m log log m). We note that the distortion of any hypergraph orthogonal separator must
depend on m at least linearly (see Section 7). We remark that there are two constructions of (graph)
orthogonal separators, “orthogonal separators via `1 ” and “orthogonal separators via `2 ,” with distortions,
√ √
Oβ ( log n log m) and Oβ ( log n log m), respectively (presented in [8]). Our construction of hypergraph
orthogonal separators uses the framework of orthogonal separators via `1 . We prove the following theorem
in Section 4.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 8
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
Theorem 2.2. There is a polynomial-time randomized algorithm that given a set of vertices V , a set
of vectors {ū} satisfying `22 –triangle inequalities (2.4) and (2.5), parameters m ≥ 2 and β ∈ (0, 1),
generates a hypergraph m-orthogonal separator with probability scale α ≥ 1/n and distortion D =
√
O(β −1 m log m log log m × log n).
3 Algorithm for Hypergraph Small-Set Expansion
In this section, we present our algorithm for Hypergraph Small-Set Expansion. Our algorithm uses
hypergraph orthogonal separators that we describe in Section 4. We use the approach of Bansal et
al. [5]. Suppose that we are given a polynomial-time algorithm that generates hypergraph m-orthogonal
separators with distortion D(m, β ) (with probability scale α > 1/ poly(n)). We show how to get a
D∗ = 4D(4/(εδ ), ε/4)–approximation for H-SSE.
Theorem 3.1. There is a randomized polynomial-time approximation algorithm for the Hypergraph Small-
Set Expansion problem that given a hypergraph H = (V, E), and parameters ε ∈ (0, 1) and δ ∈ (0, 1/2)
∗ .
finds a set S ⊂ V of size at most (1 + ε)δ n such that φ (S) ≤ 4D(4/(εδ ), ε/4) · φH,δ
Proof. We solve the SDP relaxation for H-SSE and obtain an SDP solution {ū}. Consider a hypergraph
orthogonal separator S with m = 4/(εδ ) and β = ε/4. Define a set S0 :
(
0 S if |S| ≤ (1 + ε)δ n,
S =
∅ otherwise.
Clearly, |S0 | ≤ (1 + ε)δ n. Bansal et al. [5] showed the following lemma (see also Theorem A.1 in [21]);
for completeness, we reproduce their proof here.
Lemma 3.2 (Bansal et al. [5]). Pr(u ∈ S0 ) ∈ (α/2) kūk2 , αkūk2 for every u ∈ V .
Proof. Clearly, Pr (u ∈ S0 ) ≤ Pr (u ∈ S) = αkūk2 . Now, let
Au := v̄ : kū − v̄k2 ≥ β kūk2 Bu := v̄ : kū − v̄k2 < β kūk2 .
and
We show that only a small fraction of Au belongs to S, and that the set Bu is small.
For any v ∈ Bu , we have
kūk2 − hū, v̄i = kū − v̄k2 − (kv̄k2 − hū, v̄i) < β kūk2 .
Therefore, hū, v̄i > (1 − β )kūk2 . Now,
hū, v̄i 1 δn
|Bu | ≤ ∑ 2
≤ ∑ hū, v̄i ≤ ≤ δ (1 + 2β )n = 1 + ε/2 δn.
v∈Bu (1 − β )kūk (1 − β )kūk2 v∈V 1−β
Here, the last inequality uses (2.2).
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 9
A NAND L OUIS AND Y URY M AKARYCHEV
For an arbitrary v ∈ Au , by the first and second properties of orthogonal separators, Pr (v ∈ S | u ∈ S) ≤
1/m. Thus, E [|Au ∩ S| | u ∈ S] ≤ n/m. Therefore, using Markov’s inequality,
n/m 1
Pr (|Au ∩ S| ≥ εδ n/2 | u ∈ S) ≤ ≤ .
εδ n/2 2
Therefore,
1
Pr (|S| ≤ (1 + ε)δ n) ≥ Pr (|Au ∩ S| ≤ εδ n/2 | u ∈ S) ≥
2
and
αkūk2
Pr u ∈ S0 ≥ αkūk2 Pr (|S| ≤ (1 + ε)δ n) ≥
.
2
Note that
Pr S0 cuts edge e ≤ Pr (S cuts edge e) ≤ αD∗ max kū − v̄k2
u,v∈e
where D∗ denotes D(4/(εδ ), ε/4) for the sake of brevity. Let
|Ecut (S0 )|
Z = |S0 | − .
4D∗ · sdpcost
We have
E [|Ecut (S0 )|] α ∑ αD∗ maxu,v∈e kū − v̄k2
E [Z] = E |S0 | − ∗ ≥ ∑ · kūk2 − e∈E
4D · sdpcost u∈V 2 4D∗ · sdpcost
α αD∗ sdpcost α
= − ∗ = .
2 4D · sdpcost 4
Since Z ≤ |S0 | ≤ (1 + ε)δ n < n (always), by Markov’s inequality, we have Pr (Z > 0) ≥ α/(4n) and
hence
Pr |Ecut (S0 )|/|S0 | < 4D∗ · sdpcost ≥ α/(4n) .
We sample S independently 4n/α times and return the first set S0 such that
|Ecut (S0 )|
< 4D∗ · sdpcost .
|S0 |
This gives a set S0 such that |S0 | ≤ (1 + ε)δ n, and φ (S0 ) ≤ 4D∗ φH,δ
∗ . The algorithm succeeds (finds
such a set S0 ) with a constant probability. By repeating the algorithm n times, we can make the success
probability exponentially close to 1.
In Section 4, we describe how to generate an m-hypergraph orthogonal separator with distortion
D = O log n × β −1 m log m log log m .
p
That gives us an algorithm for H-SSE with approximation factor
Oε δ −1 log δ −1 log log δ −1 × log n .
p
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 10
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
4 Generating hypergraph orthogonal separators
In this section, we present an algorithm that generates a hypergraph m-orthogonal separator. At the high
level, the algorithm is similar to the algorithm for generating orthogonal separators from Section 4.3 in
the paper by Chlamtáč, Makarychev, and Makarychev [8]. We use a different procedure for generating
words W (u) (see below) and set parameters differently; also the analysis of our algorithm is different. As
in [8], our algorithm has three main steps.
Our first step is to use a “normalization” map ϕ (the step is identical to one in [8]). This normalization
transforms the set of vectors into a set of functions in L2 [0, ∞], so that the image of every non-zero vector
is a function with L2 norm 1; the images of orthogonal vectors are orthogonal; the distance between the
images of u and v is roughly preserved. Moreover, the images satisfy L22 triangle inequalities. The map ϕ
is defined as follows. (
u, if t ≤ 1/kūk2 ,
ϕ(u)(t) =
0, otherwise.
Formally, ϕ has the following properties.
1. For all vertices u, v, w, kϕ(ū) − ϕ(v̄)k22 + kϕ(v̄) − ϕ(w̄)k22 ≥ kϕ(ū) − ϕ(w̄)k22 .
hū, v̄i
2. For all nonzero vertices u and v, hϕ(ū), ϕ(v̄)i = .
max(kūk2 , kv̄k2 )
3. In particular, for every ū 6= 0, kϕ(ū)k22 = hϕ(ū), ϕ(ū)i = 1. Also, ϕ(0) = 0.
2 kū − v̄k2
4. For all non-zero vectors ū and v̄, kϕ(ū) − ϕ(v̄)k22 ≤ .
max(kūk2 , kv̄k2 )
In the second step of our algorithm, we also use the following theorem by Arora, Lee, and Naor [3] (see
also [4]).
Theorem 4.1 (Arora, Lee, and Naor (2005), Theorem 3.1). There exist constants C ≥ 1 and p ∈ (0, 1/4)
such that for every n unit vectors xu (u ∈ V ), satisfying `22 –triangle inequalities (2.4), and every ∆ > 0, the
following holds. There exists a random subset U of V such that for every u, v ∈ V with kxu − xv k2 ≥ ∆,
∆
Pr u ∈ U and d(v,U) ≥ √ ≥ p,
C log n
where d(v,U) = minu∈U kxu − xv k2 .
The second step of our algorithm is summarised by the following lemma. In this step, we describe an
algorithm that randomly assigns each vertex u a symbol, either 0 or 1. In this step, we deviate from the
algorithm in [8].
Lemma 4.2. There is a randomized polynomial-time algorithm that, given a finite set V , unit vectors ϕ(ū)
for u ∈ V satisfying `22 -triangle inequalities, and a parameter β ∈ (0, 1), returns a random assignment
ω : V → {0, 1} that satisfies the following properties.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 11
A NAND L OUIS AND Y URY M AKARYCHEV
• For every u and v such that kϕ(ū) − ϕ(v̄)k2 ≥ β , we have Pr (ω(u) 6= ω(v)) ≥ 2p, where p > 0 is
the constant from Theorem 4.1.
• For every set e ⊂ V of size at least 2,
Pr (ω(u) 6= ω(v) for some u, v ∈ e) ≤ O β −1
p
log n max kϕ(ū) − ϕ(v̄)k2 .
u,v∈e
Proof. Let U be the random set from Theorem 4.1 for vectors xu = ϕ(ū) and ∆ = β . Choose t ∈
√
(0, ∆/(C log n)) uniformly at random. Let
(
0, if d(u,U) ≤ t,
ω(u) =
1, otherwise.
Consider first vertices u and v such that kϕ(ū) − ϕ(v̄)k2 ≥ β . By Theorem 4.1,
∆ ∆
Pr u ∈ U and d(v,U) ≥ √ ≥p and Pr v ∈ U and d(u,U) ≥ √ ≥ p.
C log n C log n
√
Note that in the former case, when u ∈ U and d(v,U) ≥ ∆/(C log n), we have ω(u) = 0 and ω(v) = 1;
√
in the latter case, when v ∈ U and d(u,U) ≥ ∆/(C log n), we have ω(v) = 0 and ω(u) = 1. Therefore,
the probability that ω(u) 6= ω(v) is at least 2p.
Now consider a set e ⊂ V of size at least 2. Let
τm = min d(U, ϕ(w̄)) and τM = max d(U, ϕ(w̄)) .
w∈e w∈e
We have τM − τm ≤ maxu,v∈e kϕ(ū) − ϕ(v̄)k2 . Note that if t < τm then ω(u) = 1 for all u ∈ e; if t ≥ τM
then ω(u) = 0 for all u ∈ e. Thus ω(u) 6= ω(v) for some u, v ∈ e only if t ∈ [τm , τM ). Since the probability
√
density of the random variable t is at most C log n, we get,
√
C log n
Pr (∃ u, v ∈ e : ω(u) 6= ω(v)) ≤ Pr (t ∈ [τm , τM )) ≤ max kϕ(ū) − ϕ(v̄)k2 .
β u,v∈e
We now amplify the result of Lemma 4.2.
Lemma 4.3. There is a randomized polynomial time algorithm that given V , vectors ϕ(ū) and β ∈ (0, 1)
as in Lemma 4.2, and a parameter m ≥ 2, returns a random assignment ω̃ : V → {0, 1} such that the
following hold.
• For every u and v such that kϕ(ū) − ϕ(v̄)k2 ≥ β ,
Pr (ω̃(u) 6= ω̃(v)) ≥ 1/2 − 1/ log2 m .
• For every set e ⊂ V of size at least 2,
Pr (ω̃(u) 6= ω̃(v) for some u, v ∈ e) ≤ O β −1
p
log n · log log m · max kϕ(ū) − ϕ(v̄)k2 .
u,v∈e
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 12
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
Proof. Let
log2 log2 m
K = max ,1 .
− log2 (1 − 4p)
We independently sample K assignments ω1 , . . . , ωK as described in Lemma 4.2. Let
ω̃(u) = ω1 (u) ⊕ · · · ⊕ ωK (u) ,
where ⊕ denotes addition modulo 2. Consider u and v such that kϕ(ū) − ϕ(v̄)k2 ≥ β . Let
p̃ = Pr (ωi (u) 6= ωi (v)) ≥ 2p for i ∈ {1, . . . , K}
(the expression does not depend on the value of i since all ωi are identically distributed). Note that
ω̃(u) 6= ω̃(v) if and only if ωi (u) 6= ωi (v) for an odd number of indices i. Therefore,
1 − (1 − 2 p̃)K
K
Pr (ω(u) 6= ω(v)) = ∑ p̃2k+1 (1 − p̃)K−2k−1 =
0≤k<K/2
2k + 1 2
1 − (1 − 4p)K 1 1
≥ ≥ − .
2 2 log2 m
Now let e ⊂ V be a subset of size at least 2. We have, by the union bound,
Pr (ω̃(u) 6= ω̃(v)) ≤ Pr (ωi (u) 6= ωi (v) for some i) ≤ O Kβ −1 log n max kϕ(ū) − ϕ(v̄)k2 .
p
u,v∈e
In the third step (step 3 of Algorithm 1), we generate “words” using the ω̃(·). This step is again
similar to one of the steps in the paper [8]. We present our complete algorithm for the hypergraph
orthogonal separator below, and we analyze our algorithm in Theorem 4.4.
Algorithm 1.
1. Set l = dlog2 m/(1 − log2 (1 + 2/ log2 m))e = log2 m + O(1).
2. Sample l independent assignments ω̃1 , . . . , ω̃l using Lemma 4.3.
3. For every vertex u, define word W (u) = (ω̃1 (u), . . . , ω̃l (u)) ∈ {0, 1}l .
4. If n ≥ 2l , pick a word W ∈ {0, 1}l uniformly at random. If n < 2l , pick a random word W ∈ {0, 1}l
so that PrW (W = W (u)) = 1/n for every u ∈ V . This is possible since the number of distinct words
constructed in step 3 is at most n (we may pick a word W not equal to any W (u)).
5. Pick r ∈ (0, 1) uniformly at random.
6. Let S = u ∈ V : kūk2 ≥ r and W (u) = W .
Theorem 4.4. Random set S is a hypergraph m-orthogonal separator with distortion
p m log m log log m
D=O log n × ,
β
probability scale α ≥ 1/n and separation threshold β .
Proof. We verify that S satisfies properties 1–3 in the definition of a hypergraph m-orthogonal separator
with α = max(1/2l , 1/n).
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 13
A NAND L OUIS AND Y URY M AKARYCHEV
Property 1. Let α = max(1/2l , 1/n). We compute the probability that u ∈ S. Observe that u ∈ S if
and only if W (u) = W and r ≤ kūk2 (these two events are independent). If n ≥ 2l , the probability that
W = W (u) is 1/2l since we choose W uniformly at random from {0, 1}l ; if n < 2l the probability is 1/n.
That is, Pr (W = W (u)) = max(1/2l , 1/n) = α. The probability that r ≤ kūk2 is kūk2 . We conclude that
property 1 holds.
Property 2. Consider two vertices u and v such that kū − v̄k2 ≥ β min(kūk2 , kv̄k2 ). Assume without
loss of generality that kūk2 ≤ kv̄k2 . Note that u, v ∈ S if and only if r ≤ kūk2 and W = W (u) = W (v). We
first upper bound the probability that W (u) = W (v). We have
2hū, v̄i = kūk2 + kv̄k2 − kū − v̄k2 ≤ (1 − β )kūk2 + kv̄k2 ≤ (2 − β )kv̄k2 .
Therefore, 2hū, v̄i/kv̄k2 ≤ 2 − β . Hence,
2hū, v̄i
kϕ(ū) − ϕ(v̄)k2 = 2 − 2hϕ(ū), ϕ(v̄)i = 2 − ≥β.
max(kūk2 , kv̄k2 )
From Lemma 4.3 we get that Pr (ω̃i (u) 6= ω̃i (v)) ≥ 1/2 − 1/log2 m for every i. The probability that
W (u) = W (v) is at most
l
1 1
+ ≤ 1/m .
2 log2 m
Therefore we have, as required,
Pr (u ∈ S, v ∈ S) = Pr r ≤ min(kūk2 , kv̄k2 ) × Pr (W = W (u) = W (v) | W (u) = W (v))
× Pr (W (u) = W (v)) ≤ min(kūk2 , kv̄k2 ) × α × (1/m) .
Property 3. Let e be an arbitrary subset of V , |e| ≥ 2. Let ρm = minw∈e kw̄k2 and ρM = maxw∈e kw̄k2 .
Note that
ρM − ρm = kw̄1 k2 − kw̄2 k2 ≤ kw̄1 − w̄2 k2 ≤ max kū − v̄k2 ,
u,v∈e
for some w1 ,w2 ∈ e. Here we used that SDP constraint (2.5) implies that kw̄1 k2 − kw̄2 k2 ≤ kw̄1 − w̄2 k2 .
Let A = u ∈ e : kūk2 ≥ r . We have S ∩ e = {u ∈ A : W (u) = W }. Therefore, if e is cut by S then
one of the following events happens.
• Event E1 : A 6= e and S ∩ e 6= ∅.
• Event E2 : A = e and A ∩ S 6= ∅, A ∩ S 6= A.
If E1 happens then r ∈ [ρm , ρM ] since A 6= e and A 6= ∅ (because A ⊃ S ∩ e 6= ∅). We have
Pr (E1 ) ≤ Pr (r ∈ (ρm , ρM ]) ≤ |ρM − ρm | ≤ max kū − v̄k2 .
u,v∈e
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 14
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
If E2 happens then (1) r ≤ ρm (since A = e) and (2) W (u) 6= W (v) for some u, v ∈ e. The probability
that r ≤ ρm is ρm . We now upper bound the probability that W (u) 6= W (v) for some u, v ∈ e. For each
i ∈ {1, . . . , l},
Pr (ω̃i (u) 6= ω̃i (v) for some u, v ∈ e) ≤ O β −1 log n · log log m max kϕ(ū) − ϕ(v̄)k2
p
u,v∈e
2kū − v̄k2
≤ O β −1 log n · log log m max
p
u,v∈e min(kūk2 , kv̄k2 )
≤ O β −1 log n · log log m × ρm−1 × max kū − v̄k2 .
p
u,v∈e
By the union bound over i ∈ {1, . . . , l}, the probability that W (u) 6= W (v) for some u, v ∈ e is at most
O l × β −1 log n · log log m × ρm−1 × max kū − v̄k2 .
p
u,v∈e
Therefore,
Pr (E2 ) ≤ ρm × O l × β −1 log n log log m × ρm−1 × max kū − v̄k2
p
u,v∈e
−1
p
log n log m log log m × max kū − v̄k2 .
≤O β
u,v∈e
We get that the probability that e is cut by S is at most
Pr (E1 ) + Pr (E2 ) ≤ O β −1 log n log m log log m × max kū − v̄k2 .
p
u,v∈e
√
For D = O(β −1 log n log m log log m)/α, we get Pr (e is cut by S) ≤ αD maxu,v∈e kū − v̄k2 . Note that
√
α ≥ 1/2l ≥ Ω(1/m). Thus D ≤ O(β −1 log n m log m log log m).
5 `2 –`22 hypergraph orthogonal separators
In this section, we present another variant of hypergraph orthogonal separators, which we call `2 –`22
hypergraph orthogonal separators. The advantage of `2 –`22 hypergraph orthogonal separators is that their
distortions do not depend on n (the number of vertices). Then in Section 6, we use `2 –`22 hypergraph
orthogonal separators to prove Theorem 6.3 (which, in turn, implies Theorem 1.4).
Definition 5.1 (`2 –`22 Hypergraph Orthogonal Separator). Let {ū : u ∈ V } be a set of vectors in the unit
ball. We say that a random set S ⊂ V is an `2 –`22 hypergraph m-orthogonal separator with `2 –distortion
D`2 : N → R, `22 –distortion D`2 , probability scale α > 0, and separation threshold β ∈ (0, 1) if it satisfies
2
the following properties.
1. For every u ∈ V , Pr(u ∈ S) = αkūk2 .
2. For every u and v such that kū − v̄k2 ≥ β min(kūk2 , kv̄k2 ),
min(kūk2 , kv̄k2 )
Pr (u ∈ S and v ∈ S) ≤ α .
m
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 15
A NAND L OUIS AND Y URY M AKARYCHEV
3. For every e ⊂ V ,
Pr (e is cut by S) ≤ αD`2 · max kū − v̄k2 + αD`2 (|e|) · min kw̄k · max kū − v̄k .
2 u,v∈e w∈e u,v∈e
(This definition differs from Definition 2.1 only in item 3.)
Theorem 5.2. There is a polynomial-time randomized algorithm that given a set of vertices V , a set
of vectors {ū} and parameters m and β generates an `2 –`22 hypergraph m-orthogonal separator with
probability scale α ≥ 1/n and distortions:
D`2 (r) = O(β −1/2 log r m log m log log m).
p
D`2 = O(m) and
2
Note that distortions D`2 and D`2 do not depend on n.
2
The algorithm and its analysis are very similar to those in the proof of Theorem 2.2. The only
difference is that we use another procedure to generate random assignments ω : V → {0, 1}. The
following lemma is an analog of Lemma 4.2.
Lemma 5.3. There is a randomized polynomial time algorithm that given a finite set V , vectors ϕ(ū)
for u ∈ V , and a parameter β ∈ (0, 1), returns a random assignment ω : V → {0, 1} that satisfies the
following properties.
• For every set e ⊂ V of size at least 2,
Pr (ω(u) 6= ω(v) for some u, v ∈ e) ≤ O β −1/2
p
log |e| × max kϕ(ū) − ϕ(v̄)k .
u,v∈e
• For every u and v such that kϕ(ū) − ϕ(v̄)k2 ≥ β ,
Pr (ω(u) 6= ω(v)) ≥ 0.3 .
Proof. We sample a random Gaussian vector g ∼ N(0, In ) (each component gi of g is distributed as
N(0, 1), all random variables gi are independent). Let N be a Poisson process on R with rate 1/ β . Let
p
w(u) = 1 if N(hg, ϕ(ū)i) is even, and w(u) = 0 if N(hg, ϕ(ū)i) is odd. Note that ω(u) = ω(v) if and only
if N(hg, ϕ(ū)i) − N(hg, ϕ(v̄)i) is even.
Consider a set e ⊂ V of size at least 2. Denote diam(e) = maxu,v∈e kϕ(ū) − ϕ(v̄)k. Let
τm = minhg, ϕ(w̄)i and τM = maxhg, ϕ(w̄)i .
w∈e w∈e
Note that
N(τm ) = min N(hg, ϕ(w̄)i) and N(τM ) = max N(hg, ϕ(w̄)i) .
w∈e w∈e
If all numbers N(hg, ϕ(ū)i) (for u ∈ e) are equal then ω(u) = ω(v) for all u, v ∈ e. Thus if ω(u) 6= ω(v) for
some u, v ∈ e then N(hg, ϕ(ū)i) 6= N(hg, ϕ(v̄)i) for some u, v ∈ e. In particular,
p then N(τM ) − N(τm ) > 0.
Given g, N(τM ) − N(τm ) is a Poisson random variable with rate (τM − τm )/ β . We have
Pr (ω(u) 6= ω(v) for some u, v ∈ e | g) ≤ Pr (N(τM ) − N(τm ) > 0 | g)
√
= 1 − e−(τM −τm )/ β ≤ β −1/2 (τM − τm ) .
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 16
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
Let ξuv = hg, ϕ(ū)i − hg, ϕ(v̄)i for u, v ∈ e (u 6= v). Note that ξuv are Gaussian random variables with
mean 0, and
Var[ξuv ] = Var[hg, ϕ(ū)i − hg, ϕ(v̄)i] = kϕ(ū) − ϕ(v̄)k2 ≤ diam(e)2 .
The expectation of the maximum of (not necessarily independent) N Gaussian random variables with
√
standard deviation bounded by σ is O( log Nσ ). We have
p p
E [τM − τm ] = E max(ξuv ) = O log(|e|(|e| − 1)) diam(e) = O log |e| diam(e)
u,v∈e
since the total number of random variables ξuv is |e|(|e| − 1). Therefore,
Pr (ω(u) 6= ω(v) for some u, v ∈ e) ≤ β −1/2 E [τM − τm ] = O β −1/2 log |e| max kϕ(ū) − ϕ(v̄)k .
p
u,v∈e
We proved that ω satisfies the first property. Now we verify that ω satisfies the second property. Consider
two vertices u and v with kϕ(ū) − ϕ(v̄)k2 ≥ β . Given g, the random variable
Z = N(hg, ϕ(ū)i) − N(hg, ϕ(v̄)i)
p
has Poisson distribution with rate λ = |hg, ϕ(ū)i − hg, ϕ(v̄)i|/ β . We have
∞ ∞
e−λ λ 2k 1 + e−2λ
Pr (Z is even | g) = ∑ Pr (Z = 2k | g) = ∑ = .
k=0 k=0 (2k)! 2
Note that λ is the absolute value of a Gaussian random variable with mean 0 and standard deviation
σ = kϕ(ū) − ϕ(v̄)k/ β ≥ 1. Thus Pr (Z is even) = E 1 + e−2σ |γ| /2, where γ is a standard Gaussian
p
random variable, γ ∼ N(0, 1). We have
" # " #
1 − e−2σ |γ| 1 − e−2|γ|
Pr (ω(u) 6= ω(v)) = E ≥E ≥ 0.3 .
2 2
Now we use the algorithm from Theorem 2.2 to obtain `2 –`22 hypergraph orthogonal separators. The
only difference is that we use the procedure from Lemma 5.3 rather than from Lemma 4.2 to generate
assignments ω.
Theorem 5.4. Random set S is an `2 –`22 hypergraph m-orthogonal separator with distortions
D`2 (r) = O β −1/2 log r m log m log log m ,
p
D`2 = O(m) and
2
probability scale α ≥ 1/n and separation threshold β ∈ (0, 1).
Proof. The proof of the theorem is almost identical to that of Theorem 4.4. We first check conditions 1
and 2 of `2 –`22 hypergraph orthogonal separators in the same way as we checked conditions 1 and 2 of
hypergraph orthogonal separators in Theorem 4.4. When we verify that property 3 holds, we use bounds
from Lemma 5.3. The only difference is how we upper bound the probability of the event E2 . Recall that
E2 is the event that
A = e , A ∩ S 6= ∅ , and A ∩ S 6= A .
We let ρm = minw∈e kw̄k2 as in Theorem 4.4. If E2 happens then
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 17
A NAND L OUIS AND Y URY M AKARYCHEV
1. r ≤ ρm since A = e, and
2. W (u) 6= W (v) for some u, v ∈ e.
The probability that r ≤ ρm is ρm . We upper bound the probability that W (u) 6= W (v) for some u, v ∈ e.
For each i ∈ {1, . . . , l},
Pr (ω̃i (u) 6= ω̃i (v) for some u, v ∈ e) ≤ O β −1/2 log |e| log log m max kϕ(ū) − ϕ(v̄)k
p
u,v∈e
kū − v̄k
≤ O β −1/2 log |e| log log m max
p
u,v∈e min(kūk, kv̄k)
−1/2 −1/2
p
≤O β log |e| log log m × ρm × max kū − v̄k.
u,v∈e
By the union bound over i ∈ {1, . . . , l}, the probability that W (u) 6= W (v) for some u, v ∈ e is at most
−1/2
O l × β −1/2 log |e| log log m × ρm × max kū − v̄k .
p
u,v∈e
Therefore,
−1/2
Pr (E2 ) ≤ ρm × O l × β −1/2 log |e| log log m × ρm × max kū − v̄k
p
u,v∈e
1/2
≤ O l × β −1/2 log |e| log log m × ρm × max kū − v̄k .
p
u,v∈e
We get that the probability that e is cut by S is at most
1/2
Pr (E1 ) + Pr (E2 ) ≤ max kū − v̄k2 + O l × β −1/2
p
log |e| log log m ρm max kū − v̄k
u,v∈e u,v∈e
−1/2
2
p
≤ max kū − v̄k + O l × β log |e| log log m min kw̄k max kū − v̄k.
u,v∈e w∈e u,v∈e
√
For D`2 = 1/α and D`2 (r) = O β −1/2 log r log m log log m /α, we get
2
Pr (e is cut by S) ≤ αD`2 · max kū − v̄k2 + αD`2 (|e|) · min kw̄k · max kū − v̄k .
2 u,v∈e w∈e u,v∈e
Note that α ≥ 1/2l ≥ Ω(1/m). Thus
D`2 (r) = O β −1/2
p
D`2 = O(m) and log r m log m log log m .
2
6 Algorithm for Hypergraph Small-Set Expansion via `2 –`22 hypergraph
orthogonal separators
In this section, we present another algorithm
q for Hypergraph Small-Set Expansion. The algorithm finds a
∗
set with expansion proportional to φG,δ . The proportionality constant depends on degrees of vertices
and hyperedge size but not on the graph size. Here, we present our result for arbitrary hypergraphs. The
result for uniform hypergraphs (Theorem 1.4) stated in the Introduction follows from our general result.
In order to state our result for arbitrary graphs, we need the following definition.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 18
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
Definition 6.1. Consider a hypergraph H = (V, E). Suppose that for every edge e we are given a
non-empty subset e◦ ⊆ e. Let
log2 |e|
η(u) = ∑ ◦
and ηmax = max η(u) .
e:u∈e◦ |e | u∈V
H be the minimum of η
Finally, let ηmax ◦
max over all possible choices of subsets e .
Claim 6.2.
H
1. ηmax ≤ max ∑ (log2 |e|)/|e|.
u∈V e:u∈e
H ≤ (d
2. If H is an r-uniform graph with maximum degree dmax then ηmax max log2 r)/r.
3. Suppose that we can choose one vertex in every edge so that no vertex is chosen more than once.
H ≤ log r
Then ηmax 2 max , where rmax is the size of the largest hyperedge in H.
Proof.
1. Let e◦ = e for every e ∈ E. We have ηmax
H ≤ max
u∈V ∑e:u∈e (log2 |e|)/|e|.
2. By item 1,
H
ηmax ≤ max ∑ (log2 |e|)/|e| = max ∑ (log2 r)/r = (dmax log2 r)/r .
u∈V e:u∈e u∈V e:u∈e
3. For every edge e ∈ E, let e◦ be the set that contains the vertex chosen for e. Then |e◦ | = 1 and
|{e : u ∈ e◦ }| ≤ 1 for every u. We have
H log2 |e| log2 rmax
ηmax ≤ max ∑ ◦
≤ max ∑ = log2 rmax .
u∈V e:u∈e◦ |e | u∈V e:u∈e◦ 1
Theorem 6.3. There is a randomized polynomial-time algorithm for the Hypergraph Small-Set Expansion
problem that given a hypergraph H = (V, E), and parameters ε ∈ (0, 1) and δ ∈ (0, 1/2], finds a set
S ⊂ V of size at most (1 + ε)δ n such that
q
φ (S) ≤ Oε δ −1 log δ −1 log log δ −1 ηmaxH · φ ∗ + δ −1 φ ∗
H,δ H,δ
q
=O eε δ −1 H φ∗ +φ∗
ηmax .
H,δ H,δ
In particular, if H is an r-uniform hypergraph with maximum degree dmax , then we have
r !!
eε δ −1 log 2 r ∗ +φ∗
φ (S) ≤ O dmax φH,δ H,δ .
r
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 19
A NAND L OUIS AND Y URY M AKARYCHEV
Proof. The proof is similar to that of Theorem 3.1. We solve the SDP relaxation for H-SSE and obtain an
SDP solution {ū}. Denote the SDP value by sdpcost. Consider an `2 –`22 hypergraph orthogonal separator
S with m = 4/(εδ ) and β = ε/4. Define a set S0 :
(
0 S, if |S| ≤ (1 + ε)δ n,
S =
∅, otherwise.
Clearly, |S0 | ≤ (1 + ε)δ n. As in the proof of Theorem 3.1,
Pr(u ∈ S0 ) ∈ (α/2) kūk2 , αkūk2 .
Note that
Pr S0 cuts edge e ≤ Pr (S cuts edge e) ≤ αD`2 max kū − v̄k2 + αD`2 (r) min kw̄k max kū − v̄k .
u,v∈e w∈e u,v∈e
Let C = α −1 E [|Ecut (S0 )|]. Let
|Ecut (S0 )|
Z = |S0 | − .
4C
We have
|Ecut (S0 )|
α α α α α
E [Z] = E |S0 | − E ≥ ∑ · kūk2 − = − = .
4C u∈V 2 4 2 4 4
Now we upper bound C. Consider the optimal choice of e◦ for H in the definition of ηmax
H .
C = α −1 E |Ecut (S0 )| ≤ α −1 ∑ Pr (e is cut by S)
e∈E
≤ D`2 ∑ max kū − v̄k2 + ∑ D`2 (|e|) min kw̄k max kū − v̄k
2 u,v∈e w∈e u,v∈e
e∈E e∈E
kw̄k
≤ D`2 · sdpcost + ∑ D`2 (|e|) ∑ × max kū − v̄k
2
e∈E w∈e◦ |e◦ | u,v∈e
D`2 (|e|)kw̄k maxu,v∈e kū − v̄k
≤ D`2 · sdpcost + ∑ ∑ p × p
2
e∈E w∈e◦ |e◦ | |e◦ |
s s
D`2 (|e|)2 kw̄k2 maxu,v∈e kū − v̄k2
≤ D`2 · sdpcost + ∑ ∑ ∑ ∑ (6.1)
2
e∈E w∈e◦ |e◦ | e∈E w∈e◦ |e◦ |
s
D`2 (|e|)2 p
≤ D`2 · sdpcost + ∑ kw̄k2 ∑ sdpcost ,
2
w∈V e:w∈e◦ |e◦ |
where the inequality of line (6.1) follows from Cauchy–Schwarz. For every vertex w,
D`2 (|e|)2 log2 |e|
∑ ◦|
≤ Oβ (m log m log log m)2 ∑ ◦|
≤ Oβ (m log m log log m)2 × ηmax
H
e:w∈e◦ |e e:w∈e◦ |e
and
∑ kw̄k2 = 1.
w∈V
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 20
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
Therefore, q
C ≤ Oβ msdpcost + m log m log log m ηmax
H · sdpcost .
By the argument from Theorem 3.1, we get that if we sample S0 sufficiently many times (i. e., (4n2 /α)
times), we will find a set S0 such that
|Ecut (S0 )|
q
−1 −1 −1 H −1
≤ 4C ≤ Oβ δ log δ log log δ ηmax · sdpcost + δ sdpcost
|S0 |
with probability exponentially close to 1.
7 SDP integrality gap
In this section, we present an integrality gap for the SDP relaxation for H-SSE. We also give a lower
bound on the distortion of a hypergraph m-orthogonal separator.
Theorem 7.1. For δ = 1/r, the integrality gap of the SDP for H-SSE is at least 1/(2δ ) = r/2.
Proof. Consider a hypergraph H = (V, E) on n = r vertices with one hyperedge e = V (e contains all
vertices). Note that the expansion of every set of size δ n = 1 is 1. Thus φH,δ ∗ = 1.
√
Consider an SDP solution that assigns vertices mutually orthogonal vectors of length 1/ r. It is easy
to see this is a feasible SDP solution. Its value is maxu,v∈e kū − v̄k2 = 2/r. Therefore, the SDP integrality
gap is at least r/2.
Now we give a lower bound on the distortion of hypergraph m-orthogonal separators.
Lemma 7.2. For every m > 4, there is an SDP solution such that every hypergraph m-orthogonal
separator with separation threshold β < 2 has distortion at least dme/4.
Proof. Consider the SDP solution from Theorem 7.1 for n = r = dme. Consider a hypergraph m-
orthogonal separator S for this solution. Let D be its distortion. Note that condition (2) from the definition
of hypergraph orthogonal separators applies to any pair of distinct vertices (u, v) since kū − v̄k2 = 2kuk2 =
2kvk2 .
By the inclusion–exclusion principle, we have
1
Pr (|S| = 1) ≥ ∑ Pr (u ∈ S) − ∑ Pr (u ∈ S, v ∈ S)
u∈S 2 u,v∈S,u6 =v
1 α min(kūk2 , kv̄k2 ) αn(n − 1)
≥ ∑ αkūk2 − ∑ =α− ≥ α/2 .
u∈S 2 u,v∈S,u6=v m 2mr
On the other hand, if |S| = 1 then S cuts e. We have
Pr (|S| = 1) ≤ Pr (S cuts e) ≤ αD max kū − v̄k2 = 2αD/r .
u,v∈e
We get that α/2 ≤ 2αD/r and thus D ≥ r/4 = dme/4.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 21
A NAND L OUIS AND Y URY M AKARYCHEV
8 Reduction from Vertex Expansion to Hypergraph Expansion
In the reduction from vertex expansion to hypergraph expansion, we will use the notion of Symmetric
Vertex Expansion. For a graph G = (V, E) and set S ⊂ V , we define its outer neighborhood N(S) as
follows.
N(S) = {u ∈ S̄ : ∃ v ∈ S such that {u, v} ∈ E} .
The symmetric vertex expansion of a set, denoted by ΦV (S), is defined as
|N(S̄) ∪ N(S)|
ΦV (S) = and ΦVG,δ = min ΦV (S) .
min(|S|, |S̄|) S⊂V
0<|S|≤δ n
We will use the following reduction from vertex expansion to symmetric vertex expansion.
Theorem 8.1 (Louis, Raghavendra, and Vempala [20]). Given a graph G, there exists a graph G0 such
that
V
c1 φG,δ ≤ ΦVG0 ,δ ≤ c2 φG,δ
V
where c1 , c2 > 0 are absolute constants, and the maximum degree of graph G0 is equal to the maximum
degree of graph G. Moreover, there exists a polynomial time algorithm to compute such graph G0 .
The following result is a detailed version of the informal Theorem 1.6 stated in the Introduction.
Theorem 8.2 (“Graph to Hypergraph Theorem,” detailed statement). There exist absolute constants
c1 , c2 ∈ R+ such that for every graph G = (V, E), there exists a polynomial-time computable hypergraph
H = (V 0 , E 0 ) such that c1 φH,δ
∗ ≤ φ V ≤ c φ ∗ . Also, for the hypergraph H, we have η H ≤ log (d
G,δ 2 H,δ max 2 max +
H
1), where ηmax is defined in Definition 6.1 and dmax is the maximum degree of G.
Proof. Starting with graph G, we use Theorem 8.1 to obtain a graph G0 = (V 0 , E 0 ) such that
V
c1 φG,δ ≤ ΦVG0 ,δ ≤ c2 φG,δ
V
.
Next we construct hypergraph H = (V 0 , E 00 ): for every vertex v ∈ V 0 , we add the hyperedge {v} ∪ N({v})
to E 00 (note that N({v}) is the set of neighbors of v in G).
Fix an arbitrary set S ⊂ V . We first show that ΦV (S) ≤ φH (S). Consider the set of vertices N(S̄).
Each vertex in v ∈ N(S̄) has a neighbor, say u, in S̄. Therefore the hyperedge {v} ∪ N({v}) is cut by S in
H. Similarly, for each vertex v ∈ N(S), the hyperedge {v} ∪ N({v}) is cut by S in H. Therefore,
N(S̄) + |N(S)| |Ecut (S)|
ΦV (S) ≤ = ≤ φH (S) .
|S| |S|
Now we verify that φH (S) ≤ ΦV (S). For any hyperedge ({v} ∪ N({v})) ∈ Ecut (S), the vertex v has to
belong to either N(S̄) or N(S). Therefore,
|Ecut (S)| N(S̄) + |N(S)|
φH (S) ≤ ≤ = ΦV (S) .
|S| |S|
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 22
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
∗ = ΦV . Therefore, by Theorem 8.1,
Thus we get that φH (S) = ΦV (S) for every S ⊂ V , and hence φH,δ G0 ,δ
V ∗ V
c1 φG,δ ≤ φH,δ ≤ c2 φG,δ .
H . We use part 3 of Claim 6.2. We choose vertex v in the hyperedge
Finally, we upper bound ηmax
H
{v} ∪ N({v}). By Claim 6.2, ηmax ≤ log2 rmax , where rmax is the size of the largest hyperedge. Note that
| {v} ∪ N({v})| = deg v + 1. Thus
H
ηmax ≤ log2 rmax ≤ log2 (dmax + 1) .
References
[1] A MIT AGARWAL , M OSES C HARIKAR , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV:
√
O( log n) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems.
In Proc. 37th STOC, pp. 573–581. ACM Press, 2005. [doi:10.1145/1060590.1060675] 5
[2] S ANJEEV A RORA AND RONG G E: New tools for graph coloring. In Proc. 14th Internat. Workshop
on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’11), pp. 1–12.
Springer, 2011. [doi:10.1007/978-3-642-22935-0_1] 4
[3] S ANJEEV A RORA , JAMES L EE , AND A SSAF NAOR: Euclidean distortion and the sparsest cut. J.
Amer. Math. Soc., 21(1):1–21, 2008. Preliminary version in STOC’05. [doi:10.1090/S0894-0347-
07-00573-5, arXiv:math/0508154] 11
[4] S ANJEEV A RORA , S ATISH R AO , AND U MESH VAZIRANI: Expander flows, geometric embed-
dings and graph partitioning. J. ACM, 56(2):5:1–5:37, 2009. Preliminary version in STOC’04.
[doi:10.1145/1502793.1502794] 11
[5] N IKHIL BANSAL , U RIEL F EIGE , ROBERT K RAUTHGAMER , KONSTANTIN M AKARYCHEV,
V ISWANATH NAGARAJAN , J OSEPH NAOR , AND ROY S CHWARTZ: Min-Max graph partition-
ing and small set expansion. SIAM J. Comput., 43(2):872–904, 2014. Preliminary version in
FOCS’11. [doi:10.1137/120873996, arXiv:1110.4319] 3, 4, 5, 6, 7, 8, 9
[6] Ü MIT V. Ç ATALYÜREK AND C EVDET AYKANAT: Hypergraph-partitioning-based decomposition
for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel and Distr. Systems, 10(7):673–
693, 1999. Preliminary version in STOC’15. [doi:10.1109/71.780863, arXiv:1510.01520] 2
[7] T-H. H UBERT C HAN , A NAND L OUIS , Z HIHAO G AVIN TANG , AND C HENZI Z HANG: Spectral
properties of hypergraph laplacian and approximation algorithms, 2016. [arXiv:1605.01483] 3
[8] E DEN C HLAMTÁČ , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: How to play
unique games using embeddings. In Proc. 47th FOCS, pp. 687–696. IEEE Comp. Soc. Press, 2006.
[doi:10.1109/FOCS.2006.36] 6, 8, 11, 13
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 23
A NAND L OUIS AND Y URY M AKARYCHEV
[9] J ULIA C HUZHOY, Y URY M AKARYCHEV, A RAVINDAN V IJAYARAGHAVAN , AND Y UAN Z HOU:
Approximation algorithms and hardness of the k-route cut problem. ACM Trans. Algorithms,
12(1):2:1–2:40, 2016. Preliminary version in SODA’12. [doi:10.1145/2644814, arXiv:1112.3611] 5
[10] K AREN D. D EVINE , E RIK G. B OMAN , ROBERT T. H EAPHY, ROB H. B ISSELING , AND Ü MIT V.
Ç ATALYÜREK: Parallel hypergraph partitioning for scientific computing. In Proc. 20th Internat
Parallel and Distr. Processing Symp. (IPDPS’06), 2006. [doi:10.1109/IPDPS.2006.1639359] 2
[11] S HAI E VRA AND TALI K AUFMAN: Bounded degree cosystolic expanders of every dimension. In
Proc. 48th STOC, pp. 36–48. ACM Press, 2016. [doi:10.1145/2897518.2897543, arXiv:1510.00839]
5
[12] U RIEL F EIGE , M OHAMMAD TAGHI H AJIAGHAYI , AND JAMES R. L EE: Improved approxima-
tion algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629–657, 2008.
Preliminary version in STOC’05. [doi:10.1137/05064299X] 5
[13] G EORGE K ARYPIS , R AJAT AGGARWAL , V IPIN K UMAR , AND S HASHI S HEKHAR: Multilevel
hypergraph partitioning: applications in VLSI domain. IEEE Trans. Very Large Scale Integration
(VLSI) Systems, 7(1):69–79, 1999. Preliminary version in DAC’97. [doi:10.1109/92.748202] 2
[14] TALI K AUFMAN , DAVID K AZHDAN , AND A LEXANDER L UBOTZKY: Ramanujan complexes and
bounded degree topological expanders. In Proc. 55th FOCS, pp. 484–493. IEEE Comp. Soc. Press,
2014. [doi:10.1109/FOCS.2014.58] 5
[15] NATHAN L INIAL AND ROY M ESHULAM: Homological connectivity of random 2-complexes.
Combinatorica, 26(4):475–487, 2006. [doi:10.1007/s00493-006-0027-9] 5
[16] A NAND L OUIS: Hypergraph Markov operators, eigenvalues and approximation algorithms. In Proc.
47th STOC, pp. 713–722. ACM Press, 2015. [doi:10.1145/2746539.2746555, arXiv:1408.2425] 3
[17] A NAND L OUIS AND KONSTANTIN M AKARYCHEV: Approximation algorithm for sparsest k-
partitioning. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1244–
1255. ACM Press, 2014. [doi:10.1137/1.9781611973402.92, arXiv:1306.4384] 7, 8
[18] A NAND L OUIS AND Y URY M AKARYCHEV: Approximation algorithms for hypergraph small set
expansion and small set vertex expansion. In Proc. 17th Internat. Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX’14), pp. 339–355. Springer, 2014.
[doi:10.4230/LIPIcs.APPROX-RANDOM.2014.339, arXiv:1404.4575] 1
[19] A NAND L OUIS , P RASAD R AGHAVENDRA , AND S ANTOSH V EMPALA: Private Communication,
2012. 4
[20] A NAND L OUIS , P RASAD R AGHAVENDRA , AND S ANTOSH V EMPALA: The complexity of ap-
proximating vertex expansion. In Proc. 54th FOCS, pp. 360–369. IEEE Comp. Soc. Press, 2013.
[doi:10.1109/FOCS.2013.46, arXiv:1304.3139] 5, 22
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 24
A PPROXIMATION A LGORITHMS FOR H-SSE AND SSVE
[21] KONSTANTIN M AKARYCHEV AND Y URY M AKARYCHEV: Nonuniform graph partitioning with
unrelated weights. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming
(ICALP’14), pp. 812–822. Springer, 2014. [doi:10.1007/978-3-662-43948-7_67, arXiv:1401.0699]
8, 9
[22] P RASAD R AGHAVENDRA AND DAVID S TEURER: Graph expansion and the unique games con-
jecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]
3
[23] P RASAD R AGHAVENDRA , DAVID S TEURER , AND P RASAD T ETALI: Approximations for the
isoperimetric and spectral profile of graphs and related parameters. In Proc. 42nd STOC, pp.
631–640. ACM Press, 2010. [doi:10.1145/1806689.1806776] 3, 4, 7
AUTHORS
Anand Louis
Assistant Professor
Department of Computer Science and Automation
Indian Institute of Science
Bengaluru
anand csa iisc ernet in
http://drona.csa.iisc.ernet.in/~anand/
Yury Makarychev
Associate Professor
Toyota Technological Institute at Chicago
Chicago, IL
yury ttic edu
http://ttic.uchicago.edu/~yury/
ABOUT THE AUTHORS
A NAND L OUIS is an Assistant Professor in the Department of Computer Science and
Automation at the Indian Institute of Science, Bengaluru. He received his Ph. D. from
Georgia Tech under the supervision of Santosh Vempala in 2014. Subsequently he was
a postdoctoral research associate in the Department of Computer Science at Princeton
University for two years.
Y URY M AKARYCHEV is an Associate Professor at the Toyota Technological Institute at
Chicago. He received his Ph. D. from Princeton University under the supervision of
Moses Charikar in 2008. Yury did a postdoctoral fellowship at Microsoft Research and
then joined TTIC in 2009.
T HEORY OF C OMPUTING, Volume 12 (17), 2016, pp. 1–25 25