A graph vertex-subset problem defines which subsets of the vertices of an input graph are
feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of …

We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs
under all three commonly studied reconfiguration models. We show that under the token …

Suppose that we are given two independent sets I b and I r of a graph such that| I b|=| I r|,
and imagine that a token is placed on each vertex in I b. Then, the sliding token problem is to …

Let I be an independent set of a graph G. Imagine that a token is located on every vertex of I.
We can now move the tokens of I along the edges of the graph as long as the set of tokens …

Sliding Token is a natural reconfiguration problem in which vertices of independent sets are
iteratively replaced by neighbors. We develop techniques that may be useful in answering …

Graph constraint logic is a framework introduced by Hearn and Demaine, which provides
several problems that are often a convenient starting point for reductions. We study the …

We study the perfect matching reconfiguration problem: Given two perfect matchings of a
graph, is there a sequence of flip operations that transforms one into the other? Here, a flip …

We explore a reconfiguration version of the dominating set problem, where a dominating set
in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S …

The dynamics of real-world applications and systems require efficient methods for improving
infeasible solutions or restoring corrupted ones by making modifications to the current state …

Given two k-independent sets I and J of a graph G, one can ask if it is possible to transform
the one into the other in such a way that, at any step, we replace one vertex of the current …