Fast Algorithm for Enumerating Graph Minors in a Graph

本年度は，本研究課題で取り組む列挙問題と関係が深い，組合せ遷移に関する研究を行った．組合せ遷移とは，ある決定問題の解2つが与えられたとき，一方から他方へ，局所的な変形操作の繰り返しで，解であることを保ったまま到達できるかという問題である．組合せ遷移は近年盛んに理論的な研究が行われ，配電網設計などへの実用も進んでいるが，既存の研究は無向グラフに対するものが多かった．そこで本研究課題では有向グラフ上の組合せ遷移に注目し，この分野における先駆的な成果を上げた．具体的には，有向グラフ中の有向木の遷移可能性判定が多項式時間で解けることを示した．また，有向木の根が固定の場合や，全域有向木の場合には最短の遷移列を見つける線形時間アルゴリズムを与えた．さらに，有向木を有向パスに限定した場合や，有向非巡回グラフに一般化した場合にはPSPACE完全であることを示した．これらの成果は国内ワークショップJCCA 2021, 国際ワークショップWorkshop on Combinatorial Reconfiguration（国際会議ICALP 2021と併催），査読付き国際会議COCOON 2021で発表した．また，本年度は最終年度につき，本研究課題で得られた成果を博士論文の形にまとめた．博士論文のテーマは決定グラフを用いた暗黙的な部分グラフの列挙である．具体的な成果としては，一般のグラフに対する避難所割当の列挙, バランス良いグラフ分割の効率良い列挙, 禁止マイナーで特徴づけられる部分グラフの列挙，ゼロサプレス型項分岐決定グラフを用いた部分グラフの列挙を記載している．また，分野全体のサーベイや非専門家向けの技術的準備も付与することで，本研究課題の成果を利用可能な形で体系的にまとめることができたと考えている．

本年度は，本研究課題で取り組む列挙問題と関係が深い，組合せ遷移に関する研究を行った．組合せ遷移とは，ある決定問題の解2つが与えられたとき，一方から他方へ，局所的な変形操作の繰り返しで，解であることを保ったまま到達できるかという問題である．組合せ遷移は近年盛んに理論的な研究が行われ，配電網設計などへの実用も進んでいるが，既存の研究は無向グラフに対するものが多かった．そこで本研究課題では有向グラフ上の組合せ遷移に注目し，この分野における先駆的な成果を上げた．具体的には，有向グラフ中の有向木の遷移可能性判定が多項式時間で解けることを示した．また，有向木の根が固定の場合や，全域有向木の場合には最短の遷移列を見つける線形時間アルゴリズムを与えた．さらに，有向木を有向パスに限定した場合や，有向非巡回グラフに一般化した場合にはPSPACE完全であることを示した．これらの成果は国内ワークショップJCCA 2021, 国際ワークショップWorkshop on Combinatorial Reconfiguration（国際会議ICALP 2021と併催），査読付き国際会議COCOON 2021で発表した．また，本年度は最終年度につき，本研究課題で得られた成果を博士論文の形にまとめた．博士論文のテーマは決定グラフを用いた暗黙的な部分グラフの列挙である．具体的な成果としては，一般のグラフに対する避難所割当の列挙, バランス良いグラフ分割の効率良い列挙, 禁止マイナーで特徴づけられる部分グラフの列挙，ゼロサプレス型項分岐決定グラフを用いた部分グラフの列挙を記載している．また，分野全体のサーベイや非専門家向けの技術的準備も付与することで，本研究課題の成果を利用可能な形で体系的にまとめることができたと考えている．