[2I5-OS-9b] AIと制約プログラミング

[2I5-OS-9b-02] A Study on Solving Independent Set Reconfiguration Problem of Sliding Tokens with Answer Set Programming

〇Kazuki Takada¹, Yuya Yamada², Mutsunori Banbara² (1. School of Informatics, Nagoya University, 2. Graduate School of Informatics, Nagoya University)

Keywords:Answer Set Programming, Independent Set Reconfiguration Problem, Sliding Token Problem, Independent Set, Combinatorial Reconfiguration

The Independent Set Reconfiguration Problem (ISRP) is defined as determining, for a given independent set problem instance and its two independent sets, whether one can be reachable to another via a sequence of independent sets, subject to some transition constraint. In this paper, we describe an approach to solving ISRP based on Answer Set Programming (ASP). We focus on the Token Sliding (TS) which is one of well-studied transition constraints. TS enforces that, in each transition of the sequence, the exact one node in independent set can change into its adjacent node. We present two ASP encodings for ISRP solving under TS: the edge-oriented and node-oriented encodings. In particular, the node-oriented encoding can concisely express the TS transition constraint. To evaluate our approach, we show some experimental results on the benchmark set of CoRe Challenge 2022.