Reflexive Digraph Reconfiguration by Orientation Strings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909540474159104 |
|---|---|
| author | Pullas, David Emmanuel Pazmiño Siggers, Mark |
| author_facet | Pullas, David Emmanuel Pazmiño Siggers, Mark |
| contents | 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 via a greedy algorithm based on certain topological requirements. Even in the case that the instance digraph is a cycle of length $m$, the algorithm, being greedy, takes time $Ω(m^2)$.
Encoding homomorphisms between two cycles as a relation on strings that represent the orientations of the cycles, we give a characterization of the components of the reconfiguration graph that can be computed in linear time and logarithmic space. In particular, this solves the reconfiguration problem for homomorphisms of cycles to cycles in log-space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01599 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reflexive Digraph Reconfiguration by Orientation Strings Pullas, David Emmanuel Pazmiño Siggers, Mark Combinatorics 05C85, 05C15 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 via a greedy algorithm based on certain topological requirements. Even in the case that the instance digraph is a cycle of length $m$, the algorithm, being greedy, takes time $Ω(m^2)$. Encoding homomorphisms between two cycles as a relation on strings that represent the orientations of the cycles, we give a characterization of the components of the reconfiguration graph that can be computed in linear time and logarithmic space. In particular, this solves the reconfiguration problem for homomorphisms of cycles to cycles in log-space. |
| title | Reflexive Digraph Reconfiguration by Orientation Strings |
| topic | Combinatorics 05C85, 05C15 |
| url | https://arxiv.org/abs/2501.01599 |