Vertex Sparsifiers and Abstract Rounding Algorithms

Introduction

The notion of vertex sparsification (in particular cut-sparsification) is introduced in : Given a graph $G=(V,E)$ and a subset of terminals $K\subset V$, the goal is to construct a graph $H=(K,E_{H})$ on just the terminal set so that simultaneously for all cuts $(A,K-A)$, the value of the minimum cut in $G$ separating $A$ from $K-A$ is approximately the same as the value of the corresponding cut in $H$. If for all cuts $(A,K-A)$, the the value of the cut in $H$ is at least the value of the corresponding minimum cut in $G$ and is at most $\alpha$ times this value, then we call $H$ a cut-sparsifier of quality $\alpha$.

The motivation for considering such questions is in obtaining approximation algorithms with guarantees that are independent of the size of the graph. For many graph partitioning and multicommodity flow questions, the value of the optimum solution can be approximated given just the values of the minimum cut separating $A$ from $K-A$ in $G$ (for every $A\subset K$). As a result the value of the optimum solution is approximately preserved, when mapping the optimization problem to $H$. So approximation algorithms can be run on $H$ as a proxy for running directly on $G$, and because the size (number of nodes) of $H$ is $|K|$, any approximation algorithm that achieves a $poly(\log|V|)$-approximation guarantee in general will achieve a $poly(\log|K|)$ approximation guarantee when run on $H$ (provided that the quality $\alpha$ is also $poly(\log|K|)$). Feasible solutions in $H$ can also be mapped back to feasible solutions in $G$ for many of these problems, so polynomial time constructions for good cut-sparsifiers yield black box techniques for designing approximation algorithms with guarantees $poly(\log|K|)$ (and independent of the size of the graph).

In addition to being useful for designing approximation algorithms with improved guarantees, the notion of cut-sparsification is also a natural generalization of many methods in combinatorial optimization that attempt to preserve certain cuts in $G$ (as opposed to all minimum cuts) in a smaller graph $H$ - for example Gomory-Hu Trees, and Mader’s Theorem. Here we consider a number of questions related to cut-sparsification:

Is there a super-constant lower bound on the quality of cut-sparsifiers? Do the best (or even near-best) cut-sparsifiers necessarily result from (a distribution on) contractions?

Do we really need to pay a price (in the approximation guarantee) when applying vertex sparsification to an optimization problem?

Can we construct (in polynomial time) cut-sparsifiers with quality as good as the current best existential results?

We resolve all of these questions in this paper. In the preceding subsections, we will describe what is currently known about each of these questions, our results, and our techniques. Recently, it has come to our attention that, independent of and concurrent to our work, Makarychev and Makarychev, and independently, Englert, Gupta, Krauthgamer, Raecke, Talgam and Talwar obtained results similar to some in this paper.

2 Super-Constant Lower Bounds and Separations

In , it is proven that in general there are always cut-sparsifiers $H$ of quality at most $O(\log k/\log\log k)$. In fact, if $G$ excludes any fixed minor then this bound improves to $O(1)$. Yet prior to this work, no super-constant lower bound was known for the quality of cut-sparsifiers in general. We prove

There is an infinite family of graphs that admits no cut-sparsifiers of quality better than $\Omega(\log^{1/4}k)$.

Some results are known in more general settings. In particular, one could require that the graph $H$ not only approximately preserve minimum cuts but also approximately preserve the congestion of all multicommodity flows (with demands endpoints restricted to be in the terminal set). This notion of vertex-sparsification is referred to as flow-sparsification (see ) and admits a similar definition of quality. gives a lower bound of $\Omega(\log\log k)$ for the quality of flow-sparsifiers. However, this does not apply to cut sparsifiers and in fact, for the example given in , there is an $O(1)$-quality cut-sparsifier!

Additionally, there are examples in which cuts can be preserved within a constant factor, yet flows cannot: Benczur and Karger proved that given any graph on $n$ nodes, there is a sparse (weighted) graph $G^{\prime}$ that approximate all cuts in $G$ within a multiplicative $(1+\epsilon)$ factor, but one provably cannot preserve the congestion of all multicommodity flows within a factor better than $\Omega(\frac{\log n}{\log\log n})$ on a sparse graph (consider the complete graph $K_{n}$). So here the limits of sparsification are much different for cuts than for flows.

In this paper, we give a super-constant lower bound on the quality of cut-sparsifiers in general and in fact this implies a stronger lower bound than is given in . Our bound is polynomially related to the current best upper-bound, which is $O(\log k/\log\log k)$.

We note that the current best upper bound is actually a reduction from the upper bound on the integrality gap of a particular LP relaxation for the -extension problem , . The integrality gap of this LP relaxation is known to be $\Omega(\sqrt{\log k})$. Yet, the best lower bound we are able to obtain here is $\Omega(\log^{1/4}k)$. This leads us to our next question: Do integrality gaps for the -extension LP immediately imply lower bounds for cut-sparsification? This question, as we will see, is essentially equivalent to the question of whether or not the best cut-sparsifiers necessarily come from a distribution on contractions.

Lower bounds on the quality of cut-sparsifiers (in this paper) and flow-sparsifiers () are substantially more complicated than integrality gap examples for the -extension LP relaxation. If the best cut-sparsifiers or flow-sparsifiers were actually always generated from some distribution on contractions in the original graph via strong duality (see Section $3$), any integrality gap would immediately imply a lower bound for cut-sparsificatin or flow-sparsification. But as we demonstrate here, this is not the case:

There is an infinite family of graphs so that the ratio of the best quality cut-sparsifier to the best quality cut-sparsifier that can be achieved through a distribution on contractions is $o(1)=O(\frac{\log\log\log\log k}{\log^{2}\log\log k})$

