Tractable hypergraph properties for constraint satisfaction and conjunctive queries

DOI10.1145/1806689.1806790zbMath1293.68171OpenAlexW2159738186MaRDI QIDQ2875201

Dániel Marx

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806790

zbMATH Keywords

constraint satisfactionfixed-parameter tractabilityconjunctive queriessubmodular width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65)

Related Items (14)

Tractable counting of the answers to conjunctive queries ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Enumerating homomorphisms ⋮ The power of propagation: when GAC is enough ⋮ Computing hypergraph width measures exactly ⋮ Quantum hypergraph states ⋮ On the complexity of existential positive queries ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Unnamed Item ⋮ Characterizing tractability of simple well-designed pattern trees with projection ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns ⋮ Unnamed Item ⋮ Structural tractability of enumerating CSP solutions ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties

This page was built for publication: Tractable hypergraph properties for constraint satisfaction and conjunctive queries