Title   name
2018 Discrete Math 세미나
 
  Title
  Speaker   Mark Siggers  
  Date 2018-04-03
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.
 
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 H-colouring of a graph G to another by changing one vertex at a time, always remaining an H-colouring. 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 PSPACE-complete. We discuss many recent results in the area and work towards conjecturing for which H the problem is PSPACE-complete.

This is joint work with Rick Brewster, Jae-baek Lee, Ben Moore and Jon Noel.