Almost 2-SAT is fixed-parameter tractable.
Igor RazgonBarry O'SullivanPublished in: J. Comput. Syst. Sci. (2009)
Keyphrases
- fixed parameter tractable
- parameterized complexity
- np complete
- satisfiability problem
- sat problem
- computational problems
- np hard
- global constraints
- sat solvers
- conjunctive queries
- bounded treewidth
- phase transition
- propositional satisfiability
- search algorithm
- abstract argumentation
- constraint satisfaction
- max sat
- special case
- computational complexity
- constraint satisfaction problems
- symmetry breaking
- lower bound