We also note that in order to prove this result we establish a somewhat surprising connection between cut-sparsification and the harmonic analysis of Boolean functions. The particular cut-sparsifier that we construct in order to prove this result is inspired by the noise stability operator, and as a result, we can use tools from harmonic analysis (Bourgain’s Junta Theorem and the Hypercontractive Inequality , ) to analyze the quality of the cut-sparsifier. Casting this question of bounding the quality as a question in harmonic analysis allows us to reason about many cuts simultaneously without worrying about the messy details of the combinatorics.

3 Abstract Integrality Gaps and Rounding Algorithms

As described earlier, running an approximation algorithm on the sparsifier $H=(K,E_{H})$ as a proxy for the graph $G=(V,E)$ pays an additional price in the approximation guarantee that corresponds to how well $H$ approximates $G$. Here we consider the question of whether this loss can be avoided.

As a motivating example, consider the problem of Steiner oblivious routing . Previous techniques for constructing Steiner oblivious routing schemes , first construct a flow-sparsifier $H$ for $G$, construct an oblivious routing scheme in $H$ and then map this back to a Steiner oblivious routing scheme in $G$. Any such approach must pay a price in the competitive ratio, and cannot achieve an $O(\log k)$-competitive guarantee because (for example) expanders do not admit constant factor flow-sparsifiers .

So black box reductions pay a price in the competitive ratio, yet here we present a technique for combining the flow-sparsification techniques in and the oblivious routing constructions in into a single step, and we prove that there are $O(\log k)$-competitive Steiner oblivious routing schemes, which is optimal. This result is a corollary of a more general idea:

The constructions of flow-sparsifiers given in (which is an extension of the techniques in ) can be regarded as a dual to the rounding algorithm in for the -extension problem. What we observe here is: Suppose we are given a rounding algorithm that is used to round the fractional solution of some relaxation to an integral solution for some optimization problem. If this rounding algorithm also works for the relaxation for the -extension problem given in (and also used in , ), then we can use the techniques in , to obtain stronger flow-sparsifiers which are not only good quality flow-sparsifiers, but also for which the optimization problem is easy. So in this way we do not need to pay an additional price in the approximation guarantee in order to replace the dependence on $n$ with a dependence on $k$. With these ideas in mind, what we observe is that the rounding algorithm in wh ich embed s metric spaces into distributions on dominating tree-metrics, can also be used to round the -extension relaxation. This allows us to construct flow-sparsifiers that have $O(\log k)$-quality, and also can be explicitly written as a convex combination of -extensions that are tree-like. On trees, oblivious routing is easy, and so this gives us a way to simultaneously construct good flow-sparsifiers and good oblivious routing schemes on the sparsifier in one step!

Of course, the rounding algorithm in for embedding metric spaces into distributions on dominating tree-metrics is a very common first step in rounding fractional relaxations of graph partitioning, graph layout and clustering problems. So for all problems that use this embedding as the main step, we are able to replace the dependence on $n$ with dependence on $k$, and we do not introduce any additional poly-logarithmic factors as in previous work! One can also interpret our result as giving a generalization of the hierarchical decompositions given in for approximating the cuts in a graph $G$ on trees. We state our results more formally, below, and we refer to such a statement as an Abstract Integrality Gap.

We call a fractional packing problem $P$ a graph packing problem if the goal of the dual covering problem $D$ is to minimize the ratio of the total units of distance $\times$ capacity allocated in the graph divided by some monotone increasing function of the distances between terminals.

This definition is quite general, and captures maximum concurrent flow, maximum multiflow, and multicast routing as special cases, in addition to many other common optimization problems. The integralThe notion of what constitutes an integral solution depends on the problem. In some cases, it translates to the distances are all or $1$, and in other cases it can mean something else. The important point is that the notion of integral just defines a class of admissible metrics, as opposed to arbitrary metrics which can arise in the packing problem. dual $ID$ problems are generalized sparsest cut, multicut and requirement cut respectively.

For any graph packing problem $P$, the maximum ratio of the integral dual to the fractional primal is at most $O(\log k)$ times the maximum ratio restricted to trees.

For a packing problem that fits into this class, this theorem allows us to reduce bounding the integrality gap in general graphs to bounding the integrality gap on trees, which is often substantially easier than for general graphs (i.e. for the example problems given above). We believe that this result helps to explain the intrinsic robustness of fractional packing problems into undirected graphs, in particular the ubiquity of the $O(\log k)$ bound for the flow-cut gap for a wide range of multicommodity flow problems.

We also give a polynomial time algorithm to reduce any graph packing problem $P$ to a corresponding problem on a tree: Again, let $K$ be the set of terminals.

Let $OPT(P,G)$ be the optimal value of the fractional graph packing problem $P$ on the graph $G$.

There is a polynomial time algorithm to construct a distribution $\mu$ on (a polynomial number of) trees on the terminal set $K$, s.t.

and such that any valid integral dual of cost $C$ (for any tree $T$ in the support of $\mu$) can be immediately transformed into a valid integral dual in $G$ of cost at most $C$.

As a corollary, given an approximation algorithm that achieves an approximation ratio of $C$ for the integral dual to a graph packing problem on trees, we obtain an approximation algorithm with a guarantee of $O(C\log k)$ for general graphs. We will refer to this last result as an Abstract Rounding Algorithm.

We also give a polynomial time construction of $O(\log k/\log\log k)$ quality flow-sparsifiers (and consequently cut-sparsifiers as well), which were previously only known to exist, but finding a polynomial time construction was still open. We accomplish this by performing a lifting (inspired by Earth-mover constraints) on an appropriate linear program. This lifting allows us to implicitly enforce a constraint that previously was difficult to enforce, and required an approximate separation oracle rather than an exact separation oracle. We give the details in section 5.

Maximum Concurrent Flow

