Studies on Implicit Graph Enumeration Using DDs
2021年度研究会推薦博士論文速報
［アルゴリズム研究会］
中畑 裕
（奈良先端科学技術大学院大学先端科学技術研究科情報科学領域 助教）
邦訳：決定グラフを用いた暗黙的グラフ列挙に関する研究
■キーワード
決定グラフ／列挙／アルゴリズム
【背景】グラフ中のパスやサイクルなど，部分グラフの列挙は重要
【問題】部分グラフの数は膨大で，すべてを陽に列挙することは困難
【貢献】決定グラフを用いた暗黙的グラフ列挙アルゴリズムを提案
決定グラフを用いた暗黙的グラフ列挙
グラフとは，頂点と辺の集合で表現される離散構造である．グラフは最も基本的な離散構造の1つであり，通信網，道路網，人間関係など，実世界の様々なネットワーク構造を数学的にモデル化するために広く使われている．与えられたグラフの中に内包されている部分グラフを解析することは，グラフに関する多くの組合せ問題を深く理解するために重要である．
近年，決定グラフ（DD）と呼ばれる圧縮データ構造の技法が進展しており，従来，陽に列挙することが不可能だった膨大な個数の組合せ集合データを，圧縮して暗黙的に効率よく表現することが可能となってきている．この技法を用いて，グラフに含まれる膨大な個数の部分グラフをDDにより暗黙的に列挙することで，グラフに関するさまざまな問題の厳密解を高速に求めることや，解の個数を厳密に数え上げることが可能となる．本研究は，DDを用いた部分グラフ列挙の技法について，いくつかの暗黙的列挙アルゴリズムを提案し，それらのアルゴリズムの計算量を理論的に見積もるとともに実験的に効率を評価したものである．
本研究では4つの問題を扱ったが，本稿では特に「禁止マイナー制約を満たす部分グラフの列挙」$${^{1）}}$$について紹介する．この研究では，DDで効率よく列挙できる部分グラフの種類を飛躍的に拡大した．
従来のDDによる部分グラフ列挙法では，部分グラフの各頂点の次数（接続する辺の本数）と頂点同士の連結性によって特徴づけできる部分グラフ（たとえば，パス，サイクル，全域木，クリーク，マッチングなど）を効率良く列挙できることが知られていた．一方で，平面的グラフ，外平面的グラフなど，重要であるがDDで効率良く列挙する方法が知られていないグラフも多かった．本研究では，グラフの「禁止マイナー制約」による特徴づけに注目し，そのような特徴づけを持つ部分グラフを列挙する方法を提案している．
マイナーとは，グラフの頂点削除，辺削除，辺縮約（辺の両端点を1つの頂点にまとめる操作）を繰り返して得られるグラフのことを指し，禁止マイナー制約とは指定されたグラフをマイナーとして含まないという制約である．禁止マイナー制約で特徴づけ可能なグラフとしては，平面的グラフ，外平面的グラフ，直並列グラフ，カクタスグラフなどが挙げられる．本研究ではマイナーの特殊ケースである「トポロジカルマイナー」を列挙するアルゴリズムを新たに提案し，これを用いて一部の禁止マイナー制約で特徴づけられる部分グラフを全列挙することが可能になることを示した．
本手法を用いてグラフに含まれる平面的な部分グラフを全列挙するアルゴリズムを実装し，実験により，提案アルゴリズムが愚直なバックトラック法より最大で約10万倍高速に，与えられたグラフのすべての平面的部分グラフを見つけられることを報告している．
本研究ではほかにも一般のグラフに対する避難所割当の列挙$${^{2）}}$$，バランス良いグラフ分割の列挙$${^{3）}}$$，項分岐決定グラフ（決定グラフの拡張）を用いた部分グラフの列挙$${^{4）}}$$という問題を扱った．これらの問題を通し，DDを用いた暗黙的グラフ列挙技法の高速化と汎用化に寄与したといえる．
■Webサイト／動画／アプリなどのURL
https://www.youtube.com/watch?v=Q4gTV4r0zRs
参考文献
1）Nakahata, Y., Kawahara, J., Horiyama, T. and Minato, S. : Implicit Enumeration of Topological-minor-embeddings and Its Application to Planar Subgraph Enumeration, Proceedings of the 14th International Conference and Workshops on Algorithms and Computing (WALCOM 2020), pp.211–222 (2020).
2）Nakahata, Y., Kawahara, J., Horiyama, T. and Kasahara, S. : Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 101-A(9):1363–1374 (2018).
3）Nakahata, Y., Kawahara, J. and Kasahara, S. : Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams, In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA 2018), pp.21:1–21:13 (2018).
4）Nakahata, Y., Nishino, M., Kawahara, J. and Minato, S. : Enumerating All Subgraphs Under Given Constraints Using Zero-suppressed Sentential Decision Diagrams, In Proceedings of the 18th International Symposium on Experimental Algorithms (SEA 2020), pp.9:1–9:14 (2020).
（2022年6月1日受付）
（2022年8月15日note公開）
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
取得年月日：2021年9月
学位種別：博士（情報学）
大学：京都大学
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
推薦文［コンピュータサイエンス領域］アルゴリズム研究会
本論文は，避難所割当問題や，バランスの良いグラフ分割問題など，グラフ構造に関連する4つの課題を設定し，それらに対して効率の良い暗黙的列挙アルゴリズムを新規に提案し，理論的解析と実験的評価を行ったもので，国際会議SEA 2020やWALCOM 2020に論文採択されるなど国際的にも高く評価されている．
研究生活 競技プログラミングをきっかけにアルゴリズムに興味を持ち，修士課程からこのテーマの研究を始めました．先生方にアドバイスをいただきつつ自由に研究に取り組ませていただいたことは大変貴重な経験になりました．博士課程中にCOVID-19の影響で研究活動が制限され，モチベーションを保つのが難しい時期もありましたが，なんとかやりきれてよかったと思います．お世話になった皆様に感謝いたします．