Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems

DOI10.1016/j.artint.2016.02.001zbMath1351.68253OpenAlexW2268771889MaRDI QIDQ253988

Aymeric Duchein, Guillaume Escamocher, Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux, Bruno Zanuttini

Publication date: 8 March 2016

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: http://oatao.univ-toulouse.fr/16973/1/cooper_16973.pdf

zbMATH Keywords

NP-completenessCSPconstraint satisfactiondomain reductionglobal constraintshybrid tractabilitytractable class

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ The power of propagation: when GAC is enough ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Broken-Triangle Property with Adjoint Values ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ On a new extension of BTP for binary CSPs ⋮ Variable and value elimination in binary constraint satisfaction via forbidden patterns

Uses Software

• MiniSat

Cites Work

• Unnamed Item
• Principles and practice of constraint programming. 20th international conference, CP 2014, Lyon, France, September 8--12, 2014. Proceedings
• A hybrid tractable class for non-binary CSPs
• Simultaneous matchings: Hardness and approximation
• Principles and practice of constraint programming. 14th international conference, CP 2008, Sydney, Australia, September 14--18, 2008. Proceedings
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Principles and practice of constraint programming. 2nd international workshop, PPCP '94, Rosario, Orcas Island, Washington, DC, USA, May 2-4, 1994. Proceedings
• Fundamental properties of neighbourhood substitution in constraint satisfaction problems
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Complexity of constraints. An overview of current research themes
• Principles and practice of constraint programming. 21st international conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015. Proceedings
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
• The Tractability of CSP Classes Defined by Forbidden Patterns
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• Theory and Applications of Satisfiability Testing