











Title 


Speaker 
Mark Siggers 


Date 
20180403 


Host 



Place 
KAIST 




Abstract : For problems with a discrete set of solutions, a reconfiguration problem defines solutions to be adjacent if they meet some condition of closeness, and then asks for two given solutions it there is a path between them in the set of all solutions.
The reconfiguration problem for graph homomorphisms has seen fair activity in recent years. Fixing a template, the problem Recol(H) for a graph H asks if one can get from one Hcolouring of a graph G to another by changing one vertex at a time, always remaining an Hcolouring. If the changed vertex has a loop, it must move to an adjecent vertex
Depending on H, the problem seems to be either polynomial time solvable or PSPACEcomplete. We discuss many recent results in the area and work towards conjecturing for which H the problem is PSPACEcomplete.
This is joint work with Rick Brewster, Jaebaek Lee, Ben Moore and Jon Noel. 





