Terminal Backup, 3D Matching and Covering Cubic Graphs
| Speaker: | Elliot Anshelevich |
|---|---|
| Affiliation: | Rensselaer Polytechnic Institute |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We
define
a
problem
called
Simplex
Matching,
and
show
that
it
is
solvable
in
polynomial
time.
While
Simplex
Matching
is
interesting
in
its
own
right
as
a
nontrivial
extension
of
non-bipartite
min-cost
matching,
its
main
value
lies
in
many
(seemingly
very
different)
problems
that
can
be
solved
using
our
algorithm.
For
example,
suppose
that
we
are
given
a
graph
with
terminal
nodes,
non-terminal
nodes,
and
edge
costs.
Then,
the
Terminal
Backup
problem,
which
consists
of
finding
the
cheapest
forest
connecting
every
terminal
to
at
least
one
other
terminal,
is
reducible
to
Simplex
Matching.
Simplex
Matching
is
also
useful
for
various
tasks
that
involve
forming
groups
of
at
least
two
members,
such
as
project
assignment
and
variants
of
facility
location.
In
an
instance
of
Simplex
Matching,
we
are
given
a
hypergraph
H
with
edge
costs,
and
edge
size
at
most
three.
We
show
how
to
find
the
min-cost
perfect
matching
of
H
efficiently,
if
the
edge
costs
obey
a
simple
and
realistic
inequality
that
we
call
the
Simplex
Condition.
The
algorithm
we
provide
is
relatively
simple
to
understand
and
implement,
but
difficult
to
prove
correct.
In
the
process
of
this
proof
we
show
some
powerful
new
results
about
covering
cubic
graphs
with
simple
combinatorial
objects.