### 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).