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.