License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.43
URN: urn:nbn:de:0030-drops-176958
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17695/
Go to the corresponding LIPIcs Volume Portal

Lévêque, Benjamin ; Mühlenthaler, Moritz ; Suzan, Thomas

Reconfiguration of Digraph Homomorphisms

pdf-format:
LIPIcs-STACS-2023-43.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{leveque_et_al:LIPIcs.STACS.2023.43,
  author =	{L\'{e}v\^{e}que, Benjamin and M\"{u}hlenthaler, Moritz and Suzan, Thomas},
  title =	{{Reconfiguration of Digraph Homomorphisms}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{43:1--43:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17695},
  URN =		{urn:nbn:de:0030-drops-176958},
  doi =		{10.4230/LIPIcs.STACS.2023.43},
  annote =	{Keywords: Digraph Homomorphisms, Combinatorial Reconfiguration}
}

Keywords: Digraph Homomorphisms, Combinatorial Reconfiguration
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI