Almost 2-SAT is Fixed-Parameter Tractable

Igor Razgon Barry O'Sullivan

Published in: CoRR (2008)

Keyphrases

fixed parameter tractable
parameterized complexity
np complete
satisfiability problem
computational problems
np hard
sat problem

global constraints
sat solvers
bounded treewidth
conjunctive queries
search algorithm
propositional satisfiability
phase transition

abstract argumentation
vertex set
max sat
computational complexity
symmetry breaking
knowledge representation

logic programming
constraint satisfaction problems
directed acyclic graph
optimal solution
branch and bound
temporal logic