An instance of the maximum concurrent flow problem consists of an undirected graph $G=(V,E)$, a capacity function $c:E\rightarrow\Re^{+}$ that assigns a non-negative capacity to each edge, and a set of demands $\{(s_{i},t_{i},f_{i})\}$ where $s_{i},t_{i}\in V$ and $f_{i}$ is a non-negative demand. We denote $K=\cup_{i}\{s_{i},t_{i}\}$. The maximum concurrent flow question asks, given such an instance, what is the largest fraction of the demand that can be simultaneously satisfied? This problem can be formulated as a polynomial-sized linear program, and hence can be solved in polynomial time. However, a more natural formulation of the maximum concurrent flow problem can be written using an exponential number of variables.

For any $a,b\in V$ let $P_{a,b}$ be the set of all (simple) paths from $a$ to $b$ in $G$. Then the maximum concurrent flow problem and the corresponding dual can be written as :

For a maximum concurrent flow problem, let $\lambda^{*}$ denote the optimum.

Let $|K|=k$. Then for a given set of demands $\{s_{i},t_{i},f_{i}\}$, we associate a vector $\vec{f}\in\Re^{k\choose 2}$ in which each coordinate corresponds to a pair $(x,y)\in{K\choose 2}$ and the value $\vec{f}_{x,y}$ is defined as the demand $f_{i}$ for the terminal pair $s_{i}=x,t_{i}=y$.

We denote $cong_{G}(\vec{f})=\frac{1}{\lambda^{*}}$

Or equivalently $cong_{G}(\vec{f})$ is the minimum $C$ s.t. $\vec{f}$ can be routed in $G$ and the total flow on any edge is at most $C$ times the capacity of the edge.

Throughout we will use the notation that graphs $G_{1},G_{2}$ (on the same node set) are "summed" by taking the union of their edge set (and allowing parallel edges).

Suppose we are given an undirected, capacitated graph $G=(V,E)$ and a set $K\subset V$ of terminals of size $k$. Let $h:2^{V}\rightarrow\Re^{+}$ denote the cut function of $G$: $h(A)=\sum_{(u,v)\in E\mbox{ s.t. }u\in A,v\in V-A}c(u,v)$. We define the function $h_{K}:2^{K}\rightarrow\Re^{+}$ which we refer to as the terminal cut function on $K$: $h_{K}(U)=\min_{A\subset V\mbox{ s.t. }A\cap K=U}h(A)$.

$G^{\prime}$ is a cut-sparsifier for the graph $G=(V,E)$ and the terminal set $K$ if $G^{\prime}$ is a graph on just the terminal set $K$ (i.e. $G^{\prime}=(K,E^{\prime})$) and if the cut function $h^{\prime}:2^{K}\rightarrow\Re^{+}$ of $G^{\prime}$ satisfies (for all $U\subset K$)

We can define a notion of quality for any particular cut-sparsifier:

The quality of a cut-sparsifier $G^{\prime}$ is defined as

We will abuse notation and define $\frac{0}{0}=1$ so that when $U$ is disconnected from $K-U$ in $G$ or if $U=\emptyset$ or $U=K$, the ratio of the two cut functions is $1$ and we ignore these cases when computing the worst-case ratio and consequently the quality of a cut-sparsifier.

2 00-Extensions

$f:V\rightarrow K$ is a -extension if for all $a\in K$, $f(a)=a$.

So a -extension $f$ is a clustering of the nodes in $V$ into sets, with the property that each set contains exactly one terminal.

Given a graph $G=(V,E)$ and a set $K\subset V$, and -extension $f$, $G_{f}=(K,E_{f})$ is a capacitated graph in which for all $a,b\in K$, the capacity $c_{f}(a,b)$ of edge $(a,b)\in E_{f}$ is

Lower Bounds for Cut Sparsifiers

Consider the following construction for a graph $G$. Let $Y$ be the hypercube of size $2^{d}$ for $d=\log k$. Then for every node $y_{s}\in Y$ (i.e. $s\in\{0,1\}^{d}$), we add a terminal $z_{s}$ and connect the terminal $z_{s}$ to $y_{s}$ using an edge of capacity $\sqrt{d}$. All the edges in the hypercube are given capacity $1$. We’ll use this instance to show 2 lower bounds, one for 0-extension cut sparsifiers and the other for arbitrary cut sparisifers.

Also, given the graph $G=(V,E)$ a set $K\subset V$ of terminals, and a semi-metric $D$ on $K$ we define the -extension problem as:

We denote $OPT(G,K,D)$ as the value of this optimum.

Let $\Delta_{U}$ denote the cut-metric in which $\Delta_{U}(u,v)=1_{|U\cap\{u,v\}|=1}$.

Also, given an partition $\mathcal{P}$ of $V$, we will refer to $\Delta_{\mathcal{P}}$ as the partition metric (induced by $\mathcal{P}$) which is $1$ if $u$ and $v$ are contained in different subsets of the partition $\mathcal{P}$, and is otherwise.

We refer to this linear program as the Semi-Metric Relaxation. For a particular instance $(G,K,D)$ of the -extension problem, we denote the optimal solution to this linear program as $OPT_{sm}(G,K,D)$.

We will refer to this linear program as the Cut-Cut Relaxation. For a particular instance $(G,K,D)$ of the -extension problem, we denote the optimal solution to this linear program as $OPT_{cc}(G,K,D)$.

The value of this linear program is that an upper bound on the integrality gap of this linear program (for a particular graph $G$ and a set of terminals $K$) gives an upper bound on the quality of cut-sparsifiers. In fact, a stronger statement is true, and the quality of the best cut-sparsifier that can be achieved through contractions will be exactly equal to the maximum integrality gap of this linear program. The upper bound is given in -and here we exhibit a strong duality:

The Contraction Quality of $G,K$ is defined to be the minimum $\alpha$ such that there is a distribution on -extensions $\gamma$ and $H=\sum_{f}\gamma(f)G_{f}$ is a $\alpha$ quality cut-sparsifier.

Consider then the cost of the semi-metric $D$ against the cut-sparsifier $H$ which is defined to be $\sum_{(a,b)}c_{H}(a,b)D(a,b)=\sum_{f}\gamma(f)\sum_{(a,b)}c_{f}(a,b)D(a,b)$ which is just the average cost of $D$ against $G_{f}$ where $f$ is sampled from the distribution $\gamma$. The Cut-Cut Linear Program gives a decomposition of $D$ into a weighted sum of cut-metrics - i.e. $D(a,b)=\sum_{U}\delta(U)\Delta_{U}(a,b)$. Also, the cost of $D$ against $H$ is linear in $D$ so this implies that

In the last line, we use $\sum_{(a,b)}c_{H}(a,b)\Delta_{U}(a,b)=h^{\prime}(U\cap K)$. Then

In the inequality, we have used the fact that $H$ is an $\alpha$-quality cut-sparsifier, and in the last line we have used that $\delta(U)>0$ implies that $h(U)=h_{K}(U\cap K)$. This completes the proof because the average cost of $D$ against $G_{f}$ where $f$ is sampled from $\gamma$ is at most $\alpha OPT_{cc}(G,K,D)$, so there must be some $f$ s.t. the cost against $D$ is at most $\alpha OPT_{cc}(G,K,D)$. ∎

We will use this strong duality between the Cut-Cut Relaxation and the Contraction Quality to show that for the graph $G$ given above, no distribution on -extensions gives better than an $\Omega(\sqrt{\log k})$ quality cut-sparsifier, and all we need to accomplish this is to demonstrate an integrality gap on the example for the Cut-Cut Relaxation.

Let’s repeat the construction of $G$ here. Let $Y$ be the hypercube of size $2^{d}$ for $d=\log k$. Then for every node $y_{s}\in Y$ (i.e. $s\in\{0,1\}^{d}$), we add a terminal $z_{s}$ and connect the terminal $z_{s}$ to $y_{s}$ using an edge of capacity $\sqrt{d}$. All the edges in the hypercube are given capacity $1$.

Then consider the distance assignment to the edges: Each edge connecting a terminal to a node in the hypercube - i.e. an edge of the form $(z_{s},y_{s})$ is assigned distance $\sqrt{d}$ and every other edge in the graph is assigned distance $1$. Then let $\sigma$ be the shortest path metric on $V$ given these edge distances.

Proof: We can take $\delta(U)=1$ for any cut $(U,V-U)$ s.t. $U=\{z_{s}\cup y_{s}|s_{i}=1\}$ - i.e. $U$ is the axis-cut corresponding to the $i^{th}$ bit. We also take $\delta(U)=\sqrt{d}$ for each $U=\{z_{s}\}$. This set of weights will achieve $\sigma(u,v)=\sum_{U}\delta(U)\Delta_{U}(u,v)$, and also there are $d$ axis cuts each of which has capacity $h(U)=\frac{k}{2}$ and there are $k$ singleton cuts of weight $\sqrt{d}$ and capacity $\sqrt{d}$ so the total cost is $O(kd)$.

Yet if we take $D$ equal to the restriction of $\sigma$ on $K$, then $OPT(G,K,D)=\Omega(kd^{3/2})$:

Proof: Consider any -extension $f$. And we can define the weight of any terminal $a$ as $weight_{f}(a)=|f^{-1}(a)|=|\{v|f(v)=a\}|$. Then $\sum_{a}weight_{f}(a)=n$ because each node in $V$ is assigned to some terminal. We can define a terminal as heavy with respect to $f$ if $weight_{f}(a)\geq\sqrt{k}$ and light otherwise. Obviously, $\sum_{a}weight_{f}(a)=\sum_{a\mbox{ s.t. }a\mbox{ is light}}weight_{f}(a)+\sum_{a\mbox{ s.t. }a\mbox{ is heavy}}weight_{f}(a)$ so the sum of the sizes of either all heavy terminals or of all light terminals is at least $\frac{n}{2}=\Omega(k)$.

Suppose that $\sum_{a\mbox{ s.t. }a\mbox{ is light}}weight_{f}(a)=\Omega(k)$. For any pair of terminals $a,b$, $D(a,b)\geq\sqrt{d}$. Also for any light terminal $a$, $f^{-1}(a)-\{a\}$ is a subset of the Hypercube of at most $\sqrt{k}$ nodes, and the small-set expansion of the Hypercube implies that the number of edges out of this set is at least $\Omega(weight_{f}(a)\log k)=\Omega(weight_{f}(a)d)$. Each such edge pays at least $\sqrt{d}$ cost, because $D(a,b)\geq\sqrt{d}$ for all pairs of terminals. So this implies that the total cost of the -extension $f$ is at least $\sum_{a\mbox{ s.t. }a\mbox{ is light}}\Omega(weight_{f}(a)d^{3/2})$.

Suppose that $\sum_{a\mbox{ s.t. }a\mbox{ is heavy}}weight_{f}(a)=\Omega(k)$. Consider any heavy terminal $z_{t}$, and consider any $y_{s}\in f^{-1}(z_{t})$ and $t\neq s$. Then the edge $(y_{s},z_{s})$ is capacity $\sqrt{d}$ and pays a total distance of $D(z_{t},z_{s})\geq\sigma(y_{t},y_{s})$. Consider any set $U$ of $\sqrt{k}$ nodes in the Hypercube. If we attempt to pack these nodes so as to minimize $\sum_{y_{s}\in U}\sigma(y_{s},y_{t})$ for some fixed node $y_{t}$, then the packing that minimizes the quantity is an appropriately sized Hamming ball centered at $y_{t}$. In a Hamming ball centered at the node $y_{t}$ of at least $\sqrt{k}$ total nodes, the average distance from $y_{t}$ is $\Omega(\log k)=\Omega(d)$, and so this implies that $\sum_{y_{s}\in f^{-1}(z_{t})}D(z_{t},z_{s})\geq\sum_{y_{s}\in f^{-1}(z_{t})}D(y_{t},y_{s})\geq\Omega(weight_{f}(z_{t})d)$. Each such edge has capacity $\sqrt{d}$ so the total cost of the -extension $f$ is at least $\sum_{a\mbox{ s.t. }a\mbox{ is heavy}}\ Omega(weight_{f}(a)d^{3/2})$ ∎

