[3L4-GS-1] Fundamental AI, theory, algorithm:

[3L4-GS-1-03] Combinatorial Reconfiguration in Constraint Satisfaction on a 3-Element Set: When Solution Space is Majority-closed

〇Hajime Hironaka¹, Kei Kimura¹, Akira Suzuki², Makoto Yokoo¹ (1. Kyushu University, 2. Tohoku University)

Keywords:Combinatorial Reconfiguration, Constraint Statisfaction Problem, Majority Operation

This study considers combinatorial reconfiguration in constraint satisfaction on a 3-element set. Combinatorial reconfiguration is a problem of determining whether it is possible to reconfigure one solution to another by transforming step by step and maintaining intermediate solutions are also feasible. On a 2-element set, Gopalan et al. and Schwerdtfeger proved that the reconfiguration problem is solvable in polynomial time if the solution space of the constraint satisfaction problem is majority-closed. This study extends these results to constraint satisfaction on a 3-element set. In this case, the majority operation is not uniquely defined and returns an arbitrary value if all three arguments are different, but we show that the reconfiguration problem is solvable in polynomial time if the solution space is closed by some majority operation.