Generalized hypertree decompositions: NP-hardness and tractable variants
From MaRDI portal
Publication:3452226
DOI10.1145/1568318.1568320zbMath1325.68097WikidataQ59259597 ScholiaQ59259597MaRDI QIDQ3452226
Zoltán Miklós, Thomas Schwentick, Georg Gottlob
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1568318.1568320
hypergraph; NP-complete; conjunctive query; acyclic; hypertree decomposition; tractable; tree projection problem
05C05: Trees
05C65: Hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
The power of non-ground rules in Answer Set Programming, HyperBench, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Fractional covers of hypergraphs with bounded multi-intersection, Structural tractability of counting of solutions to conjunctive queries, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, Connected graph searching, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, A more general theory of static approximations for conjunctive queries, An annotated bibliography on guaranteed graph searching, On the power of structural decompositions of graph-based representations of constraint problems, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs, Efficiently enumerating minimal triangulations, Fast and parallel decomposition of constraint satisfaction problems, Finding optimal triangulations parameterized by edge clique cover, Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value, Structural tractability of enumerating CSP solutions, Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints, Myhill-Nerode Methods for Hypergraphs, Covers of Query Results, A More General Theory of Static Approximations for Conjunctive Queries, HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results, Tree Projections: Game Characterization and Computational Aspects