And of course using our strong duality result, this integrality gap implies that any cut-sparsifier that results from a distribution on -extensions has quality at least $\Omega(\sqrt{\log k})$, and this matches the current best lower bound on the integrality gap of the Semi-Metric Relaxation for -extension, so in principle this could be the best lower bound we could hope for (if the integrality gap of the Semi-Metric Relaxation is in fact $O(\sqrt{\log k})$ then there are always cut-sparsifiers that results from a distribution on -extensions that are quality at most $O(\sqrt{\log k})$).

2 Lower bounds for Arbitrary Cut sparsifiers

We will in fact use the above example to give a lower bound on the quality of any cut-sparisifer. We will show that for the above graph, no cut-sparsifier achieves quality better than $\Omega(\log^{1/4}k)$, and this gives an exponential improvement over the previous lower bound on the quality of flow-sparsifiers (which is even a stronger requirement for sparsifiers, and hence a weaker lower bound).

The particular example $G$ that we gave above has many symmetries, and we can use these symmetries to justify considering only symmetric cut-sparsifiers. The fact that these cut-sparsifiers can be assumed without loss of generality to have nice symmetry properties, translates to that any such cut-sparsifier $H$ is characterized by a much smaller set of variables rather than one variable for every pair of terminals. In fact, we will be able to reduce the number of variables from $k\choose 2$ to $\log k$. This in turn will allow us to consider a much smaller family of cuts in $G$ in order to derive that the system is infeasible. In fact, we will only consider sub-cube cuts (cuts in which $U=\{z_{s}\cup y_{s}|s=[0,0,0,....0,*,*,...,*]\}$) and the Hamming ball $U=\{z_{s}\cup y_{s}|d(y_{s},y_{0})\leq\frac{d}{2}\}$.

The operation $J_{s}$ for some $s\in\{0,1\}^{d}$ which is defined as $J_{s}(y_{t})=y_{t+s\mod 2}$ and $J_{s}(z_{t})=z_{t+s\mod 2}$. Also let $J_{s}(U)=\cup_{u\in U}J_{s}(u)$.

For any permutation $\pi:[d]\rightarrow[d]$, $\pi(s)=[s_{\pi(1)},s_{\pi(2)},...s_{\pi(d)}]$. Then the operation $J_{\pi}$ for any permutation $\pi$ is defined at $J_{\pi}(y_{t})=y_{\pi(t)}$ and $T_{\pi}(z_{t})=z_{\pi(t)}$. Also let $J_{\pi}(U)=\cup_{u\in U}T_{\pi}(u)$.

For any subset $U\subset V$ and any $s\in\{0,1\}^{d}$, $h(U)=h(J_{s}(U))$.

For any subset $U\subset V$ and any permutation $\pi:[d]\rightarrow[d]$, $h(U)=h(J_{\pi}(U))$.

Both of these operations are automorphisms of the weighted graph $G$ and also send the set $K$ to $K$.

If there is a cut-sparsifier $H$ for $G$ which has quality $\alpha$, then there is a cut-sparsifier $H^{\prime}$ which has quality at most $\alpha$ and is invariant under the automorphisms of the weighted graph $G$ that send $K$ to $K$.

Proof: Given the cut-sparsifier $H$, we can apply an automorphism $J$ to $G$, and because $h(U)=h(J(U))$, this implies that $h_{K}(A)=\min_{U\mbox{ s.t. }U\cap K=A}h(U)=\min_{U\mbox{ s.t. }U\cap K=A}h(J(U))$. Also $J(U\cap K)=J(U)\cap J(K)=J(U)\cap K$ so we can re-write this last line as

And if we set $U^{\prime}=J^{-1}(U)$ then this last line becomes equivalent to

So the result is that $h_{K}(A)=h_{K}(J(A))$ and this implies that if we do not re-label $H$ according to $J$, but we do re-label $G$, then for any subset $A$, we are checking whether the minimum cut in $G$ re-labeled according to $J$, that separates $A$ from $K-A$ is close to the cut in $H$ that separates $A$ from $K-A$. The minimum cut in the re-labeled $G$ that separates $A$ from $K-A$, is just the minimum cut in $G$ that separates $J^{-1}(A)$ from $K-J^{-1}(A)$ (because the set $J^{-1}(A)$ is the set that is mapped to $A$ under $J$). So $H$ is an $\alpha$-quality cut-sparsifier for the re-labeled $G$ iff for all $A$:

which is of course true because $H$ is an $\alpha$-quality cut-sparsifier for $G$.

So alternatively, we could have applied the automorphism $J^{-1}$ to $H$ and not re-labeled $G$, and this resulting graph $H_{J^{-1}}$ would also be an $\alpha$-quality cut-sparsifier for $G$. Also, since the set of $\alpha$-quality cut-sparsifiers is convex (it is defined by a system of inequalities), we can find a cut-sparsifier $H^{\prime}$ that has quality at most $\alpha$ and is a fixed point of the group of automorphisms, and hence invariant under the automorphisms of $G$ as desired. ∎

If $\alpha$ is the best quality cut-sparsifier for the above graph $G$, then there is an $\alpha$ quality cut-sparsifier $H$ in which the capacity between two terminals $z_{s}$ and $z_{t}$ is only dependent on the Hamming distance $Hamm(s,t)$.

