Paul Bonsma
Twente, NL
TITLE: Independent Set Reconfiguration in Cographs
ABSTRACT:
We study the following independent set
reconfiguration problem: given two independent
sets A and B (of equal size) of a graph G, does
there exist a sequence of independent sets of G
that starts with A, ends with B, such that every
independent set in the sequence can be obtained
from the previous one by replacing one vertex?
This problem is PSPACE-hard in general. In this
talk we will show that it can be solved in
polynomial time if G is a cograph, or more
generally: if G can be obtained from a set of
simple base graphs by applying disjoint union and
complete join operations. These base graphs should
be from a graph class for which the problem itself
can be solved efficiently, and for which a maximum
independent set can be computed efficiently.
Chordal graphs are an example of such a class.
This result is one of the first to demonstrate how
dynamic programming can be used to solve
(PSPACE-hard) reconfiguration problems for
restricted graph classes. The talk will start with
an overview of many recent results on similar
reconfiguration problems.