Beyond Hypertree Width: Decomposition Methods Without Decompositions

DOI10.1007/11564751_15MaRDI QIDQ3524172zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Víctor Dalmau

Publication date 9 September 2008

Published in Principles and Practice of Constraint Programming - CP 2005 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: The general intractability of the constraint satisfaction problem has motivated the study of restrictions on this problem that permit polynomial-time solvability. One major line of work has focused on structural restrictions, which arise from restricting the interaction among constraint scopes. In this paper, we engage in a mathematical investigation of generalized hypertree width, a structural measure that has up to recently eluded study. We obtain a number of computational results, including a simple proof of the tractability of CSP instances having bounded generalized hypertree width.

Recommendations

• A comparison of structural CSP decomposition methods
• A unified theory of structural tractability for constraint satisfaction problems
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Uniform Constraint Satisfaction Problems and Database Theory
• Graph-Theoretic Concepts in Computer Science

Cited in

(30)

• Decomposing constraint satisfaction problems using database techniques
• A comparison of structural CSP decomposition methods
• Finding a given number of solutions to a system of fuzzy constraints
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Constraint satisfaction with succinctly specified relations
• How many variables are needed to express an existential positive query?
• Structural tractability of enumerating CSP solutions
• Regularizing conjunctive features for classification
• Structural tractability of counting of solutions to conjunctive queries
• Structural decompositions for problems with global constraints
• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• Semantic acyclicity for conjunctive queries: approximations and constraints
• Semantic acyclicity on graph databases
• A more general theory of static approximations for conjunctive queries
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Tradeoffs in the Complexity of Backdoor Detection
• Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• Tractable structures for constraint satisfaction with truth tables
• A Logical Approach to Constraint Satisfaction
• Uniform Constraint Satisfaction Problems and Database Theory
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Point-Width and Max-CSPs
• Incremental Updates of Generalized Hypertree Decompositions
• Point-width and max-CSPs
• A more general theory of static approximations for conjunctive queries
• Constraint satisfaction with bounded treewidth revisited
• A unified theory of structural tractability for constraint satisfaction problems

This page was built for publication: Beyond Hypertree Width: Decomposition Methods Without Decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3524172)