Binary constraint satisfaction problems defined by excluded topological minors

DOI10.1016/j.ic.2018.09.013zbMath1408.68130arXiv1608.05358OpenAlexW2508164492MaRDI QIDQ1633806

Peter G. Jeavons, David A. Cohen, Stanislav Živný, Martin C. Cooper

Publication date: 21 December 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.05358

zbMATH Keywords

constraint satisfactionforbidden substructuresforbidden patternstopological minors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Dismantlability, connectedness, and mixing in relational structures, Galois connections for patterns: an algebra of labelled graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• Hybrid tractability of valued constraint problems
• Graph minors. XX: Wagner's conjecture
• Forbidden minors characterization of partial 3-trees
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Graph minors. V. Excluding a planar graph
• Tree clustering for constraint networks
• An optimal k-consistency algorithm
• The power of propagation: when GAC is enough
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Variable and value elimination in binary constraint satisfaction via forbidden patterns
• Forbidden lifts (NP and CSP for combinatorialists)
• Parametrized complexity theory.
• The Tractability of CSP Classes Defined by Forbidden Patterns
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A sufficient condition for backtrack-bounded search
• A Sufficient Condition for Backtrack-Free Search
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Dividing a Graph into Triconnected Components
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• Finding topological subgraphs is fixed-parameter tractable
• Constraint Satisfaction, Logic and Forbidden Patterns
• Short proof of Menger's graph theorem
• Principles and Practice of Constraint Programming – CP 2003