2026-07-23T22:21:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17695 2024-03-06T11:00:20Z ddc:004 open_access

Reconfiguration of Digraph Homomorphisms Lévêque, Benjamin Mühlenthaler, Moritz Suzan, Thomas Digraph Homomorphisms Combinatorial Reconfiguration For a fixed graph H, the H-Recoloring problem asks whether, given two homomorphisms from a graph G to H, one homomorphism can be transformed into the other by changing the image of a single vertex in each step and maintaining a homomorphism to H throughout. The most general algorithmic result for H-Recoloring so far has been proposed by Wrochna in 2014, who introduced a topological approach to obtain a polynomial-time algorithm for any undirected loopless square-free graph H. We show that the topological approach can be used to recover essentially all previous algorithmic results for H-Recoloring and that it is applicable also in the more general setting of digraph homomorphisms. In particular, we show that H-Recoloring admits a polynomial-time algorithm i) if H is a loopless digraph that does not contain a 4-cycle of algebraic girth 0 and ii) if H is a reflexive digraph that contains no triangle of algebraic girth 1 and no 4-cycle of algebraic girth 0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Lévêque and Moritz Mühlenthaler and Thomas Suzan 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.43 urn:nbn:de:0030-drops-176958 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode