Structural tractability of counting of solutions to conjunctive queries

DOI10.1007/s00224-014-9543-yzbMath1352.68080arXiv1303.2059OpenAlexW2088101961MaRDI QIDQ269342

Stefan Mengel, Arnaud Durand

Publication date: 18 April 2016

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

Full work available at URL: https://arxiv.org/abs/1303.2059

zbMATH Keywords

conjunctive queriescounting complexityhypergraph decomposition techniques

Mathematics Subject Classification ID

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

Related Items (11)

Unnamed Item ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Answer Counting under Guarded TGDs ⋮ Parameterised counting in logspace ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Characterizing tractability of simple well-designed pattern trees with projection ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Counting Answers to Existential Questions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tractable counting of the answers to conjunctive queries
• The complexity of weighted counting for acyclic conjunctive queries
• Enumerating homomorphisms
• Hypertree decompositions and tractable queries
• Elements of finite model theory.
• The complexity of counting homomorphisms seen from the other side
• A unified theory of structural tractability for constraint satisfaction problems
• A partial k-arboretum of graphs with bounded treewidth
• Decomposing constraint satisfaction problems using database techniques
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Structural tractability of enumerating CSP solutions
• Hypertree width and related hypergraph invariants
• Parametrized complexity theory.
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Query evaluation via tree-decompositions
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• Graph minors. II. Algorithmic aspects of tree-width
• When is the evaluation of conjunctive queries tractable?
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: Structural tractability of counting of solutions to conjunctive queries