Dichotomies for classes of homomorphism problems involving unary functions

DOI10.1016/j.tcs.2003.12.015zbMath1070.68133OpenAlexW2001346827MaRDI QIDQ1884913

Tomás Feder, Iain A. Stewart, Florent R. Madelaine

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/597/1/597.pdf

zbMATH Keywords

non-uniform constraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, Satisfiability in MultiValued Circuits, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Colouring, constraint satisfaction, and complexity, Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras., On solvability of systems of polynomial equations, TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, Adjusted Interval Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Polynomial graph-colorings
• Constraints and universal algebra
• The complexity of iterated multiplication
• Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
• Conjunctive-query containment and constraint satisfaction
• Completeness of path-problems via logical reductions
• List homomorphisms and circular arc graphs
• Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Bi‐arc graphs and the complexity of list homomorphisms
• The complexity of satisfiability problems