Tree projections and structural decomposition methods: minimality and game-theoretic characterization

DOI10.1016/j.tcs.2013.12.012zbMath1279.68277arXiv1212.2314OpenAlexW2016812993WikidataQ57782832 ScholiaQ57782832MaRDI QIDQ393903

Francesco Scarcello, Gianluigi Greco

Publication date: 24 January 2014

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

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

zbMATH Keywords

computational complexitytreewidthgames on hypergraphsgeneralized hypertree widthRobber and Captain gamestructural decomposition methods

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems

Cites Work

• Hypertree decompositions and tractable queries
• Graph minors. III. Planar tree-width
• A unified theory of structural tractability for constraint satisfaction problems
• Tree clustering for constraint networks
• Graph searching and a min-max theorem for tree-width
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• A comparison of structural CSP decomposition methods
• Structural tractability of enumerating CSP solutions
• Hypertree width and related hypergraph invariants
• Degrees of acyclicity for hypergraphs and relational database schemes
• Syntactic Characterization of Tree Database Schemas
• Marshals, monotone marshals, and hypertree-width
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Tree Projections: Hypergraph Games and Minimality
• Connected Treewidth and Connected Graph Searching
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• Power of Natural Semijoins
• Acyclic Hypergraph Projections
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• On the Power of k-Consistency
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth