• Calendar

January 4, Tuesday
12:00 – 13:30

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). Graph separation problems comprise a large class of problems where the objective is to remove the smallest set of vertices (or edges) from the given graph so that certain structures in the graph are broken. Examples of such structures: paths between certain pairs of vertices, directed cycles, odd cycles, etc. In real-world applications of these problems it is often reasonable to assume that the separator (i.e. the set of vertices removed) is much smaller than the size of the whole graph. It is therefore natural to solve these problems by the means of fixed-parameter algorithms. However, designing good fixed-parameter algorithms for these problems is a very tricky task. In fact, despite many years of active research, for a number of separation problems it was not even clear if they are FPT. In this talk I will overview current results related to design of fixed-parameter algorithms for separation problems. To make the talk self-contained, I will start from definition of the fixed-parameter algorithm and provide a simple example of such algorithm. Then I will informally describe a fixed parameter algorithm for the multiway cut problem. Then I will show how the methodology underlying this algorithm has helped to resolve fixed-parameter tractability of a number of challenging problems that stayed open for many years despite attempts of many researchers. Finally, I will overview some challenging questions that are still open.