cms

---

Fixed-parameter computation is a methodology of coping with NP-hardness that, under certain conditions, allows to solve hard optimization problems both precisely and efficiency. According to this methodology, a problem is associated with a parameter $k$ and solved by an exponential time algorithm whose exponential part solely depends on the parameter while dependnency on the input size $n$ is uniformly polynomial, i.e. the degree of the polynomial is a constant, usually not greater than 3. When the parameter is small, we get a low-polynomial algorithm solving an NP-hard problem to optimality. Problems that can be solved in this way are called fixed-parameter tractable (FPT). The parameter choice depends on the particular application and can be, for example, maximum or minimum allowed size of the output or some structural measure of the input, e.g. treewidth.

This talk is related to parameterization of graph separation problems where the task is to find the smallest set of vertices separating some predefined pairs of terminals, possibly under additional constraints. In the first part of this talk, I will informally define a fixed-parameter algorithm and describe two fixed-parameter algorithms for the Vertex Cover problem. In the second part of the talk I will describe an algorithm for solving the multiway cut problem and show how the main idea of this algorithm has helped to show the fixed-parameter tractability of such challenging graph separation problems as Directed Feedback Vertex Set, minimum 2CNF deletion, and Multicut. In the final part of the talk I will outline the current challenges related to the parameterization of graph separation problems. The main challenge is kernelization of these problems, i.e. designing a polynomial-time procedure that squeezes the initial instance of the problem so that its size polynomially depends on the parameter. Such procedure being applied at the preprocessing stage can significantly enhance any algorithm solving the given problem and hence understanding kernelizability of parameterized problems is a research direction of a great practical importance.

The talk is self-contained and assumes no prior familiarity with the area.

---