Localization of Electrical Flows
Satish Rao†
EECS, UC Berkeley
satishr@cs.berkeley.edu

arXiv:1708.01632v1 [] 4 Aug 2017

Aaron Schild∗
EECS, UC Berkeley
aschild@berkeley.edu

Nikhil Srivastava‡
Mathematics, UC Berkeley
nikhil@math.berkeley.edu
August 8, 2017

Abstract
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(log2 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(log2 n). This result implies a simple oblivious routing scheme based on
electrical flows in the case of transitive graphs.

1

Introduction

Electrical Flows have have played an important role in several recent advances in graph algorithms
— for instance, in the context of exact and approximate maximum flow/minimum cut [CKM+ 11,
LRS13, Mad13], multicommodity flow [KMP12], oblivious routing [HHN+ 08, LN09, KM11], graph
sparsification [SS11], and random spanning tree generation [KM09, MST15]. This is due to the
emergence of nearly linear time Laplacian solvers for computing them, beginning with the work of
Spielman and Teng [ST04], and also to their well-known connections with random walks. Using
them to solve combinatorial problems is not typically immediate, and may be likened to putting
a square peg into a round hole: at a high level, many of the traditional problems of computer
science are concerned with finding flows in graphs with controlled ℓ1 and ℓ∞ norms (corresponding
to distance and congestion, respectively), whereas electrical flows minimize the ℓ2 norm (energy).
Reducing one to the other often requires some sort of iterative method for combining many electrical
flows with varying demands and graphs.
In this work, we ask the following basic structural question about electrical flows in arbitrary
unweighted graphs:
What is the typical ℓ1 norm of the unit current electrical flow between two neighboring
vertices u, v in a graph?
∗

Supported by NSF grant CCF-1535977.
Supported by NSF grant CCF-1535977.
‡
Supported by NSF grant CCF-1553751 and a Sloan research fellowship.
†

1

Recall that the ℓ1 norm of a unit circulation-free flow is the average distance traveled by the flow,
since any such flow fuv : E → R may be decomposed as a convex combination of paths which all
have the same direction of flow on every edge:
X
αi fi ,
fuv =
i∈Puv

where Puv is the set of simple paths from u to v, and we have
X
X
αi length(fi ).
αi kfi k1 =
kfuv k1 =
i∈Puv

i∈Puv

Thus, this question asks when/whether electrical flows in a graph travel a greater distance than
shortest paths, and by how much.

1.1

Three Examples

To get a feel for this problem, and to set the context for our result and its proof, we begin by
presenting three instructive examples. We will use the notation bv for the indicator vector of a
vertex, buv = bu − bv for the signed incidence vector of an edge uv, B for the m × n signed edgevertex incidence matrix of a graph (where the edges are oriented arbitrarily), and L = B T B for the
Laplacian matrix. For any pair of vertices u, v, we will use the notation ∆(u, v) := kfuv k1 /dist(u, v),
where fuv is the unit electrical flow between u and v and dist is the shortest path distance in the
graph.
The first example shows that in general ∆(u, v) can be quite large for the worst-case edge in a
graph.
Example 1.1 (Parallel Paths). Consider the graph consisting of a single edge between vertices u
√
√
and v and m disjoint parallel paths of length m with endpoints u and v. Since the effective
resistance of the parallel paths taken together is 1, half of the unit flow between u and v will use the
√
paths, assigning a flow of 1/2 m to each path, and the other half will traverse the ege uv. Thus,
√
we have ∆(u, v) = ( m + 1)/2. However, notice that for most of the other edges in the graph, ∆
√
is tiny. For instance, for any edge ab near the middle of one of the parallel paths, a 1 − O(1/ m)
fraction of the flow will traverse the single edge, so we will have ∆(a, b) = O(1).
On the other hand, ∆(u, v) is uniformly bounded for every edge in an expander.
Example 1.2 (Expander Graphs). Let G be a constant degree d−regular expander graph with
transition matrix P satisfying kP − J/nk ≤ λ for some constant λ, where J is the all ones matrix.
Letting Q := P − J/n and E = I − J/n, we have the power series expansion orthogonal to the all
ones vector:
X
(L/d)+ = (E − Q)+ = E +
Qk .
k≥1

Now for every edge uv we calculate the electrical flow across its endpoints:
kBL+ buv k1 ≤ kBk1→1 kL+ k1→1 kbuv k1 ,

2

where k·k1→1 is the 1→1 operator norm, i.e., maximum column sum of the matrix. Let T = O(log n)
be the mixing time of G, after which kP T − J/nk1→1 = kQT k1→1 ≤ 1/n. Noting that kBk1→1 ≤ d
and Qk = P k − J/n and applying the triangle inequality, we obtain:
T

2d X
(kP k k1→1 + kJ/nk1→1 ) + kL+ k1→1 · kQT k1→1 .
kBL buv k1 ≤
d
+

k=0

Since P k is a doubly stochastic matrix we have kP k k1→1 = 1 for all k. Moreover, kL+ k1→1 ≤
√
√
nkL+ k ≤ n/λ. Combining these facts, we get a final bound of ∆(u, v) = O(log n), for every
edge uv ∈ G.
We remark that bounds similar to (and somewhat more general than) the above were shown in
the papers [LN09, KM11] using different techniques.
Finally, we note that there are highly non-expanding graphs for which ∆(u, v) is also uniformly
bounded, which means that expansion does not tell the whole story.
Example 1.3 (The Grid). Let G be the n×n two dimensional torus (i.e., grid with sides identified).
Then it is shown in [LN09] that for every edge uv ∈ G we have ∆(u, v) = O(log n), even though
G is clearly not an expander. We briefly sketch an argument explaining where this bound comes
from. Let uv be any horizontal edge in G, and let w be a vertex in G at vertical distance k from
u and v. We will show that the potential at w in the unit current uv-electrical flow is small, in
particular that
φ(w) := bTw L+ buv = O(1/k2 ).
First we recall (see, e.g., [Bol13] Chapter IX) that the potential at a vertex w when u, v are fixed to
potentials −1, 1 is: 2(Pw (tv < tu ) − Pw (tu < tv )), where Pw is the law of the random walk started
at w and tu is the first time at which the walk hits u. By Ohm’s law, this means that:
φ(w) ≤

2
(Pw (tv < tu ) − Pw (tu < tv )) ,
Reff(u, v)

where Reff(u, v) := bTuv L+ buv is the effective resistance of the edge uv. Since the resistance of every
edge in the grid is equal to 1/2, we find that |φ(w)| = O(|Pw (tv < tw ) − Pw (tw < tv )|).
We now analyze these probabilities. Roughly speaking, the random walk from w will take time
Ω(k2 ) to reach the horizontal line H containing uv, at which point its horizontal distance (along
H) from w will be distributed as a k2 -step random horizontal random walk centered at w (since
about half of the steps of the random walk up to that point will be horizontal). The difference in
probabilities between any two neighboring points in H will therefore be at most O(1/k2 ), which
implies the bound on |φ(x)|. Consequently, the potential difference across any edge wx at distance
k is at most O(1/k 2 ); since there are O(k) edges at distance k, the total contribution from such
edges is O(1/k), and summing over all distances k (and repeating the argument for vertical edges)
yields a bound of O(log n).

1.2

Our Results

Our first theorem is the following.

3

Theorem 1.4. If G = (V, E) is an unweighted graph with m edges, then
X
∆(u, v) ≤ O(m log2 n).
uv∈E

This theorem formalizes the intuition in the parallel paths example that there cannot be too
many edges in a graph for which the electrical flow uses very long paths. A corollary for edgetransitive graphs is that the above bound holds for every edge, by symmetry. This generalizes
our analysis on the grid (which used very specific properties) to a much broader category which
includes all Cayley graphs.
Theorem 1.4 is a consequence of a more general result concerning the weighted transfer impedance
matrix of a graph. Given a weighted graph G = (V, E, c) with edge weights ce ≥ 0, let C be an
m × m diagonal matrix containing the edge weights. Then L = B T CB is the Laplacian matrix of
G and the weighted transfer impedance matrix is the m × m matrix defined as:
Π = C 1/2 BL+ B T C 1/2 .
It is well-known and easy to see that the entry (BL+ B)(e, f ) is the potential difference across the
ends of edge e when a unit current is injected across the ends of edge f , and vice versa, and that Π
is a projection matrix with trace n − 1. In particular, the latter fact implies that kΠk = 1, where
k · k is the spectral norm.
Let Π be the entrywise absolute value matrix of Π. Our main theorem is:
Theorem 1.5. For an arbitrary weighted graph G,
kΠk = O(log2 n)
Theorem 1.4 follows from Theorem 1.5 by plugging in the the all ones vector u = (1, . . . , 1)T :
X
X
kΠe k1 =
∆(e),
uT Πu =
e∈E

e∈E

where Πe = BL+ buv is the row of Π corresponding to e = uv, i.e., the electrical flow across the
endpoints of e. Since kuk2 = m, the spectral norm bound in Theorem 1.5 implies that uT Πu ≤
O(m log2 n).

1.3

Applications to Oblivious Routing

Oblivious routing refers to the following problem: given a graph G, specify a set of flows {fuv }
between pairs of vertices u, v so that for any set of demand pairs (s1 , t1 ), . . . , (sk , tk ), the congestion
of the flow obtained by taking the union of {fsi ti }i≤k is at most a small factor (called the competitive
ratio) greater than the congestion of the optimal multicommodity flow for the given pairs. This is a
well-studied problem with a vast literature which we will not attempt to recount; a landmark result
is the optimal theorem of Räcke [Rac02] which shows that there is an oblivious routing scheme with
competitive ratio O(log n) for every graph.
In spite of this optimal result, there has been interest in studying whether simpler schemes
achieve good competitive ratios. A particulary simple scheme, studied in [HHN+ 08, LN09, KM11],
is to simply route fuv using the electrical flow. The paper [HHN+ 08] shows that this scheme has a
4

good competitive ratio on any graph when restricted to demands which all share a single source. It
was shown in [LN09, KM11] that the competitive ratio of electrical routing on an unweighted graph
is exactly equal to kΠk1→1 , i.e., the maximum of ∆(u, v) over all edges in a graph. In these papers,
it was shown that for grids, hypercubes, and expanders the competitive ratio is O(log n). Our
theorem immediately extends this to all transitive graphs, albeit with a guarantee of O(polylog(n))
rather than O(log(n)).
Corollary 1.6. Electrical Flow Routing achieves a competitive ratio of O(log2 n) on every edgetransitive graph.
Proof. By Theorem 1.4 and symmetry, we have that every column sum of Π is at most O(log2 n). By
Proposition 1 and Lemma 4 of [LN09] (or by Theorem 3.1 of [KM11]), this implies that routing each
pair by the electrical flow has a competitive ratio of O(log2 n) as an oblivious routing scheme.

1.4

Techniques

Given the expander example above, it may be tempting to attempt to prove Theorem 1.4 by decomposing an arbitrary graph into disjoint expanding clusters. However, using such a decomposition
would likely require proving that edge electrical flows do not cross between the clusters, which is
what we are trying to show in the first place.
We use an alternate scheme inspired by recent Schur-complement based Laplacian solvers.
Recall the Schur complement formula for the pseudoinverse of a symmetric block matrix (see e.g.
[DKP+ 17] Section 5):
Fact 1.7. If


P
L=
QT


Q
R

for symmetric P, R and R invertible, then:




I
0 Schur (L, P )+
I −QR−1
0
+
T
L =Z
Z
I
−R−1 QT I
0
R−1 0

(1)

where Schur (L, P ) = P − QR−1 QT denotes the Schur complement of L onto P , obtained by
eliminating R by partial Gaussian elimination, and Z is the projection orthogonal to the nullspace
of L.
The idea is to apply this formula to compute the terms |bTe L+ bf | by eliminating vertices oneby-one, as in [KS16], and bounding the original value of |bTe L+ bf | in terms of the value on small
Schur complements. One cannot eliminate arbitrary vertices and get a good bound, though. We
use Proposition 3.2 to show that there always exists a vertex whose elimination results in a good
bound. Since Laplacian matrices with self loops are closed under taking Schur complements the
remaining matrix is the Laplacian of a weighted graph as well. Mapping the demand vectors be
and bf to the vertex set of this graph and recurring yields the sum of interest.

2

Schur Complements, Probabilities, and Energies

In this section we collect some preliminary facts about Schur complements of Laplacians and establish some useful correspondences between electrical potentials and probabilities. We do this so
5

that after recurring on a Schur complement of the graph G that we care about, we can interpret the
recursively generated sums that we generate using Fact 1.7 in terms of G. We will make frequent
use of the fact that for a Laplacian matrix LG with block LS , the Schur complement Schur (LG , LS )
is also a Laplacian. For a graph G and subset of vertices S will use the notation Schur (G, S) to
denote the graph corresponding to Schur (LG , LS ). Since all vectors we will apply pseudoinverses
to will be orthogonal to the corresponding nullspaces (the corresponding constant vectors, since
all Schur complements will be Laplacians), we will not write the projection Z in Fact 1.7 in what
follows.
Definition 2.1. Consider a graph G. For any set of vertices S ⊆ V (G) with |S| ≥ 2, a vertex
v ∈ S, and a vertex x ∈ V (G), let
pG,S
v (x) := Px [tv < tS\v ]

For an edge e = {x, y} ∈ E(G), let
qvG,S (e) := |pSv (x) − pSv (y)|
where tS ′ denotes the hitting time to the set S ′ . Let
rvG,S (e) := max(pSv (x), pSv (y), 1/|S|)
When G is clear from the context, we omit G from the superscript.
P
Corollary 2.2. For any set S and any e = {x, y} ∈ E(G), v∈S rvG,S (x) ≤ 3.

G,S
G,S
Proof. {pG,S
v (z)}v is a distribution for any fixed vertex z ∈ V (G). Bounding rv (e) ≤ pv (x) +
G,S
1
pv (y) + |S| yields the desired result.

It is well-known that the above probabilities can be represented as normalized potentials (see,
for instance, [Bol13] Chapter IX).
Fact 2.3. Let H be the graph obtained by identifying all vertices of S\{v} to one vertex s. Then
pSv (x) :=

+
|bT
vs LH bxs |
+
bT
vs LH bvs

for any x ∈ V (G) and qvS (e) :=

+
|bT
vs LH be |
+
bT
vs LH bvs

for any e ∈ E(G).

In proving the desired result, it will help to recursively compute Schur complements with respect
to certain sets of vertices S. We now relate the Schur complement to the above probabilities, which
will be central to our proof; the following proposition is likely to be known but we include it for
completeness.
Proposition 2.4. For a set of vertices S ⊆ V (G) and a vertex x ∈ V (G) possibly not in S,
let bx ∈ RV (G) denote the indicator vector of x. Let bSx ∈ RS denote the vector with coordinates
bSx (v) = pSv (x) for all v ∈ S. Write LG as a two-by-two block matrix:


P Q
L=
QT R
where P , Q, and R have index pairs S × S, S × (V (G) \ S), and V (G) \ S × V (G) \ S respectively.
Then
bSx = MS bx
where


MS = I −QR−1 .
6

Proof. If x ∈ S, then bSx is the indicator vector of x and x is in the identity block of MS . Therefore,
bSx = MS bx .
If x ∈
/ S, then let bcx denote the coordinate restriction of bx to V (G) \ S. We want to show that
S
bx = −QR−1 bcx . Consider the linear system
bcx = Rp
Let H be the graph obtained by identifying all vertices in S within G to a single vertex s. Then
the vector p′ with p′s = 0 and p′v = pv for all v ∈ V (H) \ {s} is a solution to a boundary value
problem with p′s = 0 and p′x having the maximum potential of any vertex. The block matrix Q
can be viewed as mapping the potentials p′ to a flow proportional to the xs-flows on edges incident
with s. By Proposition 2.2 of [LP16], for example, the incoming flow on edges to s is equal to
the probability that an x → s random walk first visits s by crossing that edge. Grouping edges
according to their common endpoints shows that −QR−1 bcx is a scalar multiple of bSx .
However, notice that
1T (−QR−1 )bcx = (−1T Q)R−1 bcx = 1T RR−1 bcx = 1 = 1T bSx
so bSx = −QR−1 bcx , as desired.
Once one views the the qvS (e)s in the above way, it makes sense to discuss the energy of the
qvS (e)s in relation to the probabilities pSv (x). It turns out that the total energy contributed by edges
with both endpoints having potential at most p is at most a p fraction of the total energy.
Proposition 2.5. For any p ∈ (0, 1), let F be the set of edges {x, y} with maxz∈{x,y} pSv (z) ≤ p.
Then the total energy of those edges is at most a p fraction of the overall energy. More formally,
X

e∈F

ce (qvS (e))2 ≤ p

X

ce (qvS (e))2

e∈E(G)

Proof. Let H be the graph obtained by identifying S\{v} to a vertex s in G. By Fact 2.3, we can
show the desired proposition by proving the following:
X

e∈F

2
T +
ce (bTvs L+
H be ) ≤ pbvs LH bvs

for an arbitrary graph H and the subset of edges F ⊆ E(H) with maxz∈{x,y} |bTvs L+
H bzs | ≤

pbTvs L+
H bvs .

Write the sum on the left side in terms of an integral over sweep cuts. For p ∈ (0, 1), let Cp
denote the set of edges cut by the normalized potential p. More precisely, let Cp be the set of edges
T +
T +
T +
{x, y} with |bTvs L+
H bxs | ≥ pbvs LH bvs and |bvs LH bys | ≤ pbvs LH bvs . Notice that

7

X

2
ce (bTvs L+
H be )

e∈F

≤

Z

=

Z

≤

+
pbT
vs LH bvs

0

X

e∈Cq
+
pbT
vs LH bvs

ce |bTvs L+
H be |dq

1dq

0
pbTvs L+
H bvs

where the equality follows from the fact that Cq is a threshold cut for the v − s electrical flow
and the first inequality follows from splitting the contribution of e to the sum in terms of threshold
cuts. This inequality is the desired result.
Finally, we relate the weighted degrees of of vertices in Schur (G, S) to energies in G with
respect to S.
1
Definition 2.6. Let cH
v denote the sum of the conductances of edges incident with v in H.

Proposition 2.7. Let G be a graph. Consider a set S and let H = Schur(G, S). Then
cH
v =

X

G,S
2
cG
e (qv (e))

e∈E(G)

Proof. Let I be the graph obtained by identifying S \{v} to s in H. Since the effective conductance
1
of parallel edges is the sum of the conductance of those edges, cH
v = bT L+ b .
vs

I

vs

By commutativity of Schur complements, I can also be obtained by identifying S\{v} in G
before eliminating all vertices besides s and v. Let J be the graph obtained by just doing the first
step (identifying S\{v}). By definition of Schur complements,
T +
bTvs L+
I bvs = bvs LJ bvs

By Fact 2.3,
bTvs L+
J bvs = P

1
G G,S
2
e∈E(G) ce (qv (e))

Substitution therefore shows the desired result.

3

Proof of Theorem 1.5

We will deduce Theorem 1.5 from the following seemingly weaker statement regarding positive test
vectors.
1

To avoid confusion, we remind the reader that by conductances we always mean electrical conductances, i.e.,
weights in the graph, and not conductances in the sense of expansion.

8

E(G)

Theorem 3.1. Let G be a graph. Then for any vector w ∈ R≥0 ,
X

e,f ∈E

√
2
2
we wf ce cf |bTe L+
G bf | ≤ O(log n)||w||2

Theorem 1.5 can be deduced from this by a Perron-Frobenius argument.
1/2

1/2

T
Proof of Theorem 1.5. Since the matrix M = |CG BG L+
G BG CG | has nonnegative entries, there is
an eigenvector with maximum eigenvalue with nonnegative coordinates by Perron-Frobenius. Such
an eigenvector corresponds to a positive eigenvalue. Theorem 3.1 bounds the value of the quadratic
form of this eigenvector. In particular, the quadratic form is at most O(log2 n) times the ℓ2 norm
squared of the vector, as desired.

The proof hinges on the following key quantity. Define
P
√
( e∈E(G) we ce quS (e))2
P
DegreeS (u) :=
S
2
e∈E(G) ce qu (e)

The quantity DegreeS (u) may be interpreted as a measure of the sparsity of the vector (quS (e))e ,
since it is the ratio of the (weighted) ℓ21 norm of this vector and its ℓ22 norm. Note that when
S = V (G), w = 1, and G is unweighted, DegreeS (u) is simply the degree of u.
There are two parts to the proof: (1) recursively reducing the original problem to a number of
problems involving sums of simpler inner products and (2) bounding those sums. The difference
between the value of a problem and the subproblem after eliminating u is at most DegreeS (u). We
want to show that there always is a choice of u with a small value of DegreeS (u). The following
proposition shows this:
Proposition 3.2. For any {ce }e -weighted graph G, set S ⊆ V (G) with |S| ≥ 2, and nonnegative
weights {we }e∈E(G) , the following holds:
X

u∈S

DegreeS (u) ≤ O(log |S|)

X

we2

e∈E(G)

We now reduce Theorem 3.1 to this proposition by picking the vertex u with that minimizes the
summand DegreeS (u) of Proposition 3.2 and recurring on the Schur complement with u eliminated.
The summand of Proposition 3.2 is an upper bound on the decrease due to eliminating u.
Proof of Theorem 3.1 given Proposition 3.2. Define the following:
• G0 ← G, c(0) ← c, x0 ← arg minx∈V (G) DegreeS0 (x), S0 ← V (G), i ← 0.
• While |V (Gi )| > 2:
– i ←i+1

– Gi ← Schur(Gi−1 , V (Gi−1 ) \ {xi−1 })
– c(i) ← conductance vector for Gi

– Si ← V (Gi )

– xi ← arg minx∈V (Gi ) DegreeSi (x)
9

• T ←i
Let Li ← LGi and let mi = Lxi xi . We start by understanding how to express the left hand side
(i)
of the desired inequality in Gi for all i. For a vertex x ∈ V (G), let bx ∈ RV (Gi ) denote the vector
(i)
(i)
(i)
(i)
with bx (v) = pvG,Si (x) for all v ∈ V (Gi ). For an edge {x, y} ∈ V (G), let bxy = bx − by . Let
Vi :=

X

e,f ∈E(G)

√
(i) √
we ce |be(i)T L+
i bf | cf wf

We now bound Vi in terms of Vi+1 for all nonnegative integers i < T . By Fact 1.7 and
Proposition 2.4,
X
√
(i) √
Vi =
we ce |be(i)T L+
i bf | cf wf
e,f ∈E(G)

=

X

e,f ∈E(G)

≤ Vi+1 +

(i)

(i)

√
1 (i) √
(i+1)
x | cf wf
+ xe(i)T
we ce |be(i+1)T L+
i+1 bf
mi f
X

e,f ∈E(G)

√
1 (i) √
x | cf wf
we ce |xe(i)T
mi f

(i)

where xe := be (xi ). Since the xe s are scalars, we can futher simplify the above sum:


√

2

√
1 (i) √
1 

we ce |x(i)
x | cf wf =
we ce |xe(i)T
e |
mi f
mi
e∈E(G)
e,f ∈E(G)

2
X
√
1

= (i) 
we ce x(i)
e
cxi e∈E(G)
P
√ Si  2
e∈E(G) we ce qxi (e)
=
P
Si
2
e∈E(G) ce qxi (e)
X

X

= DegreeSi (xi )

where the second-to-last denominator equality follows from Proposition 2.7. Since xi minimizes
DegreeSi (xi ), Proposition 3.2 with S ← Si and G ← G implies that

log n
2
||w||2
DegreeSi (xi ) ≤ O
|Si |


log n
2
≤O
||w||2
n−i


10

Plugging this in shows that
Vi ≤ Vi+1 + O



log n
n−i



||w||22

for all i < T . Therefore, to bound V0 , it suffices to bound VT . Let ST = {a, b}. Then
VT =

X

e,f ∈E(G)

X

=

e,f ∈E(G)

=

X

e,f ∈E(G)

√
)T + (T ) √
LT bf | cf wf
we ce |b(T
e
√
√
G,Si
i
(e)|bTab L+
we ce quG,S
T bab |qui (f ) cf wf
i
|bTab L+
√ |bT L+ be |
T bf | √
cf wf
b
we ce Tab +T bTab L+
T ′ ab T +
bab LT bab
bab LT bab

≤ ||w||22

where the last line follows from Cauchy-Schwarz. Therefore,
VT ≤ ||w||22
Combining these bounds yields a harmonic sum that proves the desired result.
Now, we prove Proposition 3.2.
(i)

Proof. For each vertex v ∈ S and each integer i ∈ [0, log |S|], let Xv ⊆ E(G) denote the set of edges
(i)
(i)
(i+1)
e = {x, y} for which rvS (e) ≤ 2−i . Let T := log |S|. For each 0 ≤ i < T , let Yv = Xv \ Xv
.
(T )
(T )
Let Yv = Xv .
(i+1)
(i)
(i)
(0)
⊆ Xv . Therefore, {Yv }Ti=0 is a partition
For each v and each i ≥ 0, Xv = E(G), and Xv
of E(G) for each v ∈ S. By Cauchy-Schwarz,
P
√
X ( e∈E(G) we ce quS (e))2
P
DegreeS (u) =
S
2
e∈E(G) ce qu (e)
u∈S
u∈S
P

S
2 S
X
X
e∈E(G) ce qu (e) /ru (e)

P
ruS (e)we2 
≤
S
2
e∈E(G) ce qu (e)
X

u∈S

(i+1)

By the definition of Xu

X

u∈S




X

e∈E(G)

P

ruS (e)we2 

e∈E(G)

,

2 S
S
e∈E(G) ce qu (e) /ru (e)
P
S
2
e∈E(G) ce qu (e)

≤

X

u∈S

(i)

By the definition of Xu and Proposition 2.5,
11




X

e∈E(G)



ruS (e)we2 

T
X
i=0

P

2i+1 P

(i)
e∈Yu

ce quS (e)2

S
2
e∈E(G) ce qu (e)

!

X

u∈S




X

e∈E(G)



ruS (e)we2 

T
X
i=0

P

2i+1 P

(i)
e∈Yu

ce quS (e)2

S
2
e∈E(G) ce qu (e)

!

≤
≤

X

u∈S

X

u∈S









T
X

!

X

ruS (e)we2 

X

ruS (e)we2  (2T + 2)

X

we2

e∈E(G)

e∈E(G)



i=0

2

By Proposition 2.2,
X

u∈S




X

e∈E(G)



ruS (e)we2  (2T + 2) ≤ (6T + 6)

e∈E(G)

Combining these bounds shows that
X

u∈S

DegreeS (u) ≤ (6T + 6)

X

e∈E(G)

we2 ≤ O(log |S|)||w||22

as desired.

Acknowledgments
We would like to thank Hariharan Narayanan, Akshay Ramachandran, and Hong Zhou for many
helpful conversations.

References
[Bol13]

Béla Bollobás. Modern graph theory, volume 184. Springer Science & Business Media,
2013.

[CKM+ 11] Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and ShangHua Teng. Electrical flows, laplacian systems, and faster approximation of maximum
flow in undirected graphs. In Proceedings of the forty-third annual ACM symposium on
Theory of computing, pages 273–282. ACM, 2011.
[DKP+ 17] David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Proceedings of the
49th Annual ACM SIGACT Symposium on Theory of Computing, pages 730–742. ACM,
2017.
[HHN+ 08] Prahladh Harsha, Thomas P Hayes, Hariharan Narayanan, Harald Räcke, and Jaikumar
Radhakrishnan. Minimizing average latency in oblivious routing. In Proceedings of
the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 200–207.
Society for Industrial and Applied Mathematics, 2008.

12

[KM09]

Jonathan A Kelner and Aleksander Madry. Faster generation of random spanning trees.
In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium
on, pages 13–21. IEEE, 2009.

[KM11]

Jonathan Kelner and Petar Maymounkov. Electric routing and concurrent flow cutting.
Theoretical Computer Science, 412(32):4123–4135, 2011.

[KMP12]

Jonathan A Kelner, Gary L Miller, and Richard Peng. Faster approximate multicommodity flow using quadratically coupled flows. In Proceedings of the forty-fourth annual
ACM symposium on Theory of computing, pages 1–18. ACM, 2012.

[KS16]

Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians:
Fast, sparse, and simple. CoRR, abs/1605.02353, 2016.

[LN09]

Gregory Lawler and Hariharan Narayanan. Mixing times and l p bounds for oblivious
routing. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics,
pages 66–74. Society for Industrial and Applied Mathematics, 2009.

[LP16]

Russell Lyons and Yuval Peres. Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press,
New York, 2016.

[LRS13]

Yin Tat Lee, Satish Rao, and Nikhil Srivastava. A new approach to computing maximum flows using electrical flows. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 755–764. ACM, 2013.

[Mad13]

Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual
Symposium on, pages 253–262. IEEE, 2013.

[MST15]

Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random
spanning trees and the effective resistance metric. In Proceedings of the Twenty-Sixth
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2019–2036. Society for
Industrial and Applied Mathematics, 2015.

[Rac02]

Harald Racke. Minimizing congestion in general networks. In Foundations of Computer
Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 43–52. IEEE,
2002.

[SS11]

Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances.
SIAM Journal on Computing, 40(6):1913–1926, 2011.

[ST04]

Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph
partitioning, graph sparsification, and solving linear systems. In Proceedings of the
thirty-sixth annual ACM symposium on Theory of computing, pages 81–90. ACM, 2004.

13

