On fixed-parameter tractable parameterizations of SAT

Stefan Szeider

in Theory and Applications of Satisfiability, 6th International Conference, SAT 2003, Selected and Revised Papers, Eds.: E. Giunchiglia and A. Tacchella, Lecture Notes in Computer Science 2919, pp. 188-202, Springer Verlag, 2004.

Download:  [paper ps]   [paper pdf]

Abstract:

We survey and compare parameterizations of SAT in the framework of Parameterized Complexity (Downey and Fellows, Springer, New York, 1999). In particular, we consider
  • parameters based on structural graph decompositions (tree-width, branch-width, and clique-width),
  • a parameter emerging from matching theory (maximum deficiency), and
  • a parameter defined by translating clause-sets into pure-implicational formulas.


[back to Stefan Szeider's homepage]