Title:
An introduction to the independent set reconfiguration problem (ISReconf)

Speaker:
HOANG, Duc Anh (JAIST)

Abstract:
In real-world situations, there may exist many feasible solutions which can be used to solve a single problem. Usually, for saving time, money, etc., it is required that one need to find a way to transform (reconfigure) one solution to another. This gives rise to the study of a collection of combinatorial problems which is known as reconfiguration problems. In my poster session, we will present a brief introduction to reconfiguration problems and some of their variants, especially the independent set reconfiguration problem (ISReconf).

Reconfiguration problems are the set of problems in which we are given a set of configurations, together with some reconfiguration rule(s). The question is, using a given rule, can we find a step-by-step transformation which transform one configuration to another? Readers may remember the Rubik's cube and its relatives as examples of reconfiguration puzzles. Recently, many kind of reconfiguration problems have been studied extensively for several well-known problems, including independent set, satisfiability, set cover, clique, matching, vertex-colouring, list edge-colouring, etc. Among many variants of reconfiguration problems, the ISReconf problem is of particular theoretical interest. Recall that an independent set in a graph G is a set of pairwise non-adjacent vertices. Given a graph G and two independent sets I, J, imagine that a token (coin) is placed at each vertex of I. The ISReconf problem asks whether there is a way to transform the set of tokens using a given rule so that after transforming, each vertex of J contains a token and all intermediate sets of tokens areindependent. In my poster session, beside introducing what ISReconf is, I explain why researchers are interested in it, what results have been discovered so far, what tools are useful for ISReconf study, and which direction that researchers will find interesting.