Reconfiguring homomorphisms to reflexive graphs via a simple reduction
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929546862788608 |
|---|---|
| author | Mühlenthaler, Moritz Siggers, Mark H. Suzan, Thomas |
| author_facet | Mühlenthaler, Moritz Siggers, Mark H. Suzan, Thomas |
| contents | Given a graph $G$ and two graph homomorphisms $α$ and $β$ from $G$ to a fixed graph $H$, the problem $H$-Recoloring asks whether there is a transformation from $α$ to $β$ that changes the image of a single vertex at each step and keeps a graph homomorphism throughout. The complexity of the problem depends among other things on the presence of loops on the vertices. We provide a simple reduction that, using a known algorithmic result for $H$-Recoloring for square-free irreflexive graphs $H$, yields a polynomial-time algorithm for $H$-Recoloring for square-free reflexive graphs $H$. This generalizes all known algorithmic results for $H$-Recoloring for reflexive graphs $H$. Furthermore, the construction allows us to recover some of the known hardness results. Finally, we provide a partial inverse of the construction for bipartite instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12687 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconfiguring homomorphisms to reflexive graphs via a simple reduction Mühlenthaler, Moritz Siggers, Mark H. Suzan, Thomas Discrete Mathematics Data Structures and Algorithms 05C85 (Primary) 05C15, 68Q25 (Secondary) Given a graph $G$ and two graph homomorphisms $α$ and $β$ from $G$ to a fixed graph $H$, the problem $H$-Recoloring asks whether there is a transformation from $α$ to $β$ that changes the image of a single vertex at each step and keeps a graph homomorphism throughout. The complexity of the problem depends among other things on the presence of loops on the vertices. We provide a simple reduction that, using a known algorithmic result for $H$-Recoloring for square-free irreflexive graphs $H$, yields a polynomial-time algorithm for $H$-Recoloring for square-free reflexive graphs $H$. This generalizes all known algorithmic results for $H$-Recoloring for reflexive graphs $H$. Furthermore, the construction allows us to recover some of the known hardness results. Finally, we provide a partial inverse of the construction for bipartite instances. |
| title | Reconfiguring homomorphisms to reflexive graphs via a simple reduction |
| topic | Discrete Mathematics Data Structures and Algorithms 05C85 (Primary) 05C15, 68Q25 (Secondary) |
| url | https://arxiv.org/abs/2410.12687 |