Tractable structures for constraint satisfaction with truth tables

DOI10.1007/s00224-009-9248-9zbMath1253.68180MaRDI QIDQ537902

Dániel Marx

Publication date: 23 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1807/

zbMATH Keywords

computational complexity; treewidth; constraint satisfaction; adaptive width

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, On the complexity of existential positive queries, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Tractability in constraint satisfaction problems: a survey

Cites Work

• Hypertree decompositions and tractable queries
• Conjunctive-query containment and constraint satisfaction
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Which problems have strongly exponential complexity?
• Constraint satisfaction with succinctly specified relations
• Approximating fractional hypertree width
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• When is the evaluation of conjunctive queries tractable?
• The complexity of maximal constraint languages
• The complexity of satisfiability problems
• Uniform Constraint Satisfaction Problems and Database Theory
• The Structure of Tractable Constraint Satisfaction Problems
• Unnamed Item
• Unnamed Item