Transcript PPTX - UBC Department of Computer Science

Graph Sparsifiers by
Edge-Connectivity and
Random Spanning Trees
Nick Harvey
University of Waterloo
Department of Combinatorics and Optimization
Joint work with Isaac Fung
What are sparsifiers?
Weighted subgraphs that approximately preserve some properties
• Approximating all cuts
[BSS’09]
– Sparsifiers: number of edges = O(n log n /²2) ,
every
Poly(n)cut approximated within 1+². [BK’96]
– O~(m) time algorithm to construct them
• Spectral approximation
n = # vertices
m = # edges
[BSS’09]
– Spectral sparsifiers: number of edges = O(n log n /²2),
“entire spectrum” approximated within 1+². [SS’08]
Poly(n)
Laplacian matrix of G
Laplacian matrix of Sparsifier
– O~(m) time algorithm to construct them
Why are sparsifiers useful?
n = # vertices
m = # edges
• Approximating all cuts
– Sparsifiers: fast algorithms for cut/flow problem
Problem
Approximation
Runtime
Reference
Min st Cut
1+²
O~(n2)
BK’96
Sparsest Cut
O(log n)
O~(n2)
BK’96
Max st Flow
1
O~(m+nv)
KL’02
O~(n2)
AHK’05
O~(m+n3/2)
KRV’06
Sparsest Cut
O~(m+n3/2+²)
S’09
Perfect Matching in n/a
Regular Bip. Graphs
O~(n1.5)
GKK’09
Sparsest Cut
O~(m+n1+²)
M’10
Sparsest Cut
Sparsest Cut
O(log2 n)
v = flow value
Our Motivation
• BSS algorithm is very mysterious, and
“too good to be true”
• Are there other methods to get sparsifiers
with only O(n/²2) edges?
• Wild Speculation: Union of O(1/²2) random
spanning trees gives a sparsifier (if weighted appropriately)
– True for complete graph [GRV ‘08]
• Corollary of our Main Result:
The Wild Speculation is false, but the union of
O(log2 n/²2) random spanning trees gives a
sparsifier
Formal problem statement
n = # vertices
m = # edges
• Design an algorithm such that
• Input: An undirected graph G=(V,E)
• Output: A weighted subgraph H=(V,F,w),
where FµE and w : F ! R
• Goals:
# edges between U and V\U in G
weight of edges between U and V\U in H
• |||±
· ²² |±(U)|
|±G(U)|
|±(U)|
w(±(U))
G(U)| - w(±
H(U)) || ·
(We only want to preserve cuts)
• |F| = O(n log n / ²2)
• Running time = O~( m / ²2 )
8U µ V
Sparsifying Complete Graph
• Sampling: Construct H by sampling every edge of G
with prob p=100 log n/n. Give each edge weight 1/p.
• Properties of H:
• # sampled edges = O(n log n)
• |±G(U)| ¼ |±H(U)| 8U µ V
• So H is a sparsifier of G
Proof Sketch
• Consider any cut ±G(U) with |U|=k. Then |±G(U)|¸kn/2.
• Let Xe = 1 if edge e is sampled. Let X = e2C Xe = |±H(U)|.
• Then ¹ = E[X] = p|±(U)| ¸ 50 k log n.
• Say cut fails if |X-¹| ¸ ¹/2.
Key Ingredients
• So Pr[ cut fails ] · 2 exp( - ¹/12 ) · n-4k.
• # of cuts with |U|=k is
.
• So Pr[ any cut fails ] · k n-4k
Chernoff Bound
Bound on # small cuts
-2.
< k n-3k < nUnion
bound
Exponentially
decreasing
Exponentially
increasing
• Whp, every
U has ||±
< p|±(U)|/2
H(U)| - p|±(U)||
probability of failure
# of bad events
Generalize to arbitrary G?
Eliminate most of these
Keep this
• Can’t sample edges with same probability!
• Idea [BK’96]
Sample low-connectivity edges with high probability,
and high-connectivity edges with low probability
Non-uniform sampling algorithm
• Input: Graph G=(V,E), parameters pe 2 [0,1]
• Output: A weighted subgraph H=(V,F,w),
where FµE and w : F ! R
For i=1 to ½
For each edge e2E
With probability pe,
Add e to F
Increase we by 1/(½pe)
• Main Question: Can we choose ½ and pe’s
to achieve sparsification goals?
[BK’96]
Non-uniform sampling algorithm
[BK’96]
• Input: Graph G=(V,E), parameters pe 2 [0,1]
• Output: A weighted subgraph H=(V,F,w),
where FµE and w : F ! R
For i=1 to ½
For each edge e2E
With probability pe,
Add e to F
Increase we by 1/(½pe)
• Claim: H perfectly approximates G in expectation!
• For any e2E, E[ we ] = 1
) For every UµV, E[ w(±H(U)) ] = |±G(U)|
• Goal: Show every w(±H(U)) is tightly concentrated
Assume ² is constant
Prior Work
• Benczur-Karger ‘96
Similar to edge connectivity
– Set ½ = O(log n), pe = 1/“strength” of edge e
(max k s.t. e is contained in a k-edge-connected vertex-induced subgraph of G)
– All cuts are preserved
– e pe · n ) |F| = O(n log n)
– Running time is O(m log3 n)
(# edges in sparsifier)
• Spielman-Srivastava ‘08
– Set ½ = O(log n), pe = 1/“effective conductance” of edge e
(view G as an electrical network where each edge is a 1-ohm resistor)
–
–
–
–
H is a spectral sparsifier of G ) all cuts are preserved
e pe = n-1 ) |F| = O(n log n)
(# edges in sparsifier)
O(m log3 n)
50
Running time is O(m log n)
[Koutis-Miller-Peng ’10]
Uses “Matrix Chernoff Bound”
Our Work
• Fung-Harvey ’10
Assume ² is constant
(independentlyHariharan-Panigrahi ‘10)
– Set ½ = O(log2 n), pe = 1/edge-connectivity of edge e
(min size of a cut that contains e)
– Edge-connectivity ¸ max { strength, effective conductance }
– e pe · n ) |F| = O(n log2 n)
Why?
Pr[ e 2 T ] = effective resistance of e
– Running time is O(m log2 n)
edges are negatively correlated
) Chernoff bound still works
– Advantages:
• Edge connectivities natural, easy to compute
• Faster than previous algorithms
• Implies sampling by edge strength, effective resistances,
or random spanning trees works
– Disadvantages:
• Extra log factor, no spectral sparsification
Our Work
• Fung-Harvey ’10
Assume ² is constant
(independentlyHariharan-Panigrahi ‘10)
– Set ½ = O(log2 n), pe = 1/edge-connectivity of edge e
(min size of a cut that contains e)
– Edge-connectivity ¸ max { strength, effective conductance }
– e pe · n ) |F| = O(n log2 n)
– Running time is O(m log2 n)
– Advantages:
• Edge connectivities natural, easy to compute
• Faster than previous algorithms
• Implies sampling by edge strength, effective resistances…
• Extra trick: Can shrink |F| to O(n
O(n log
logn)
n) by using
Benczur-Karger to sparsify our sparsifier!
– Running time is O(m log2 n) + O~(n)
Our Work
• Fung-Harvey ’10
Assume ² is constant
(independentlyHariharan-Panigrahi ‘10)
– Set ½ = O(log2 n), pe = 1/edge-connectivity of edge e
(min size of a cut that contains e)
– Edge-connectivity ¸ max { strength, effective conductance }
– e pe · n ) |F| = O(n log2 n)
– Running time is O(m log2 n)
– Advantages:
• Edge connectivities natural, easy to compute
• Faster than previous algorithms
• Implies sampling by edge strength, effective resistances…
• Panigrahi ’10
– A sparsifier with O(n log n /²2) edges, with running time
O(m) in unwtd graphs and O(m)+O~(n/²2) in wtd graphs
• Notation: kuv = min size of a cut separating u and v
• Main ideas:
– Partition edges into connectivity classes
E = E1 [ E2 [ ... Elog n where Ei = { e : 2i-1·ke<2i }
– Prove weight of sampled edges that each cut
takes from each connectivity class is about right
– Key point: Edges in ±(U)ÅEi have nearly same weight
– This yields a sparsifier
U
Prove weight of sampled edges that each cut
takes from each connectivity class is about right
• Notation:
• C = ±(U) is a cut
• Ci = ±(U) Å Ei is a cut-induced set
• Need to prove:
C1
C2
C3
C4
• Notation: Ci = ±(U) Å Ei is a cut-induced set
8 cut-induced set Ci
Prove
• Key Ingredients
• Chernoff bound: Prove
small
• Bound on # small cuts: Prove
#{ cut-induced sets Ci induced by a small cut |C| }
is small.
• Union bound: sum of failure probabilities is small,
so probably no failures.
C1
C2
C3
C4
Counting Small Cut-Induced Sets
• Theorem: Let G=(V,E) be a graph. Fix any BµE.
Suppose ke¸K for all e in B. (kuv = min size of a cut separating u and v)
Then, for every ®¸1,
|{ ±(U) Å B : |±(U)|·®K }| < n2®.
• Corollary: Counting Small Cuts [K’93]
Let G=(V,E) be a graph.
Let K be the edge-connectivity of G. (i.e., global min cut value)
Then, for every ®¸1,
|{ ±(U) : |±(U)|·®K }| < n2®.
(Slightly unfair)
Comparison
• Theorem: Let G=(V,E) be a graph. Fix any BµE.
Suppose ke¸K for all e in B. (kuv = min size of a cut separating u and v)
Then
|{ ±(U) Å B : |±(U)|·c }| < n2c/K
8c¸1.
• Corollary [K’93]: Let G=(V,E) be a graph.
Let K be the edge-connectivity of G. (i.e., global min cut value)
Then,
|{ ±(U) : |±(U)|·c }| < n2c/K
8c¸1.
• How many cuts of size 1?
Theorem says < n2, taking K=c=1.
Corollary, says < 1, because K=0.
(Slightly unfair)
Comparison
• Theorem: Let G=(V,E) be a graph. Fix any BµE.
Suppose ke¸K for all e in B. (kuv = min size of a cut separating u and v)
Then
|{ ±(U) Å B : |±(U)|·c }| < n2c/K
8c¸1.
• Corollary [K’93]: Let G=(V,E) be a graph.
Let K be the edge-connectivity of G. (i.e., global min cut value)
Then,
|{ ±(U) : |±(U)|·c }| < n2c/K
8c¸1.
• Important point: A cut-induced set is a subset of edges.
Many cuts can induce the same set.
±(U)
±(U’)
Algorithm for Finding a Min Cut
[K’93]
• Input: A graph
• Output: A minimum cut (maybe)
• While graph has  2 vertices
– Pick an edge at random
– Contract it
• End While
• Output remaining edges
• Claim: For any min cut, this algorithm outputs
it with probability ¸ 1/n2.
• Corollary: There are · n2 min cuts.
Finding a Small
Cut-Induced
Set
Splitting Off
• Input:
graph
G=(V,E),
and BµE
Replace
edgesA{u,v}
and {u’,v}
with {u,u’}
v
v
• Output:
cut-induced subset
of B u u’
while
preservingAedge-connectivity
u
u’
Between
all vertices
• While
graphother
has than
 2 vvertices
Wolfgang Mader
– If some vertex v has no incident edges in B
• Split-off all edges at v and delete v
– Pick an edge at random
– Contract it
• End While
• Output remaining edges in B
• Claim: For any min cut-induced subset of B, this
algorithm outputs it with probability >1/n2.
• Corollary: There are <n2 min cut-induced subsets of B
Sparsifiers from Random Spanning Trees
• Let H be union of ½=log2 n uniform random spanning trees,
where we is 1/(½¢(effective resistance of e))
• Then all cuts are preserved and |F| = O(n log2 n)
• Why does this work?
– PrT[ e 2 T ] = effective resistance of edge e [Kirchoff 1847]
– Similar to usual independent sampling algorithm,
with pe = effective resistance of e
– Key difference: edges in a random spanning tree are
not independent, but they are negatively correlated!
[BSST 1940]
– Chernoff bounds still work. [Panconesi, Srinivasan 1997]
Sparsifiers from Random Spanning Trees
• Let H be union of ½=log2 n uniform random spanning trees,
where we is 1/(½¢(effective resistance of e))
• Then all cuts are preserved and |F| = O(n log2 n)
• How is this different than independent sampling?
– Consider an n-cycle. There are n/2 disjoint cuts of size 2.
– When ½=1, each cut has constant prob of having no edges
) need ½=(log n) to get a connected graph
– With random trees, get connectivity after just one tree
– Are O(1) trees are enough to preserve all cuts?
– No! ( log n ) trees are required
Conclusions
• Graph sparsifiers important for fast algorithms and some
combinatorial theorems
• Sampling by edge-connectivities gives a sparsifier
with O(n log2 n) edges in O(m log2 n) time
– Improvements: O(n log n) edges in O(m) + O~(n) time
[Panigrahi ‘10]
• Sampling by effective resistances also works
) sampling O(log2 n) random spanning trees
gives a sparsifier
Questions
• Improve log2 n to log n?
• Sampling o(log n) random trees gives a sparsifier
with o(log n) approximation?