Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable.
Konstantin MakarychevYury MakarychevYuan ZhouPublished in: FOCS (2015)
Keyphrases
- fixed parameter tractable
- np complete
- symmetry breaking
- parameterized complexity
- constraint satisfaction problems
- global constraints
- computational problems
- constraint satisfaction
- sat problem
- constraint programming
- np hard
- ordering heuristics
- satisfiability problem
- constraint propagation
- arc consistency
- computational complexity
- conjunctive queries
- bounded treewidth
- search algorithm
- graph coloring
- phase transition
- relational databases
- search tree
- sat encodings
- first order logic
- database