The matching structure behind the composition of strips
| Speaker: | Yuri Faenza |
|---|---|
| Affiliation: | Università di Roma "Tor Vergata" |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
A strip is a triple (G,a,b), where G is a simple, undirected graph and a,b are vertices of G whose neighborhood is a clique. The composition of strips takes as input a set of strips, and outputs a graph. Chudnovsky and Seymour showed that strips from a suitable family form the building blocks of a wide class of claw-free graphs, meaning that every graph in this class can be expressed as the composition of strips from the family, and conversely a composition of those strips always produces a claw-free graph from this class. One of the reasons why claw-free graphs attracted the interest of many researchers is that they generalize line graphs, thus the Maximum (Weighted) Stable Set problem on claw-free graphs generalizes the maximum (weighted) matching problem.
In
this
talk
we
show
that,
in
fact,
MWSS
problems
on
graphs
that
are
the
composition
of
strips
share
a
common
matching-like
structure,
both
from
an
algorithmic
and
from
a
polyhedral
point
of
view.
We
also
address
a
number
of
applications
of
these
results,
mainly
back
in
the
context
of
claw-free
graphs,
including
extended
formulations
and
a
polytime
separation
routine
for
the
stable
set
polytope
of
claw-free
graphs,
and
a
new
combinatorial
algorithm
for
the
MWSS
on
claw-free
graphs.
These
latter
results
use
a
novel
algorithmic
decomposition
theorem
for
claw-free
graphs
with
stability
number
at
least
4.
These
results
are
part
of
the
speaker's
PhD
thesis,
and
are
a
joint
work
with
G.Oriolo
and
G.
Stauffer.