A comparison of structural CSP decomposition methods
From MaRDI portal
We compare tractable classes of Constraint Satisfaction Problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in database theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general CSPs (i.e., CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree-decomposition method turns out to be the most general method.
Recommendations
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- On the power of structural decompositions of graph-based representations of constraint problems
- Uniform Constraint Satisfaction Problems and Database Theory
- Recent Advances in Constraints
- A unified theory of structural tractability for constraint satisfaction problems
Cites work
- A sufficient condition for backtrack-bounded search
- A Sufficient Condition for Backtrack-Free Search
- Closure properties of constraints
- Conjunctive query containment revisited
- Conjunctive-query containment and constraint satisfaction
- Constraint satisfaction from a deductive viewpoint
- Decomposing constraint satisfaction problems using database techniques
- Easy problems for tree-decomposable graphs
- Graph minors. II. Algorithmic aspects of tree-width
- scientific article; zbMATH DE number 3986679 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1361465 (Why is no real title available?)
- Hypertree decompositions and tractable queries
- Network-based heuristics for constraint-satisfaction problems
- On the Desirability of Acyclic Database Schemes
- Power of Natural Semijoins
- Syntactic Characterization of Tree Database Schemas
- Tree clustering for constraint networks
Cited in
(64)- Decomposing constraint satisfaction problems using database techniques
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Decomposable constraints
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Disjunctions, independence, refinements
- The power of propagation: when GAC is enough
- Combining restarts, nogoods and bag-connected decompositions for solving csps
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Constraint satisfaction with succinctly specified relations
- Fast and parallel decomposition of constraint satisfaction problems
- Structural tractability of enumerating CSP solutions
- Large hypertree width for sparse random hypergraphs
- Domain permutation reduction for constraint satisfaction problems
- The complexity of reasoning with global constraints
- Unifying tree decompositions for reasoning in graphical models
- Partition-based logical reasoning for first-order and propositional theories
- Task-dependent qualitative domain abstraction
- Hypertree width and related hypergraph invariants
- Characteristic function games with restricted agent interactions: core-stability and coalition structures
- Computing partial hypergraphs of bounded width
- Structural tractability of counting of solutions to conjunctive queries
- Structural decompositions for problems with global constraints
- On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Finding good decompositions for dynamic programming on dense graphs
- Fixed-parameter tractability of treewidth and pathwidth
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- Dynamic Management of Heuristics for Solving Structured CSPs
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Typed Guarded Decompositions for Constraint Satisfaction
- On minimal constraint networks
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
- Learning to integrate deduction and search in reasoning about quantified Boolean formulas
- Tractable counting of the answers to conjunctive queries
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Equivalence between hypergraph convexities
- Generic local computation
- scientific article; zbMATH DE number 1149412 (Why is no real title available?)
- Solving partial constraint satisfaction problems with tree decomposition
- HyperBench. A benchmark and tool for hypergraphs and empirical findings
- On sparse discretization for graphical games
- Coalition formation in social environments with logic-based agents1
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- A Logical Approach to Constraint Satisfaction
- Uniform Constraint Satisfaction Problems and Database Theory
- Lifted Reasoning for Combinatorial Counting
- Diagnosing tree-structured systems
- Incremental Updates of Generalized Hypertree Decompositions
- Cops and robber on oriented graphs with respect to push operation
- CSP beyond tractable constraint languages
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Constraint reasoning
- Parameterized analysis of the cops and robber problem
- Hypertree decompositions and tractable queries
- A safeness condition for minimal separators based on vertex connectivity
- The complexity of counting homomorphisms seen from the other side
- A polynomial relational class of binary CSP
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- On the complexity of constrained Nash equilibria in graphical games
- Weighted hypertree decompositions and optimal query plans
- A unified theory of structural tractability for constraint satisfaction problems
- Treewidth computations. I: Upper bounds
- On the power of structural decompositions of graph-based representations of constraint problems
- Causal graphs and structurally restricted planning
This page was built for publication: A comparison of structural CSP decomposition methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589639)
