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 : Cork University, Ireland


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.