Log-Space Reconfiguration of Digraph Cycle Homomorphisms via Orientation Strings
Deciding whether two homomorphisms between reflexive digraph cycles lie in the same component of the reconfiguration graph Hom(C,D). Encoding both cycles as orientation strings, the components are characterized through the primitive root of the target's string and the wind of the homomorphism (Theorem 1.8), giving a linear-time, logarithmic-space algorithm that replaces the earlier Omega(m^2) greedy approach and places cycle-to-cycle homomorphism reconfiguration in log-space (arXiv:2501.01599, math.CO).
Reflexive Digraph Reconfiguration by Orientation Strings
The reconfiguration problem for homomorphisms of digraphs to a reflexive digraph cycle, which amounts to deciding if a `reconfiguration graph' is connected, is known to by polynomially time solvable …