Tractable hypergraph properties for constraint satisfaction and conjunctive queries

DOI10.1145/1806689.1806790zbMATH Open1293.68171OpenAlexW2159738186MaRDI QIDQ2875201FDOQ2875201

Authors: 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

Recommendations

• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• scientific article
• Structural tractability of counting of solutions to conjunctive queries
• Satisfiability on hypergraphs
• Consequence operations based on hypergraph satisfiability
• scientific article
• Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
• Tractable structures for constraint satisfaction with truth tables
• Tractable structures for constraint satisfaction with truth tables

zbMATH Keywords

constraint satisfactionfixed-parameter tractabilityconjunctive queriessubmodular width

Mathematics Subject Classification ID

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

Cited In (20)

• Title not available (Why is that?)
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• Title not available (Why is that?)
• Tractable counting of the answers to conjunctive queries
• The complexity of weighted counting for acyclic conjunctive queries
• Enumerating homomorphisms
• Tractable structures for constraint satisfaction with truth tables
• Computing hypergraph width measures exactly
• The power of propagation: when GAC is enough
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Characterizing tractability of simple well-designed pattern trees with projection
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Tractable structures for constraint satisfaction with truth tables
• On the complexity of existential positive queries
• Structural tractability of enumerating CSP solutions
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Computing partial hypergraphs of bounded width
• Quantum hypergraph states
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875201)