While an optimization problem aims to find a solution with the best property or properties, combinatorial reconfiguration formalizes the frequently-arising phenomenon of making incremental changes to modify one feasible solution into another in a step-by-step manner. Since its inception in 2011, the reconfiguration framework has unified and encouraged research on the theory and application of relationships among solutions to classical problems. Using a graph representation, each solution (or configuration) is connected by an edge to any other configuration that results from a simple modification step. Results in the area have considered various algorithmic and structural questions about such graphs (e.g. reachability of one configuration from another, connectivity among all configurations, or diameter that is the maximum distance between configurations), typically in relation to a specific problem.

Understanding of the framework itself, however, has remained more elusive. As one example, there is not yet a clear understanding of the correspondence between tractability of classical problems and tractability of reachability problems derived from those classical problems. Moreover, when reachability is intractable (PSPACE-hard), the dividing lines between tractable and intractable classes of instances do not yet follow understood patterns.

The goal of this Dagstuhl Seminar is to bring together researchers specializing in reconfiguration and related fields to both strengthen and expand the community and to study further natural research directions for the future of the field, with a focus on two main directions.

First, we aim to design generic meta-theorems (including meta-algorithmic results) for reconfiguration problems, namely results that evaluate the complexity of some classes of, rather than simply individual, problems. This research direction has attracted substantial attention in optimization thanks to the existence of a broad and generic algorithmic toolbox. Unfortunately, most of the tools used to obtain results in optimization are not adapted to design algorithms for reconfiguration problems.

Even if there exist some reconfiguration meta-theorems, little is known compared to optimization problems. To develop that field, we aim to promote the development of a comparable toolbox for reconfiguration problems during this workshop. That is, we intend to design new techniques to solve reconfiguration problems and identify generic classes of problems for which such methods have not yet been developed.

Second, we aim to identify and study the most important questions about structural properties of reconfiguration graphs with a focus on lower bounds for combinatorial reconfiguration, which – despite considerable recent research attention – remain surprisingly poorly understood. Indeed, even though most reconfiguration problems are known to be PSPACE-complete (implying super-polynomial diameter for reconfiguration graphs under the assumption of NP ≠ PSPACE), very few explicit constructions are known and methods to accurately evaluate the diameter of reconfiguration graphs are very rare.

These themes capture deep theoretical questions and broad unifying principles that have recently come to the forefront of this rapidly growing field. To achieve these goals, the seminar aims to bring together researchers from diverse areas, including complexity theory, structural graph theory, logic, and algorithm design, to benefit from the exchange of ideas and approaches in addressing these key challenges in the field.

Creative Commons BY 4.0

Nicolas Bousquet, Takehiro Ito, Naomi Nishimura, and Sebastian Siebertz