^October November – 2008 ^December

Fixed-parameter algorithms provide an alternative methodology of coping with NP-hardness that allows to solve hard optimization problems exactly and in a low-polynomial time.The necessary condition for design of a fixed- parameter algorithm is the presence of a parameter associated with the given problem. The time complexity of a fixed-parameter algorithm can be represented in a form $O(f(k)*n^c)$, where $k$ is the parameter, $f(k)$ is an exponential function on the parameter, $c$ is a constant usually not greater than 3. Thus a fixed-parameter algorithm is exponential in the parameter but polynomial in the input size. The low-polynomial time is achieved for small values of $k$.

The design of fixed-parameter algorithms was inspired by observation that in areas like bioinformatics and network design many hard problems are associated with natural parameters that in practice are very small.

Problems that admit fixed-parameter algorithms are called fixed-parameter tractable (FPT) and the area of Theoretical Computer Science studying various aspects of fixed-parameter tractability and intractability is called Parameterized Complexity. One of the key questions investigated in the area is classification of problems i.e. telling whether a particular problem is FPT. The community has identified a number of the most challenging open questions related to classification of problems. One of such questions is understanding whether the following problem is FPT: given a 2-CNF formula, is it possible to remove at most $k$ clauses so that the resulting formula becomes satisfiable? This problem is called 2-CNF deletion. It attracted attention of researchers due to a large number of potential applications of this problem. Despite a number of attempts to solve the problem, the status of fixed-parameter tractability of the problem remained unresolved for more than 10 years. The fixed-parameter tractability of the problem has been confirmed in Razgon, O'Sullivan "Almost 2-SAT is fixed-parameter tractable", ICALP 2008.

In this talk I will briefly introduce the area of Parameterized Complexity and overview main ideas of the fixed-parameter algorithm for the 2-CNF deletion problem. The talk is designed for the audience completely unfamiliar with the area of Parameterized Complexity.