Friday, October 8, 2010 — 3:30 PM to 4:30 PM EDT

Graph Sparsifiers

Speaker: Nick Harvey
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Can a dense graph be approximated by a sparse graph? Surprisingly, yes. A "sparsifier" of a graph is a weighted subgraph that approximates the weight of every cut, up to a factor (1+eps). Benczur and Karger showed that, for any graph on n nodes, sparsifiers with only O(n log n / eps^2) edges exist, and furthermore they can be constructed efficiently. 

Sparsifiers have numerous applications, including fast algorithms for network flow and cut problems. Related constructions play a key role in Spielman and Teng's remarkable algorithm for solving diagonally dominant linear systems in nearly linear time. 
We give a new approach to constructing sparsifiers, which simplifies and clarifies the original work of Benczur and Karger. Our algorithm independently samples every edge uv with probability inversely proportional to the edge-connectivity between u and v. The fact that this approach produces a sparsifier resolves an open question of Benczur and Karger. The resulting sparsifiers have O(n log^2 n / eps^2) edges. Our proofs are based on extensions of Karger's contraction algorithm for computing minimum cuts in a graph. 

Joint work with Isaac Fung.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2019 (160)
    1. November (13)
    2. October (18)
    3. September (15)
    4. August (9)
    5. July (17)
    6. June (18)
    7. May (16)
    8. April (9)
    9. March (24)
    10. February (13)
    11. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)