Tractable Structures for Constraint Satisfaction with Truth TablesReport as inadecuate

Tractable Structures for Constraint Satisfaction with Truth Tables - Download this document for free, or read online. Document in PDF available to download.

1 DCSIT - Department of Computer Science and Information Theory

Abstract : The way the graph structure of the constraints influences the complexity of constraint satisfaction problems CSP is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer depends also on how the constraints are represented in the input. We study this question for the truth table representation of constraints. We introduce a new hypergraph measure adaptive width and show that CSP with truth tables is polynomial-time solvable if restricted to a class of hypergraphs with bounded adaptive width. Conversely, assuming a conjecture on the complexity of binary CSP, there is no other polynomial-time solvable case.

Keywords : computational complexity constraint satisfaction treewidth adaptive width

Author: Dániel Marx -



Related documents