Tractability in constraint satisfaction problems: a survey
From MaRDI portal
Publication:271997
DOI10.1007/s10601-015-9198-6zbMath1334.90220OpenAlexW1009693448MaRDI QIDQ271997
Clément Carbonnel, Martin C. Cooper
Publication date: 20 April 2016
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: http://oatao.univ-toulouse.fr/16861/1/carbonnel_16861.pdf
computational complexitymicrostructurerelaxationpolymorphismdichotomypolynomial-timeforbidden patterntractable language
Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)
Related Items (9)
On planar valued CSPs ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ CSP beyond tractable constraint languages ⋮ Backdoor Sets for CSP. ⋮ The Broken-Triangle Property with Adjoint Values ⋮ A polynomial relational class of binary CSP ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction
Uses Software
Cites Work
- Maintaining knowledge about temporal intervals
- Satisfiability of acyclic and almost acyclic CNF formulas
- Colouring, constraint satisfaction, and complexity
- Tractable structures for constraint satisfaction with truth tables
- Hybrid tractability of valued constraint problems
- Hypertree decompositions and tractable queries
- Improved upper bounds for vertex cover
- Backdoors into heterogeneous classes of SAT and CSP
- Parameterized complexity of constraint satisfaction problems
- The complexity of weighted Boolean \#CSP with mixed signs
- Constraint satisfaction with bounded treewidth revisited
- The strong perfect graph theorem
- Conservative constraint satisfaction re-revisited
- The complexity of equality constraint languages
- DARN! A weighted constraint solver for RNA motif localization
- A finite set of functions with an EXPTIME-complete composition problem
- Soft arc consistency revisited
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Maximal infinite-valued constraint languages
- Relatively quantified constraint satisfaction
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- On the complexity of H-coloring
- Network-based heuristics for constraint-satisfaction problems
- The ellipsoid method and its consequences in combinatorial optimization
- Temporal constraint networks
- From local to global consistency
- Constraints, consistency and closure
- A unifying approach to temporal constraint reasoning
- On the algebraic structure of combinatorial problems
- Linear-time algorithms for testing the realisability of line drawings of curved objects
- Constraint satisfaction over connected row-convex constraints
- Characterising tractable constraints
- A new tractable class of constraint satisfaction problems
- Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
- Graph minors. XIII: The disjoint paths problem
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Constraint satisfaction with succinctly specified relations
- Characterizations of several Maltsev conditions.
- Complexity of constraints. An overview of current research themes
- Domain permutation reduction for constraint satisfaction problems
- The complexity of soft constraint satisfaction
- Hypertree width and related hypergraph invariants
- Recognizing Berge graphs
- Combinatorial problems raised from 2-semilattices
- Nonserial dynamic programming
- CSP for binary conservative relational structures
- The collapse of the bounded width hierarchy
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Local Consistency and SAT-Solvers
- Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
- Complexity of conservative constraint satisfaction problems
- Building tractable disjunctive constraints
- On Maltsev Digraphs
- The Tractability of CSP Classes Defined by Forbidden Patterns
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- A Probabilistic Approach to the Dichotomy Problem
- Reasoning about temporal relations
- Non-dichotomies in Constraint Satisfaction Complexity
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of temporal constraint satisfaction problems
- Constraint solving via fractional edge covers
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Complexity of Weighted Boolean #CSP
- Complexity of Finding Embeddings in a k-Tree
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- On the minimality and global consistency of row-convex constraint networks
- Closure properties of constraints
- Constraint tightness and looseness versus local and global consistency
- On generating all solutions of generalized satisfiability problems
- Deciding First-Order Properties of Nowhere Dense Graphs
- Constraint Satisfaction Problems on Intervals and Lengths
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
- The Complexity of Valued Constraint Satisfaction Problems
- Arc consistency and friends
- Time–dependent Simple Temporal Networks: Properties and Algorithms
- Reducibility among Combinatorial Problems
- A new line of attack on the dichotomy conjecture
- The complexity of maximal constraint languages
- On the Subexponential-Time Complexity of CSP
- Certainty closure
- The Complexity of General-Valued CSPs
- Generalized Majority-Minority Operations are Tractable
- Classifying the Complexity of Constraints Using Finite Algebras
- Paths, Trees, and Flowers
- The Parameterized Complexity of k-B<scp>iclique</scp>
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of conservative valued CSPs
- The expressibility of functions on the boolean domain, with applications to counting CSPs
- The complexity of the counting constraint satisfaction problem
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- An Algebraic Theory of Complexity for Discrete Optimization
- The complexity of satisfiability problems
- A Characterisation of First-Order Constraint Satisfaction Problems
- A Simple Algorithm for Mal'tsev Constraints
- Full Constraint Satisfaction Problems
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Monotone Temporal Planning: Tractability, Extensions and Applications
- Constraint Satisfaction Parameterized by Solution Size
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
- The complexity of theorem-proving procedures
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Computing and Combinatorics
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- The Structure of Tractable Constraint Satisfaction Problems
- Tractable constraints on ordered domains
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Tractability in constraint satisfaction problems: a survey
