Tractability in constraint satisfaction problems: a survey

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

zbMATH Keywords

computational complexitymicrostructurerelaxationpolymorphismdichotomypolynomial-timeforbidden patterntractable language

Mathematics Subject Classification ID

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

• DARN!
• ToulBar2

Cites Work

• 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
• 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

This page was built for publication: Tractability in constraint satisfaction problems: a survey