Proof: Given any quadruple $z_{s},z_{t}$ and $z_{s^{\prime}},z_{t^{\prime}}$ s.t. $Hamm(s,t)=Hamm(s^{\prime},t^{\prime})$, there is a concatenation of operations from $J_{s}$, $J_{\pi}$ that sends $s$ to $s^{\prime}$ and $t$ to $t^{\prime}$. This concatenation of operations $J$ is in the group of automorphisms that send $K$ to $K$, and hence we can assume that $H$ is invariant under this operation which implies that $c_{H}(s,t)=c_{H}(s^{\prime},t^{\prime})$. ∎

One can regard any cut-sparsifier (not just ones that result from contractions) as a set of $k\choose 2$ variables, one for the capacity of each edge in $H$. Then the constraints that $H$ be an $\alpha$-quality cut-sparsifier are just a system of inequalities, one for each subset $A\subset K$ that enforces that the cut in $H$ is at least as large as the minimum cut in $G$ (i.e. $h^{\prime}(A)\geq h_{K}(A)$) and one enforcing that the cut is not too large (i.e. $h^{\prime}(A)\leq\alpha h_{K}(A)$). Then in general, one can derive lower bounds on the quality of cut-sparsifiers by showing that if $\alpha$ is not large enough, then this system of inequalities is infeasible meaning that there is not cut-sparsifier achieving quality $\alpha$. Unlike the above argument, this form of a lower bound is much stronger and does not assume anything about how the cut-sparsifier is generated.

Theorem 1. For $\alpha=\Omega(\log^{1/4}k)$, there is no cut-sparsifier $H$ for $G$ which has quality at most $\alpha$.

Proof (sketch): Assume that there is a cut-sparsifier $H^{\prime}$ of quality at most $\alpha$. Then using the above corollary, there is a cut-sparsifier $H$ of quality at most $\alpha$ in which the weight from $a$ to $b$ is only a function of $Hamm(a,b)$. Then for each $i\in[d]$, we can define a variable $w_{i}$ as the total weight of edges incident to any terminal of length $i$. I.e. $w_{i}=\sum_{b\mbox{ s.t. }Hamm(a,b)=i}c_{H}(a,b)$.

For simplicity, here we will assume that all cuts in the sparsifier $H$ are at most the cost of the corresponding minimum cut in $G$ and at least $\frac{1}{\alpha}$ times the corresponding minimum cut. This of course is an identical set of constraints that we get from dividing the standard definition that we use in this paper for $\alpha$-quality cut-sparsifiers by $\alpha$.

We need to derive a contradiction from the system of inequalities that characterize the set of $\alpha$-quality cut sparsifiers for $G$. As we noted, we will consider only the sub-cube cuts (cuts in which $U=\{z_{s}\cup y_{s}|s=[0,0,0,....0,*,*,...*]\}$) and the Hamming ball $U=\{z_{s}\cup y_{s}|d(y_{s},y_{0})\leq\frac{d}{2}\}$, which we refer to as the Majority Cut.

Consider the Majority Cut: There are $\Theta(k)$ terminals on each side of the cut, and most terminals have Hamming weight close to $\frac{d}{2}$. In fact, we can sort the terminals by Hamming weight and each weight level around Hamming weight $\frac{d}{2}$ has roughly a $\Theta(\frac{1}{\sqrt{d}})$ fraction of the terminals. Any terminal of Hamming weight $\frac{d}{2}-\sqrt{i}$ has roughly a constant fraction of their weight $w_{i}$ crossing the cut in $H$, because choosing a random terminal Hamming distance $i$ from any such terminal corresponds to flipping $i$ coordinates at random, and throughout this process there are almost an equal number of $1$s and s so this process is well-approximated by a random walk starting at $\sqrt{i}$ on the integers, which equally likely moves forwards and backwards at each step for $i$ total steps, and asking the probability that the walk ends at a negative integer.

