Structural decompositions for problems with global constraints
From MaRDI portal
Publication:272005
DOI10.1007/S10601-015-9181-2zbMATH Open1334.90192arXiv1502.02467OpenAlexW2093462208MaRDI QIDQ272005FDOQ272005
Authors: Evgenij Thorstensen 
Publication date: 20 April 2016
Published in: Constraints (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1502.02467
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
- Title not available (Why is that?)
- Handbook of constraint programming.
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Simultaneous matchings: Hardness and approximation
- Tractable cases of the extended global cardinality constraint
- Parametrized complexity theory.
- Backdoors to satisfaction
- Can you beat treewidth?
- Classifying the Complexity of Constraints Using Finite Algebras
- A comparison of structural CSP decomposition methods
- Constraint satisfaction with succinctly specified relations
- The complexity of reasoning with global constraints
- Hypertree width and related hypergraph invariants
- Size bounds and query plans for relational joins
- Approximating fractional hypertree width
- Optimization Methods for the Partner Units Problem
- Title not available (Why is that?)
- Typed Guarded Decompositions for Constraint Satisfaction
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- Width functions for hypertree decompositions
- Principles and Practice of Constraint Programming – CP 2004
- Hypertree decompositions and tractable queries
- A unified theory of structural tractability for constraint satisfaction problems
Cited In (8)
- Self-decomposable global constraints
- Global propagation of side constraints for solving over-constrained problems
- Recent Advances in Constraints
- The Effect of Constraint Representation on Structural Tractability
- Structural tractability of enumerating CSP solutions
- Typed Guarded Decompositions for Constraint Satisfaction
- On the power of structural decompositions of graph-based representations of constraint problems
- Decomposition structures for soft constraint evaluation problems: an algebraic approach
Uses Software
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)
