The First International Workshop on
Combinatorial Reconfiguration (CoRe 2015)

February 18-20, 2015      Sendai, Japan

The first international workshop on Combinatorial Reconfiguration (CoRe 2015) will be held on February 18-20, 2015 in Sendai, Japan. This is the first workshop dedicated to the topic of "combinatorial reconfiguration."

What is "combinatorial reconfiguration" ?

Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a combinatorial problem such that all intermediate results are also feasible. For example, given two specified satisfying assignments A and B to a Boolean formula, one might ask whether A can be transformed into B by changing the assignment of one variable at a time such that each intermediate assignment is also satisfying. Thus, a reconfiguration problem asks the "reachability" on the solution space, whereas the original problem asks the "existence" of at least one feasible solution.

The original SAT problem asking
the "existence" of satisfying assignments (blue circles).

The reconfiguration problem for SAT asking
the "reachability" between two satisfying assignments (red path).

The main challenge for solving reconfiguration problems efficiently is that the number of feasible solutions is usually exponential in the input size, so to obtain efficient search algorithms, one cannot simply enumerate them; smarter search methods are required. Indeed, for most reconfiguration problems, the reachability question is PSPACE-hard in general, although efficiently solvable cases can be identified.

Steering Committee

Organizing Committee

Co-hosted by Graduate School of Information Sciences, Tohoku University, Japan.

Photo credit: Miyagi Prefecture Sightseeing Section