On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
| Speaker: | Andreas Feldmann |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
The
bottleneck
of
the
currently
best
known
approximation
algorithms
for
the
NP-hard
Steiner
tree
problem
is
the
solution
of
its
large,
so
called
hypergraphic,
linear
programming
relaxation
(HYP).
Hypergraphic
LPs
are
NP-hard
to
solve
exactly,
and
it
is
a
formidable
computational
task
to
even
approximate
them
sufficiently
well.
We
focus
on
another
well-studied
but
poorly
understood
LP
relaxation
of
the
problem:
the
bidirected
cut
relaxation
(BCR).
This
LP
is
compact,
and
can
therefore
be
solved
efficiently.
Its
integrality
gap
is
known
to
be
greater
than
1.161,
and
while
this
is
widely
conjectured
to
be
close
to
the
real
answer,
only
a
(trivial)
upper
bound
of
two
is
known.
We
give
an
efficient
constructive
proof
that
BCR
and
HYP
are
polyhedrally
equivalent
in
instances
that
do
not
have
an
(edge-induced)
claw
on
Steiner
vertices;
i.e.,
instances
that
do
not
contain
a
Steiner
vertex
with
3
Steiner
neighbours.
This
is
a
significant
step
forward
from
the
previously
known
equivalence
for
(so
called
quasi-bipartite)
instances
in
which
Steiner
vertices
form
an
independent
set.