×

Reconfiguration of homomorphisms to reflexive digraph cycles. (English) Zbl 1466.05137

Summary: Let \(G\) be a digraph and \(B\) be a fixed reflexive digraph cycle. Given two homomorphisms \(\phi\), \(\phi^\prime : G \to B\), a walk from \(\varphi\) to \(\phi^\prime\) in the Hom-graph \(\operatorname{Hom}(G, B)\) corresponds to what is often called a reconfiguration sequence of the homomorphisms. Except in the case that \(B\) contains a 4-cycle, containing an oriented cycle of algebraic girth 0, we give a polynomial time algorithm that either finds a path between two given homomorphisms or discovers an obstruction certifying the non-existence of such a path.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bonsma, P.; Cereceda, L., Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theor. Comput. Sci., 410, 5215-5226 (2009) · Zbl 1177.05112
[2] Brewster, R. C.; Lee, J.; Siggers, M., Recolouring reflexive digraphs, Discrete Math., 341, 6, 1708-1721 (2018) · Zbl 1384.05083
[3] Brewster, R. C.; McGuinness, S.; Moore, B.; Noel, J. A., On the complexity of the reconfiguration problem for graph homomorphisms, J. Theor. Comput. Sci., 639, 1-13 (2016)
[4] Brewster, R. C.; Noel, J. A., Mixing homomorphisms, recolorings, and extending circular precolorings, J. Graph Theory, 80, 173-198 (2015) · Zbl 1330.05060
[5] Cereceda, L., Mixing Graph Colourings (2007), The London School of Economics and Political Science, PhD thesis
[6] Cereceda, L.; van den Heuvel, J.; Johnson, M., Connectedness of the graph of vertex-colourings, Discrete Math., 308, 913-919 (2008) · Zbl 1133.05053
[7] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1998) · Zbl 0914.68075
[8] Larose, B.; Loten, C.; Zádori, L., A polynomial-time algorithm to recognize near-unanimity graphs, J. Algorithms, 55, 177-191 (2005) · Zbl 1101.68960
[9] Maróti, M.; Zádori, L., Reflexive digraphs with near unanimity operations, Discrete Math., 12, 2316-2328 (2012) · Zbl 1245.05059
[10] Wrochna, M., Homomorphism reconfiguration via homotopy, (32nd International Symposium on Theoretical Aspects of Computer Science. 32nd International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 30 (2015), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), 730-742 · Zbl 1356.68111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.