Structural decompositions for problems with global constraints
From MaRDI portal
Abstract: A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.
Recommendations
- Typed Guarded Decompositions for Constraint Satisfaction
- On the power of structural decompositions of graph-based representations of constraint problems
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- A comparison of structural CSP decomposition methods
Cites work
- scientific article; zbMATH DE number 5999532 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A comparison of structural CSP decomposition methods
- A unified theory of structural tractability for constraint satisfaction problems
- Approximating fractional hypertree width
- Backdoors to satisfaction
- Can you beat treewidth?
- Classifying the Complexity of Constraints Using Finite Algebras
- Constraint satisfaction with succinctly specified relations
- Handbook of constraint programming.
- Hypertree decompositions and tractable queries
- Hypertree width and related hypergraph invariants
- Optimization Methods for the Partner Units Problem
- Parametrized complexity theory.
- Principles and Practice of Constraint Programming – CP 2004
- Simultaneous matchings: Hardness and approximation
- Size bounds and query plans for relational joins
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of reasoning with global constraints
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- Tractable cases of the extended global cardinality constraint
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Typed Guarded Decompositions for Constraint Satisfaction
- Width functions for hypertree decompositions
Cited in
(8)- Self-decomposable global constraints
- On the power of structural decompositions of graph-based representations of constraint problems
- Global propagation of side constraints for solving over-constrained problems
- The Effect of Constraint Representation on Structural Tractability
- Decomposition structures for soft constraint evaluation problems: an algebraic approach
- Structural tractability of enumerating CSP solutions
- Recent Advances in Constraints
- Typed Guarded Decompositions for Constraint Satisfaction
This page was built for publication: Structural decompositions for problems with global constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q272005)
