Animation scientifique

Here, reconfiguration asks, given two solutions to some problem, if one can be stepwise transformed into the other, while keeping a solution throughout. We focus on problems where the modifications are tokens traveling along edges of a graph: Independent Set Reconfiguration under Directed Token Sliding (IS-DTS) and Constrained Colored Token Swapping (CCTS).

We discuss lower bounds on the (parameterized) complexity: IS-DTS is W[2]-hard when parameterized by the number of tokens k and treewidth (tw); it does not admit a polynomial kernel in DAGs for k+tw; and CCTS is NP-hard even when the (base) graph is a spider. While the three results are different on the surface, they all three require gadgets that tightly control the possible moves the tokens can make throughout the reconfiguration sequence.