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 I will overview a number of past results related to design of
fixed-parameter for challenging problems based on graph separation. Then,
in the main part of my talk, I will present a recent methodology that
allows an easy designm of fixed-parameter algorithms for a wide range of
separation problems and solves a number of open questions in the area. The
material of the main part of my talk is based on my STACS 2010 paper.
A more detailed description of the paper and its .pdf copy are available
at http://www.cs.ucc.ie/~ir2/overview.html item 1.3.
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.