License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.730
URN: urn:nbn:de:0030-drops-49546
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4954/
Go to the corresponding LIPIcs Volume Portal

Wrochna, Marcin

Homomorphism Reconfiguration via Homotopy

pdf-format:
54.pdf (0.7 MB)

Abstract

We consider the following problem for a fixed graph H: given a graph G and two H-colorings of G, i.e. homomorphisms from G to H, can one be transformed into the other by changing one color at a time, maintaining an H-coloring throughout.This is the same as finding a path in the Hom(G,H) complex. For H=K_k this is the problem of finding paths between k-colorings, which was recently shown to be in P for k\leq 3 and PSPACE-complete otherwise (Bonsma and Cereceda 2009, Cereceda et al. 2011).
We generalize the positive side of this dichotomy by providing an algorithm that solves the problem in polynomial time for any H with no C_4 subgraph. This gives a large class of constraints for which finding solutions to the Constraint Satisfaction Problem is NP-complete, but paths in the solution space can be found in polynomial time.

The algorithm uses a characterization of possible reconfiguration sequences (that is, paths in Hom(G,H)), whose main part is a purely topological condition described in terms of the fundamental groupoid of H seen as a topological space.

BibTeX - Entry

@InProceedings{wrochna:LIPIcs:2015:4954,
  author =	{Marcin Wrochna},
  title =	{{Homomorphism Reconfiguration via Homotopy}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{730--742},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4954},
  URN =		{urn:nbn:de:0030-drops-49546},
  doi =		{10.4230/LIPIcs.STACS.2015.730},
  annote =	{Keywords: reconfiguration, recoloring, homomorphisms, homotopy, hom complex}
}

Keywords: reconfiguration, recoloring, homomorphisms, homotopy, hom complex
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

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