In particular, for any terminal of Hamming weight $\frac{d}{2}-t$, the fraction of the weight $w_{i}$ that crosses the Majority Cut is $O(exp\{-\frac{t^{2}}{i})$. So the total weight of length $i$ edges (i.e. edges connecting two terminals at Hamming distance $i$) cut by the Majority Cut is $O(w_{i}|\{z_{s}|Hamm(s,0)\geq\frac{d}{2}-\sqrt{i}\}|)=O(w_{i}\sqrt{i/d})k$ because each weight close to the boundary of the Majority cut contains roughly a $\Theta(\frac{1}{\sqrt{d}})$ fraction of the terminals. So the total weight of edges crossing the Majority Cut in $H$ is $O(k\sum_{i=1}^{d}w_{i}\sqrt{i/d})$

And the total weight crossing the minimum cut in $G$ separating $A=\{z_{s}|d(y_{s},y_{0})\leq\frac{d}{2}\}$ from $K-A$ is $\Theta(k\sqrt{d})$. And because the cuts in $H$ are at least $\frac{1}{\alpha}$ times the corresponding minimum cut in $G$, this implies $\sum_{i=1}^{d}w_{i}\sqrt{i/d}\geq\Omega(\frac{\sqrt{d}}{\alpha})$

Next, we consider the set of sub-cube cuts. For $j\in[d]$, let $A_{j}=\{z_{s}|s_{1}=0,s_{2}=0,..s_{j}=0\}$. Then the minimum cut in $G$ separating $A_{j}$ from $K-A_{j}$ is $\Theta(|A_{j}|\min(j,\sqrt{d}))$, because each node in the Hypercube which has the first $j$ coordinates as zero has $j$ edges out of the sub-cube, and when $j>\sqrt{d}$, we would instead choose cutting each terminal $z_{s}\in A_{j}$ from the graph directly by cutting the edge $(y_{s},z_{s})$.

Also, for any terminal in $A_{j}$, the fraction of length $i$ edges that cross the cut is approximately $1-(1-\frac{j}{d})^{i}=\Theta(\min(\frac{ij}{d},1))$. So the constraints that each cut in $H$ be at most the corresponding minimum cut in $G$ give the inequalities $\sum_{i=1}^{d}\min(\frac{ij}{d},1)w_{i}\leq O(\min(j,\sqrt{d}))$

We refer to the above constraint as $B_{j}$. Multiply each $B_{j}$ constraint by $\frac{1}{j^{3/2}}$ and adding up the constraints yields a linear combination of the variables $w_{i}$ on the left-hand side. The coefficient of any $w_{i}$ is

And using the Integration Rule this is $\Omega(\sqrt{\frac{i}{d}})$.

This implies that the coefficients of the constraint $B$ resulting from adding up $\frac{1}{j^{3/2}}$ times each $B_{j}$ for each $w_{i}$ are at least as a constant times the coefficient of $w_{i}$ in the Majority Cut Inequality. So we get

And we can evaluate the constant $\sum_{j=1}^{d-1}j^{-3/2}\min(j,\sqrt{d})=\sum_{j=1}^{\sqrt{d}}j^{-1/2}+\sqrt{d}\sum_{j=\sqrt{d}+1}^{d-1}j^{-3/2}$ using the Integration Rule, this evaluates to $O(d^{1/4})$. This implies $O(d^{1/4})\geq\frac{\sqrt{d}}{\alpha}$ and in particular this implies $\alpha\geq\Omega(d^{1/4})$. So the quality of the best cut-sparsifier for $H$ is at least $\Omega(\log^{1/4}k)$. $\Box$

We note that this is the first super-constant lower bound on the quality of cut-sparsifiers. Recent work gives a super-constant lower bound on the quality of flow-sparsifiers in an infinite family of expander-like graphs. However, for this family there are constant-quality cut-sparsifiers. In fact, lower bounds for cut-sparsifiers imply lower bounds for flow-sparsifiers, so we are able to improve the lower bound of $\Omega(\log\log k)$ in the previous work for flow-sparsifiers by an exponential factor to $\Omega(\log^{1/4}k)$, and this is the first lower bound that is tight to within a polynomial factor of the current best upper bound of $O(\frac{\log k}{\log\log k})$.

This bound is not as good as the lower bound we obtained earlier in the restricted case in which the cut-sparsifier is generated as a convex combination of -extension graphs $G_{f}$. As we will demonstrate, there are actually cut-sparsifiers that achieve quality $o(\sqrt{\log k})$ for $G$, and so in general restricting to convex combinations of -extensions is sub-optimal, and we leave open the possibility that the ideas in this improved bound may result in better constructions of cut (or flow)-sparsifiers that are able to beat the current best upper bound on the integrality gap of the -extension linear program.

Noise Sensitive Cut-Sparsifiers

In Appendix A, we give a brief introduction to the harmonic analysis of Boolean functions, along with formal statements that we will use in the proof of our main theorem in this section.

Here we give a cut-sparsifier $H$ which will achieve quality $o(\sqrt{\log k})$ for the graph $G$ given in Section 3, which is asymptotically better than the best cut-sparsifier that can be generated from contractions.

As we noted, we can assume that the weight assigned between a pair of terminals in $H$, $c_{H}(a,b)$ is only a function of the Hamming distance from $a$ to $b$. In $G$, the minimum cut separating any singleton terminal $\{z_{s}\}$ from $K-\{z_{s}\}$ is just the cut that deletes the edge $(z_{s},y_{s})$. So the capacity of this cut is $\sqrt{d}$. We want a good cut-sparsifier to approximately preserve this cut, so the total capacity incident to any terminal in $H$ will also be $\sqrt{d}$ - i.e. $c^{\prime}(\{z_{s}\})=\sqrt{d}$.

We distribute this capacity among the other terminals as follows: We sample $t\sim_{\rho}s$, and allocate an infinitesimal fraction of the total weight $\sqrt{d}$ to the edge $(z_{s},z_{t})$. Equivalently, the capacity of the edge connecting $z_{s}$ and $z_{t}$ is just $Pr_{u\sim_{\rho}t}[u=s]\sqrt{d}$. We choose $\rho=1-\frac{1}{\sqrt{d}}$. This choice of $\rho$ corresponds to flipping each bit in $t$ with probability $\Theta(\frac{1}{\sqrt{d}})$ when generating $u$ from $t$. We prove that the graph $H$ has cuts at most the corresponding minimum-cut in $G$.

This cut-sparsifier $H$ has cuts at most the corresponding minimum-cut in $G$. In fact, a stronger statement is true: $\vec{H}$ can be routed as a flow in $G$ with congestion $O(1)$. Consider the following explicit routing scheme for $\vec{H}$: Route the $\sqrt{d}$ total flow in $\vec{H}$ out of $z_{s}$ to the node $y_{s}$ in $G$. Now we need to route these flows through the Hypercube in a way that does not incur too much congestion on any edge. Our routing scheme for routing the edge from $z_{s}$ to $z_{t}$ in $\vec{H}$ from $y_{s}$ to $y_{t}$ will be symmetric with respect to the edges in the Hypercube: choose a random permutation of the bits $\pi:[d]\rightarrow[d]$, and given $u\sim_{\rho}t$, fix each bit in the order defined by $\pi$. So consider $i_{1}=\pi(1)$. If $t_{i_{1}}\neq u_{i_{1}}$, and the flow is currently at the node $x$, then flip the $i_{1}^{th}$ bit of $x$, and continue for $i_{2}=\pi(2)$, $i_{3},...i_{d}=\pi(d)$.

Each permutation $\pi$ defines a routing scheme, and we can average over all permutations $\pi$ and this results in a routing scheme that routes $\vec{H}$ in $G$.

This routing scheme is symmetric with respect to the automorphisms $J_{s}$ and $J_{\pi}$ of $G$ defined above.

The congestion on any edge in the Hypercube incurred by this routing scheme is the same.

The above routing scheme will achieve congestion at most $O(1)$ for routing $\vec{H}$ in $G$.

Proof: Since the congestion of any edge in the Hypercube under this routing scheme is the same, we can calculate the worst case congestion on any edge by calculating the average congestion. Using a symmetry argument, we can consider any fixed terminal $z_{s}$ and calculate the expected increase in average congestion when sampling a random permutation $\pi:[d]\rightarrow[d]$ and routing all the edges out of $z_{s}$ in $H$ using $\pi$. This expected value will be $k$ times the average congestion, and hence the worst-case congestion of routing $\vec{H}$ in $G$ according to the above routing scheme.

As we noted above, we can define $H$ equivalently as arising from the random process of sampling $u\sim_{\rho}t$, and routing an infinitesimal fraction of the $\sqrt{d}$ total capacity out of $z_{t}$ to $z_{u}$, and repeating until all of the $\sqrt{d}$ capacity is allocated. We can then calculate the the expected increase in average congestion (under a random permutation $\pi$) caused by routing the edges out of $z_{s}$ as the expected increase in average congestion divided by the total fraction of the $\sqrt{d}$ capacity allocated when we choose the target $u$ from $u\sim_{\rho}t$. In particular, if we allocated a $\Delta$ fraction of the $\sqrt{d}$ capacity, the expected increase in total congestion is just the total capacity that we route multiplied by the length of the path. Of course, the length of this path is just the number of bits in which $u$ and $t$ differ, which in expectation is $\Theta(\sqrt{d})$ by our choice of $\rho$.

So in this procedure, we allocate $\Delta\sqrt{d}$ total capacity, and the expected increase in total congestion is the total capacity routed $\Delta\sqrt{d}$ times the expected path length $\Theta(\sqrt{d})$. We repeat this procedure $\frac{1}{\Delta}$ times, and so the expected increase in total congestion caused by routing the edges out of $z_{t}$ in $G$ is $\Theta(d)$. If we perform this procedure for each terminal, the resulting total congestion is $\Theta(kd)$, and because there are $\frac{kd}{2}$ edges in the Hypercube, the average congestion is $\Theta(1)$ which implies that the worst-case congestion on any edge in the Hypercube is also $O(1)$, as desired. Also, the congestion on any edge $(z_{s},y_{s})$ is $1$ because there is a total of $\sqrt{d}$ capacity out of $z_{s}$ in $H$, and this is the only flow routed on this edge, which has capacity $\sqrt{d}$ in $G$ by construction. So the worst-case congestion on any edge in the above routing scheme is $O(1)$. ∎

For any $A\subset K$, $h^{\prime}(A)\leq O(1)h_{K}(A)$.

Proof: Consider any set $A\subset K$. Let $U$ be the minimum cut in $G$ separating $A$ from $K-A$. Then the total flow routed from $A$ to $K-A$ in $\vec{H}$ is just $h^{\prime}(A)$, and if this flow can be routed in $G$ with congestion $O(1)$, this implies that the total capacity crossing the cut from $U$ to $V-U$ is at least $\Omega(1)h^{\prime}(A)$. And of course the total capacity crossing the cut from $U$ to $V-U$ is just $h_{K}(A)$ by the definition of $U$, which implies the corollary. ∎

So we know that the cuts in $H$ are never too much larger than the corresponding minimum cut in $G$, and all that remains to show that the quality of $H$ is $o(\sqrt{\log k})$ is to show that the cuts in $H$ are never too small. We conjecture that the quality of $H$ is actually $\Theta(\log^{1/4}k)$, and this seems natural since the quality of $H$ just restricted to the Majority Cut and the sub-cube cuts is actually $\Theta(\log^{1/4}k)$, and often the Boolean functions corresponding to these cuts serve as extremal examples in the harmonic analysis of Boolean functions. In fact, our lower bound on the quality of any cut-sparsifier for $G$ is based only on analyzing these cuts so in a sense, our lower bound is tight given the choice of cuts in $G$ that we used to derive infeasibility in the system of equalities characterizing $\alpha$-quality cut-sparsifiers.

2 A Fourier Theoretic Characterization of Cuts in H𝐻H

Here we give a simple formula for the size of a cut in $H$, given the Fourier representation of the cut. So here we consider cuts $A\subset K$ to be Boolean functions of the form $f_{A}:\{-1,+1\}^{d}\rightarrow\{-1,+1\}$ s.t. $f_{A}(s)=+1$ iff $z_{s}\in A$.

$h^{\prime}(A)=k\frac{\sqrt{d}}{2}\frac{1-NS_{\rho}[f_{A}(x)]}{2}$

Proof: We can again use the infinitesimal characterization for $H$, in which we choose $u\sim_{\rho}t$ and allocate $\Delta$ units of capacity from $z_{s}$ to $z_{t}$ and repeat until all $\sqrt{d}$ units of capacity are spent.

If we instead choose $z_{s}$ uniformly at random, and then choose $u\sim_{\rho}t$ and allocate $\Delta$ units of capacity from $z_{s}$ to $z_{t}$, and repeat this procedure until all $k\frac{\sqrt{d}}{2}$ units of capacity are spent, then at each step the expected contribution to the cut is exactly $\Delta\frac{1-NS_{\rho}[f_{A}(x)]}{2}$ because $\frac{1-NS_{\rho}[f_{A}(x)]}{2}$ is exactly the probability that if we choose $t$ uniformly at random, and $u\sim_{\rho}t$ that $f_{A}(u)\neq f_{A}(t)$ which means that this edge contributes to the cut. We repeat this procedure $\frac{k\sqrt{d}}{2\Delta}$ times, so this implies the lemma. ∎

h^{\prime}(A)=\Theta\Big{(}k\sum_{S}\hat{f}_{S}^{2}\min(|S|,\sqrt{d})\Big{)}

Proof: Using the setting $\rho=1-\frac{1}{\sqrt{d}}$, we can compute $h^{\prime}(A)$ using the above lemma: