[2Yin-A] Poster 3

[2Yin-A-11] Reconfiguration CSP on a 4-Element Set: When Solution Space Is Closed Under a Symmetric Majority Operation

〇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 4-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 the feasibility of intermediate solutions. On a 2- and 3-element set, it was proved that the reconfiguration problem is solvable in polynomial time if the solution space of the constraint satisfaction problem is majority-closed. This result was shown by Gopalan et al. and Schwerdtfeger for a 2-element set and by us for a 3-element set. On a 3-or-more-element set, the majority operation is not uniquely defined and returns an arbitrary value if all three arguments are different. This study extends these results to constraint satisfaction on a 4-element set. In this case, we proved that the reconfiguration problem is solvable in polynomial time if the solution space is closed under some symmetric majority operation. A majority operation is symmetric if the operation returns the same value when the arguments are permuted.