March 25, Wednesday 14:15, Room 303, Jacobs
Fixed-parameter algorithms for graph
separation problems
Lecturer : Igor Razgon
Lecturer homepage : http://www.cs.ucc.ie/~ir2/
Affiliation :
Abstract:
Fixed-parameter
algorithms are methods of coping with NP-hardness
that can be viewed as a
compromise between efficient and imprecise
approximation algorithms and
inefficient but precise exponential
time algorithms.
Fixed-parameter algorithms are both precise and efficient
(i.e.
their runtime is polynomial in the input size). Since they solve
NP-hard problems, there
is a price for that: their runtime is exponential
in terms of a parameter
associated with a problem. The point is that when
the parameter is small,
the exponential part of the runtime becomes a
(hopefully)
negligible multiplicative or additive constant and as a result
an NP-hard problem can be
solved in a low polynomial time. Problems that
can be solved in the above
way are called Fixed-Parameter Tractable (FPT).
At this moment, there
are many problems known to be FPT and many problems
known to be not FPT unless
some widely believed conjecture in the
complexity theory fails. On the
other hand, there are many problems whose
fixed-parameter tractability status is
a very challenging open question
resisting attacks of many
researchers during many years. Incidentally,
most of such
"stubborn" problems can be considered as graph separation
problems or closely related to
them. In a graph separation
problem we are given a graph
and a set of source-sink pairs and we are
asked to compute the
smallest set of vertices or edges (sometimes
subject to additional
constraints) whose removal separates each
sink from the respective
source. This talk will address the design of
fixed-parameter algorithms for such
problems.
I will start the talk
from a brief introduction into the area of
fixed-parameter tractability in which
I will introduce the relevant
terminology and show how to design
a simple fixed-parameter algorithm.
Then, in the main part
of my talk, I will introduce two recent
methodologies that allowed to design
fixed-parameter algorithms for a
number of challenging
problems. The talk is designed for a general
Computer Science
audience and thus does not require any prior
familiarity with the area of
fixed-parameter algorithms.