Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems

DOI10.1016/j.ic.2016.11.004zbMath1355.68121arXiv1603.09617OpenAlexW2326948987MaRDI QIDQ729822

Francesco Scarcello, Gianluigi Greco

Publication date: 22 December 2016

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfaction problemsdatabasesconjunctive queriesstructural decomposition methodsgames on discrete structureshomomorphism problemhypertree decompositionstree projections

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (4)

The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value

Uses Software

• EmptyHeaded

Cites Work

• The complexity of mixed multi-unit combinatorial auctions: tractability under structural and qualitative restrictions
• Tree projections and structural decomposition methods: minimality and game-theoretic characterization
• Hybrid tractability of valued constraint problems
• The complexity of pursuit on a graph
• Hypertree decompositions and tractable queries
• A game of cops and robbers
• Graph minors. III. Planar tree-width
• The complexity of zero-visibility cops and robber
• A unified theory of structural tractability for constraint satisfaction problems
• On the power of structural decompositions of graph-based representations of constraint problems
• The tree projection theorem and relational query processing
• Cops and robbers in graphs with large girth and Cayley graphs
• Graph searching and a min-max theorem for tree-width
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Cops and robbers on intersection graphs
• Vertex-to-vertex pursuit in a graph
• On the computational complexity of a game of cops and robbers
• Cops and robbers is EXPTIME-complete
• Pursuing a fast robber on a graph
• Hypertree width and related hypergraph invariants
• Variations on cops and robbers
• Cops and Robber with Constraints
• Chasing a Fast Robber on Planar Graphs and Random Graphs
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• Marshals, monotone marshals, and hypertree-width
• GYM: A Multiround Distributed Join Algorithm
• The complexity of acyclic conjunctive queries
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Constraint solving via fractional edge covers
• Tree-Related Widths of Graphs and Hypergraphs
• Power of Natural Semijoins
• Alternation
• A compressed Generalized Hypertree Decomposition-based solving technique for non-binary Constraint Satisfaction Problems
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems