UC Berkeley

Graph partitioning has played an important role in theoretical computer science, particularly

in the design of approximation algorithms and metric embeddings. In some of these applica-

tions, fundamental tradeoffs in graph partitioning prevented further progress. To overcome

these barriers, we consider partitions of certain derived graphs of an undirected graph G ob-

tained by applying Gaussian elimination to the Laplacian matrix of G to eliminate vertices

from G. We use this technique and others to obtain new results on the following fronts:

Cheeger’s Inequality: Cheeger’s inequality shows that any undirected graph G with min-

imum

√ nonzero normalized Laplacian eigenvalue λ G has a cut with conductance at most

O( λ G ). Qualitatively, Cheeger’s inequality says that if the relaxation time of a graph is

high, there is a cut that certifies this. However, there is a gap in this relationship, as cuts

can have conductance as low as Θ(λ G ).

To better approximate the relaxation time of a graph, we consider a more general object.

Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphs

obtained via Gaussian elimination from G. Combinatorially, random walks in these graphs

are equivalent in distribution to random walks in G restricted to a subset of its vertices. As

a result, all Schur complement cuts have conductance at least Ω(λ G ). We show that unlike

with cuts, this inequality is tight up to a constant factor. Specifically, there is a derived

graph containing a cut with conductance at most O(λ G ).

Oblivious Routing: We show that in any graph, the average length of a flow path in an

electrical flow between the endpoints of a random edge is O(log 2 n). This is a consequence of

a more general result which shows that the spectral norm of the entrywise absolute value of

the transfer impedance matrix of a graph is O(log 2 n). This result implies a simple oblivious

routing scheme based on electrical flows in the case of transitive graphs.

Random Spanning Tree Sampling: We give an m 1+o(1) β o(1) -time algorithm for generat-

ing uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In2

the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome

by eliminating vertices from a graph using Schur complements of the associated Laplacian

matrix.

Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree

using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut

the random walk from a vertex v to the boundary of a set of vertices assigned to v called a

“shortcutter.” We depart from prior work by introducing a new way of employing Laplacian

solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most

random walk steps occur far away from an unvisited vertex. We apply this observation by

charging uses of a shortcutter S to random walk steps in the Schur complement obtained by

eliminating all vertices in S that are not assigned to it.

Spectral Sparsification: We introduce a new approach to spectral sparsification that

approximates the quadratic form of the pseudoinverse of a graph Laplacian restricted to a

subspace. We show that sparsifiers with a near-linear number of edges in the dimension

of the subspace exist. Our setting generalizes that of Schur complement sparsifiers. Our

approach produces sparsifiers by sampling a uniformly random spanning tree of the input

graph and using that tree to guide an edge elimination procedure that contracts, deletes,

and reweights edges. In the context of Schur complement sparsifiers, our approach has two

benefits over prior work. First, it produces a sparsifier in almost-linear time with no runtime

dependence on the desired error. We directly exploit this to compute approximate effective

resistances for a small set of vertex pairs in faster time than prior work [33]. Secondly,

it yields sparsifiers that are reweighted minors of the input graph. As a result, we give a

near-optimal answer to a variant of the Steiner point removal problem.

A key ingredient of our algorithm is a subroutine of independent interest: a near-linear

time algorithm that, given a chosen set of vertices, builds a data structure from which we

can query a multiplicative approximation to the decrease in the effective resistance between

two vertices after identifying all vertices in the chosen set to a single vertex with inverse

polynomial additional additive error in near-constant time.