Dichotomies for classes of homomorphism problems involving unary functions

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

Iain A. Stewart, Tomás Feder, 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

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

Related Items

TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, On solvability of systems of polynomial equations

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