[4R1-OS-13] OS-13

[4R1-OS-13-02] Improved ASP Encoding for Solving Independent Set Reconfiguration Problem

〇Ayumu Hirasawa¹, Tomohiro Mizowaki¹, Kazuki Takada¹, Mutsunori Banbara¹ (1. Graduate School of Informatics, Nagoya University)

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

独立集合遷移問題とは，基となる独立集合問題とその2つの実行可能解が与えられたとき，一方から他方へ，遷移制約を満たしつつ，実行可能解のみを経由して到達可能かを判定する問題である．この問題は，最も広く研究されている組合せ遷移問題の1つであり，一般的にPSPACE完全であることが知られている．また，国際組合せ遷移競技会CoRe Challenge 2022-2023のベンチマークとして使用されるなど，その実践的な解法アルゴリズムの研究が盛んに行われている．

本稿では，解集合プログラミングを用いた，独立集合遷移問題を解く新たな符号化を提案する．既存符号化は，各遷移においてどの頂点を独立集合に含めるかという点に着目する一方，提案符号化は，各遷移において独立集合に含まれるどの頂点が取り除かれるかという点に着目するという大きな違いがある．提案符号化の有効性を評価するため，CoRe Challenge 2022問題集を用いた実験を行った．その結果，提案符号化は，CoRe Challenge 2023の複数部門で優勝した既存符号化と比較して，より多くの問題を解き，その優位性を確認できた．