Speaker
Prof.
Stefan Szeider
(Vienna University of Technology)
Description
Parameterized complexity is a new framework for the
theoretical analysis of computational problems. It
considers -- in addition to the problem input size -- a
secondary measurement, the parameter. The parameter
can represent a qualitative aspect of the input and
indicate how well the input is structured. This two-
dimensional setting admits a more fine-grained worst-
case complexity analysis, with the potential of being
more realistic than the one-dimensional setting of
classical complexity theory. The central notion of
parameterized complexity is fixed-parameter tractability
(FPT) which refers to solvability in time f(k)n^c, where n
denotes the input size, f is some function of the
parameter k, and c is a constant. Fixed-parameter
tractability extends the classical notion of polynomial-
time tractability. In this talk I will discuss some recent
parameterized complexity results for the propositional
satisfiability problem (SAT). In particular, I will focus on
three groups of parameters:
(i) parameters that represent the distance from a
tractable subproblem; the distance can be measured in
terms of the size of a smallest backdoor set, (ii)
parameters that represent decomposability, such as the
treewidth of graphical representations of formulas, and
(iii) parameters that represent locality, such as the
number of variables that can be flipped within a single
step of a local search algorithm.
Finally, I will discuss how parameterized complexity can
provide performance guarantees for polynomial-time
preprocessing, by means of the notion of "kernelization".
Primary author
Prof.
Stefan Szeider
(Vienna University of Technology)
