Finding small stabilizers for unstable graphs
| Speaker: | Andrew Childs |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
A
vertex
v
of
a
graph
G
is
called
inessential
if
there
exists
a
maximum
matching
in
G
that
exposes
v.
G
is
said
to
be
stable
if
the
set
of
its
inessential
vertices
forms
a
stable
set.
Stable
graphs
play
a
key
role
in
network
bargaining
games
where
we
are
given
a
set
of
players
represented
as
vertices
of
a
graph
G,
and
a
set
of
possible
deals
between
players
represented
by
the
edges
of
G.
Kleinberg
and
Tardos
[STOC
’08]
defined
the
notion
of
a
balanced
outcome
for
a
network
bargaining
game,
and
proved
that
a
balanced
outcome
exists
if
and
only
if
the
correspondent
graph
G
is
stable.
This
connection
motivates
the
optimization
problem
of
finding
a
minimum
cardinality
stabilizer
of
a
given
unstable
graph
G,
that
is
a
subset
of
edges
F
such
that
G\F
is
stable.
In
this
talk
we
prove
some
structural
results
about
this
problem
and
develop
efficient
approximation
algorithms
for
sparse
graphs.
Joint
work
with
A.Bock,
K.Chandrasekaran,
J.Koenemann,
B.Peis