Combinatorial Reconfiguration
組合せ遷移問題の理論と応用
Theory and Applications of Combinatorial Reconfiguration
研究概要
組合せ遷移では，定められた変換規則を繰り返し適用することで，ある実行可能解から別の実行可能解へと変形できるかを問う問題を扱います．本テーマでは，古典的組合せ構造に対する遷移問題の計算複雑性を解明するとともに，最短遷移手順の算出や，解の品質を改善しながら遷移を行う最適化遷移といった発展的問題にも取り組んでいます．近年は，遷移ルールを緩和あるいは拡張した枠組みの研究で大きな成果を上げています．
（ここに図や画像を挿入する予定です）
研究テーマ
古典的組合せ構造に対する遷移問題の計算複雑性
グラフ彩色・独立集合・支配集合・フィードバック頂点集合の遷移や，整数線形方程式系の遷移など，多様な組合せ構造に対する到達可能性判定問題に取り組んでいます．問題がPSPACE完全となる構造的境界を明らかにしたり，特定のグラフクラスやパラメータに対する多項式時間アルゴリズム・FPTアルゴリズムを設計したりするなど，計算複雑性の精緻な解明を進めています．
最適化遷移と拡張遷移ルール
解の値を改善しながら遷移を行う最適化遷移問題や，遷移ルールの緩和・拡張により新たな構造的性質が現れる枠組みの研究に取り組んでいます．とくに，拡張遷移ルールの下での誘導部分グラフ同型関係の遷移問題に関する成果は，従来の遷移枠組みでは捉えられなかった現象を明らかにし，組合せ遷移の理論的地平を広げる研究を展開しています．
関連する発表
- 学術雑誌Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura and Xiao Zhou, "Decremental optimization of vertex-coloring under the reconfiguration framework," International Journal of Computer Mathematics: Computer Systems Theory, vol. 8, issue 1, part 2, pp. 80-92, 2023.
- 学術雑誌Takehiro Ito, Haruka Mizuta, Naomi Nishimura and Akira Suzuki, "Incremental optimization of independent sets under the reconfiguration framework," Journal of Combinatorial Optimization (JOCO), vol. 43, issue 5, pp. 1264-1279, 2022.
- 学術雑誌Tatsuhiro Suga, Akira Suzuki, Yuma Tamura and Xiao Zhou, "Changing induced subgraph isomorphisms under extended reconfiguration rules," Information and Computation, vol. 307, article 105367, pp.1-21, 2025.