PIMS - UManitoba Computer Science Lecture: Naomi Nishimura

n this talk, I will present two recent results in the area of combinatorial reconfiguration, in the process providing both a primer for those unfamiliar with the reconfiguration framework and insights into new directions for those already familiar with previous work in the area. Reconfiguration provides a way of exploring the relationships among configurations (typically solutions to an instance of a problem), where a reconfiguration step transforms one configuration into another by a small, incremental change.

In the result on subgraphs, each configuration is a subset of edges or vertices of an input graph that form a subgraph in a specified class. We consider the complexity of determining whether or not one configuration can be transformed (or, is reconfigurable) to another by a sequence of reconfiguration steps for different choices of graph classes and representations of subgraphs.

In studying graph minors, we consider each configuration to be a labeling of the vertices of a graph G by the vertices of a graph H. We then determine the properties of both G and H that result in each configuration being reconfigurable to any other.