12:00 – 14:00
Fixed-Parameter Tractability of the 2-CNF Deletion problem
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.