Mini-symposium on Combinatorial Reconfiguration
SIAM DM'16
Back to Homepage
(From left to right, Jesus Salas, Takehiro Ito, myself, Amer Mouawad, Carl Feghali, Jonathan Noel)
The program was as follows.
-
Takehiro Ito, Invitation to Combinatorial Reconfiguration (slides).
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a combinatorial problem such that all intermediate results are also feasible. They are PSPACE-complete for most underlying NP-complete problems, and in P for several polynomial-time solvable underlying problems, although there are exceptions to both general patterns. In this talk, I will give a broad introduction and invite you to this exciting new area.
-
Carl Feghali, Kempe Equivalence of Colourings of Graphs (slides).
Let G be a graph with colouring α. Let a and b be two colours. Then a connected component of the subgraph induced by those vertices coloured either a or b is known as a Kempe chain. A colouring of G obtained from α by swapping the colours on the vertices of a Kempe chain is said to have been obtained by a Kempe change. Two colourings of G are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. In this talk, I will survey some of the existing results, cover common proof techniques and mention some open problems in this area.
-
Jesus Salas, Kempe reconfiguration and Potts antiferromagnets (slides).
The Potts model plays an important role in Statistical Mechanics: it is very simple to formulate, but highly nontrivial. Many unusual features occur in its antiferromagnetic regime; in particular, the existence of critical points at zero temperature. Monte Carlo Markov chains have been very often used to study the properties of this model. The Wang--Swendsen--Koteck\'y (WSK) cluster algorithm is the most popular to simulate Potts antiferromagnets. Moreover, at zero temperature, this algorithm is equivalent to Kempe reconfiguration. We shall review whether the zero-temperature WSK algorithm is irreducible or not on several regular graphs embedded on a torus. Non-bipartite graphs are the most challenging ones: in some physically important cases, the algorithm fails to be irreducible.
-
Amer Mouawad, Shortest reconfiguration paths in the solution space of Boolean formulas (slides).
Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment s to another satisfying assignment t of an input Boolean formula. Earlier work characterized the complexity of deciding the existence of a sequence of flips between two given satisfying assignments using Schaefer's framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the growing set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though the sequence flips variables that have the same value in both s and t. This is in contrast to most reconfiguration problems studied so far, where polynomial-time algorithms for computing the shortest path were known only for cases where the path modified no more than the symmetric difference of s and t. Our proof uses Birkhoff's representation theorem on a set system that we show to be a distributive lattice. The technique provides insights and can perhaps be used for other reconfiguration problems as well.
-
Jonathan Noel, Reconfiguring Graph Homomorphisms and Colourings (slides).
The starting point for this talk is the following question: given two proper k-colourings of a graph G, is it possible to transform one colouring into the other by changing the colour of one vertex at a time so that every intermediate colouring is proper k-colouring? The computational complexity for this problem exhibits a rather surprising dichotomy: it is polynomial if k≤3 and PSPACE-complete if k≥4.
We consider the analogous problem for graph homomorphisms, which generalize graph colourings. Here, the complexity is only known for some restricted families of `target graphs' H
including (1) C4-free graphs, (2) `circular cliques' and (3) odd wheels. We discuss some of the ideas behind the proofs of these results and propose several avenues for future research.
Back to Homepage