M/614

A reconfiguration problem is the reachability problem on an interesting class of graphs, namely the solution graphs of a combinatorial problem: Given two solutions to some instance, the task is to decide whether one solution can be transformed into the other via ``local'' changes while maintaining feasibility. For example, given two k-colorings of a graph, the task is to decide whether one can be transformed into the other by changing the color of a single vertex at a time, such that each intermediate coloring is proper. It turns out that the complexity of reconfiguration problems bears some surprises in the sense that a reconfiguration problem can be hard although its underlying combinatorial problem is tractable and vice versa. We give an overview of some recent results and techniques in this area, with a focus on vertex coloring and matchings (and their relation to sliding token puzzles).

Dr.-Ing. Moritz Mühlenthaler

Department Informatik, Friedrich-Alexander-Universität Erlangen-Nürnberg