Oct 20, 2015: Paul Bonsma: Algorithmic techniques for reconfiguration problems

October 20, 2015Algorithmic techniques for reconfiguration problems
Room: HB 2APaul Bonsma

Reconfiguration problems are computational or combinatorial problems related to the exploration of symmetric solution/state spaces. A solution graph (or reconfiguration graph) concept S is obtained by defining problem instances (such as graphs), solutions for these instances (such as proper colorings of the graph), and a symmetric adjacency relation between the solutions (such as recoloring a single vertex). This defines a solution graph S(G) for each instance G.

Two examples of well-studied computational reconfiguration problems are:

  (Connectivity problem:)
  Given an instance G, is the solution graph S(G) connected?

  (Reachability problem:)
  Given an instance G and two solutions A and B, does S(G) contain a path between A and B?

Although most problems of this kind are hard (typically PSPACE-complete), some efficient algorithms are known (meaning polynomial time or fixed parameter tractable algorithms). In this talk I will give examples and an overview of techniques for obtaining efficient algorithms for such problems. The main focus will be on graph problems such as the reconfiguration of independent sets or shortest paths in a graph.