January 5, Wednesday 14:15,
Jacobs Building Room 303
Title: parameterized complexity of graph separation problems: current results and further challenges
Lecturer : Igor Razgon
Lecturer homepage : http://www.cs.le.ac.uk/people/ir45/
Affiliation : Department of Computer Science, University of Leicester
consider an NP-hard optimization problem with input size $n$ which is associated with a parameter $k$ (the parameter may be, for instance, the maximum allowed output size). We say that this problem is fixed-parameter tractable (FPT) if it can be solved by a fixed-parameter algorithm, i.e. an algorithm whose runtime is uniformly polynomial in $n$, though exponential (or even superexponential) in $k$. Examples of such runtimes are $O((2^k)*n)$, $O(3^k+n^2)$ and so on. When $k$ is small, the hope is that the respective dependence on $k$ is also small. In this case, an NP-hard optimization problem can be solved in a low polynomial time. Thus, if the considered parameter is reasonably small in practical applications, fixed-parameter algorithms can be used as a method of coping with NP-hardness, both precise (unlike approximation algorithms) and efficient (unlike ordinary brute-force algorithms).