Tractability in constraint satisfaction problems: a survey

DOI10.1007/S10601-015-9198-6zbMATH Open1334.90220OpenAlexW1009693448MaRDI QIDQ271997FDOQ271997

Authors: Clément Carbonnel, M. 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

Recommendations

• New tractable classes from old
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Hybrid tractable classes of constraint problems
• Tractability by approximating constraint languages
• Asking the Metaquestions in Constraint Tractability

zbMATH Keywords

computational complexityrelaxationdichotomyforbidden patternmicrostructurepolymorphismpolynomial-timetractable language

Mathematics Subject Classification ID

Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• The complexity of conservative valued CSPs
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• An algebraic theory of complexity for discrete optimization.
• 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
• Dualities for Constraint Satisfaction Problems
• 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
• 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
• Constraint satisfaction with bounded treewidth revisited
• Conservative constraint satisfaction re-revisited
• The complexity of equality constraint languages
• A finite set of functions with an EXPTIME-complete composition problem
• DARN! A weighted constraint solver for RNA motif localization
• Soft arc consistency revisited
• Maintaining knowledge about temporal intervals
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Complexity of constraints. An overview of current research themes
• Tractable triangles and cross-free convexity in discrete optimisation
• Title not available (Why is that?)
• The tractability of CSP classes defined by forbidden patterns
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Paths, Trees, and Flowers
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• On the complexity of H-coloring
• The ellipsoid method and its consequences in combinatorial optimization
• Temporal constraint networks
• Graph minors. XIII: The disjoint paths problem
• Non-dichotomies in Constraint Satisfaction Complexity
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of temporal constraint satisfaction problems
• 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
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems
• Recent Results on the Algebraic Approach to the CSP
• The complexity of theorem-proving procedures
• The complexity of weighted Boolean \#CSP with mixed signs
• The strong perfect graph theorem
• Maximal infinite-valued constraint languages
• Relatively quantified constraint satisfaction
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Network-based heuristics for constraint-satisfaction problems
• 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
• 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.
• 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
• Title not available (Why is that?)
• The collapse of the bounded width hierarchy
• An effective dichotomy for the counting constraint satisfaction problem
• Local consistency and SAT-solvers
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• Approximating fractional hypertree width
• Complexity of conservative constraint satisfaction problems
• Building tractable disjunctive constraints
• On Maltsev digraphs
• The complexity of finite-valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The complexity of constraint satisfaction: an algebraic approach
• A Probabilistic Approach to the Dichotomy Problem
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• 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)
• Satisfiability of acyclic and almost acyclic CNF formulas
• Title not available (Why is that?)
• On the minimality and global consistency of row-convex constraint networks
• Constraint tightness and looseness versus local and global consistency
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On generating all solutions of generalized satisfiability problems
• Title not available (Why is that?)
• Colouring, constraint satisfaction, and complexity
• Title not available (Why is that?)
• 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
• A new line of attack on the dichotomy conjecture
• The complexity of maximal constraint languages
• On the subexponential-time complexity of CSP
• Certainty closure: reliable constraint reasoning with incomplete or erroneous data
• The complexity of general-valued CSPs
• Generalized Majority-Minority Operations are Tractable
• The parameterized complexity of \(k\)-biclique
• Tractable structures for constraint satisfaction with truth tables
• Tractability and learnability arising from algebras with few subpowers

Cited In (37)

• The complexity of constraint satisfaction problems (invited talk)
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Generalized Majority-Minority Operations are Tractable
• Tractable set constraints
• CSP beyond tractable constraint languages
• Computational Short Cuts in Infinite Domain Constraint Satisfaction
• The Broken-Triangle Property with Adjoint Values
• Backdoors into heterogeneous classes of SAT and CSP
• Tractable constraints on ordered domains
• New tractable classes from old
• A polynomial relational class of binary CSP
• Backdoor sets for CSP
• The tractability of CSP classes defined by forbidden patterns
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Principles and Practice of Constraint Programming – CP 2004
• Methods and Applications of Artificial Intelligence
• Hybrid tractable classes of constraint problems
• Constraint satisfaction with succinctly specified relations
• Constraint satisfaction problems over numeric domains
• Complexity of reachability problems in neural networks
• Galois connections for patterns: an algebra of labelled graphs
• Tractable structures for constraint satisfaction with truth tables
• Discovering archipelagos of tractability for constraint satisfaction and counting
• Discovering archipelagos of tractability for constraint satisfaction and counting
• Complexity classifications of Boolean constraint satisfaction problems
• On the complexity of trial and error for constraint satisfaction problems
• On planar valued CSPs
• Constraint satisfaction tractability from semi-lattice operations on infinite sets
• Computer Science Logic
• Some new tractable classes of CSPs and their relations with backtracking algorithms
• Title not available (Why is that?)
• Tractability by approximating constraint languages
• Tractable decision for a constraint language implies tractable search
• Sum-of-Products with Default Values: Algorithms and Complexity Results
• Constraint satisfaction problems: convexity makes AllDifferent constraints tractable
• A unifying framework for structural properties of CSPS: definitions, complexity, tractability
• Periodic constraint satisfaction problems: Tractable subclasses

Uses Software

• DARN!
• ToulBar2

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q271997)