Title: Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
| Speaker: | Chandra Chekuri |
| Affiliation: | University of Illinois, Urbana-Champaign |
| Zoom: | Please email Emma Watson |
Abstract:
The
densest
subgraph
problem
in
a
graph
(DSG),
in
the
simplest
form,
is
the
following.
Given
an
undirected
graph
G
=
(V,
E)
find
a
subset
S
of
vertices
that
maximizes
the
ratio
|E(S)|/|S|
where
E(S)
is
the
set
of
edges
with
both
endpoints
in
S.
DSG
and
several
of
its
variants
are
well-studied
in
theory
and
practice
and
have
many
applications
in
data
mining
and
network
analysis.
We
study
fast
algorithms
and
structural
aspects
of
DSG
via
the
lens
of
supermodularity.
For
this
we
consider
the
densest
supermodular
subset
problem
(DSS):
given
a
non-negative
supermodular
function
f
over
a
ground
set
V,
maximize
f(S)/|S|.
For
DSG
we
describe
a
simple
flow-based
algorithm
that
outputs
a
(1−\epsilon)-approximation
in
deterministic
O(m
polylog(n)/\epsilon)
time
where
m
is
the
number
of
edges.
Greedy
peeling
algorithms
have
been
very
popular
for
DSG
and
several
variants
due
to
their
efficiency,
empirical
performance,
and
worst-case
approximation
guarantees.
We
describe
a
simple
peeling
algorithm
for
DSS
and
analyze
its
approximation
guarantee
in
a
fashion
that
unifies
several
existing
results.
Boob
et
al.
developed
an
iterative
peeling
algorithm
for
DSG
which
appears
to
work
very
well
in
practice,
and
made
a
conjecture
about
its
convergence
to
optimality.
We
affirmatively
answer
their
conjecture,
and
in
fact
prove
that
a
natural
generalization
of
their
algorithm
converges
for
any
supermodular
function
f;
the
key
to
our
proof
is
to
consider
an
LP
formulation
that
is
derived
via
the
Lovász
extension
of
a
supermodular
function
which
is
inspired
by
the
LP
relaxation
of
Charikar
that
has
played
an
important
role
in
several
developments.
This
is
joint
work
with
Kent
Quanrud
and
Manuel
Torres.
The
paper
appeared
in
ACM-SIAM
SODA
2022
and
is
available
at http://chekuri.cs.illinois.edu/papers/densest-subgraph-soda22.pdf