group A01

Computer Science Approach for Expanding Combinatorial Reconfiguration:Toward Automatic Generation of Algorithms


Founding “algorithmic meta-theorems” for combinatorial reconfiguration, and aiming at automatic generation of combinatorial reconfiguration algorithms.

The first step of algorithm development, not only for combinatorial reconfiguration, is performed as case studies. Namely, for each problem at hand, a new method is developed, and an algorithm is designed that is suited for that particular problem. The accumulation of case studies occasionally results in “quite similar” algorithms, that is, algorithms that use essentially the same technique but deal with different problems. This leads to the question “for which problems the technique is effective,” which is the essence of algorithmic methodology. This is the study of algorithmic meta-theorems. In summary, meta-theorems constitute the research that sublimates the accumulated algorithmic techniques from case studies into a “unified design methodology.”

Algorithms for combinatorial reconfiguration have extensively been developed since around 2013, and have been appearing in premier international conferences of the theory of algorithms. On the other hand, case studies are not accumulated satisfactorily, and the study of algorithmic meta-theorems is not cultivated. Group A01 aims at accumulating case studies by challenging unsolved problems of combinatorial reconfiguration and founding algorithmic meta-theorems for combinatorial reconfiguration.