Web Portal for Combinatorial Reconfiguration
This is a website portal for Combinatorial Reconfiguration (CoRe).
What is "combinatorial reconfiguration" ?
Reconfiguration problems arise when we wish to find a step-by-step transformation between feasible solutions of a combinatorial (search) 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 search 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.
(For more details, please go to "Introduction" page.)