Title: FPT meets discharging
| Speaker: | Marthe Bonamy |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
An
NP-hard
problem
is
Fixed
Parameter
Tractable
(FPT)
w.r.t.
a
given
parameter
if
any
instance
can
be
reduced
in
polynomial-time
to
an
instance
of
size
bounded
by
a
function
of
the
parameter.
The
discharging
methods
are
typically
used
to
prove
combinatorial
theorems
(most
notably
the
Four
Colour
Theorem).
These
two
areas
are
usually
considered
independently,
though
they
have
enough
in
common
that
it
is
tempting
to
look
for
applications
of
one
into
the
other.
Here
we
investigate
two
recent
results
which
were
obtained
through
this
comparison.
The
first
one
deals
with
the
Feedback
Vertex
Set
problem
(how
many
vertices
do
we
have
to
remove
from
a
graph
to
obtain
a
forest?)
parameterized
with
the
size
of
the
solution
(is
removing
k
vertices
enough?),
in
the
setting
of
planar
graphs.
We
present
a
linear-time
pre-processing
algorithm
which
outputs
a
planar
graph
on
at
most
13k
vertices,
obtained
with
Lukasz
Kowalik
(University
of
Warsaw).
The
second
one
deals
with
colouring
the
square
of
a
planar
graph
with
given
girth.
We
present
an
FPT-inspired
proof
of
a
2007
conjecture
that
the
square
of
a
planar
graph
of
girth
5
and
large
enough
maximum
degree
requires
only
one
more
colour
than
the
obvious
lower
bound,
obtained
with
Dan
Cranston
(Virginia
Commonwealth
University)
and
Luke
Postle
(University
of
Waterloo).