Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT

DOI10.1016/j.tcs.2022.12.002OpenAlexW4313340638MaRDI QIDQ2110380

Matthias Lanzinger

Publication date: 21 December 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphsatisfiabilitySATbeta-acyclicconjunctive queries with negation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Satisfiability of acyclic and almost acyclic CNF formulas
• Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
• Hypertree decompositions and tractable queries
• Decomposing constraint satisfaction problems using database techniques
• Upper bounds to the clique width of graphs
• Hypertree width and related hypergraph invariants
• Size Bounds and Query Plans for Relational Joins
• Degrees of acyclicity for hypergraphs and relational database schemes
• Hypergraph Acyclicity and Propositional Model Counting
• Solving #SAT and MAXSAT by Dynamic Programming
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• Node-Deletion Problems on Bipartite Graphs
• Reducibility among Combinatorial Problems
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• Parameterized Algorithms
• A Computing Procedure for Quantification Theory
• Point-Width and Max-CSPs
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT