The Existence of Homomorphisms to Oriented Cycles
From MaRDI portal
Publication:4837649
DOI10.1137/S0895480192239992zbMath0831.05059OpenAlexW2063356069MaRDI QIDQ4837649
Publication date: 12 February 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480192239992
computational complexityhomomorphismdigraphsNP-completeoriented pathoriented cyclebackward arcsforward arcs
Related Items
Homomorphisms to oriented paths ⋮ Minimum cost homomorphism dichotomy for oriented cycles ⋮ The complexity of restricted graph homomorphisms ⋮ Complexity of tree homomorphisms ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Homomorphic preimages of geometric paths ⋮ Homomorphisms and oriented colorings of equivalence classes of oriented graphs ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Duality pairs and homomorphisms to oriented and unoriented cycles ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Dualities for Constraint Satisfaction Problems