JAIST Repository
https://dspace.jaist.ac.jp/Title

グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究

Author(s)大舘, 陽太Citation

科学研究費助成事業研究成果報告書: 1‑5Issue Date

2016‑06‑03

TypeResearch Paper

Text version

publisher

URL

http://hdl.handle.net/10119/13677

RightsDescription

若手研究(B), 研究期間：2013〜2015, 課題番号
：25730003, 研究者番号：80610196, 研究分野：グラ
フアルゴリズム

Japan Advanced Institute of Science and Technology

２版

様式

Ｃ−１９、Ｆ−１９、Ｚ−１９ （共通）

科学研究費助成事業

研究成果報告書
平成 ２８ 年

６ 月

３ 日現在

機関番号： １３３０２
研究種目： 若手研究(B)
研究期間： 2013 〜 2015
課題番号： ２５７３０００３
研究課題名（和文）グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究

研究課題名（英文）Fixed width parameter algorithms for the graph isomorphism problem

研究代表者
大舘陽太（Otachi, Yota）

北陸先端科学技術大学院大学・情報科学研究科・助教
研究者番号：８０６１０１９６
交付決定額（研究期間全体）：（直接経費）

3,200,000 円

研究成果の概要（和文）：連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した．該
当論文では，問題そのものを直接解くのではなく，ある種のメタアルゴリズムを作るという方針をとった．グラフ同型性判定の古典的アルゴリズムとして，Weisfeiler‑Lehmanアルゴリズムという手法がある．この論文では，このWeisfei
ler‑Lehmanを一般化・高速化し，ある種のグラフ幅パラメータが定数の場合に対する固定パラメータ容易性を示した．
関連して，入力グラフがある種の禁止構造を持つ場合を研究した．あるグラフを誘導マイナーとして含まないクラスに対する同型性判定問題に対して計算量二分法を与えた．

研究成果の概要（英文）：We showed that the graph isomorphism problem is fixed‑parameter tractable whenparameterized by root‑connected tree distance width. To show the result, we modified the classic
Weisfeiler‑Lehman algorithm so that it works not only for all vertex subsets of size k but also for
restricted family of vertex subsets of size k. Furthermore, the modified algorithm runs in FPT time withthe parameter k. Then we showed that we can apply the algorithm to the graph isomorphism problem
parmeterized by several graph width parameters including root‑connected tree distance width.
We also studied the graph isomorphism problem for graph classes forbidding a single graph as an inducedminor. We showed a complexity dichotomy with respect to the forbidden induced minor.

研究分野： グラフアルゴリズム
キーワード： グラフアルゴリズム

グラフ同型性判定問題

グラフ幅パラメータ

様式

Ｃ－１９、Ｆ－１９、Ｚ－１９（共通）１．研究開始当初の背景
本研究では，与えられた二つのグラフが“同じ”であるか否かを判定するグラフ同型性判定問題を扱う．より正確には以下のとおり定式化される: グラフ G は頂点集合 V(G)と，頂点の非順序対の集合である辺集合 E(G)によって表現される．二つのグラフ G と H が同型であるとは，V(G)から V(H)への辺関係を保存する全単射が存在することである．例えば下図は，同型なグラフの対（左側）と非同型なグラフの対（右側）の例である．

うまく頂点集合を選ぶことで最小化された幅を，そのグラフの道距離幅と呼ぶ．距離構造を作る際に，木状の枝分かれを許すのが木距離構造である．あるレベルがそこから下を見た時に非連結になる場合に枝分かれを許す（上図参照）．定義より木距離幅は道距離幅以下である．木距離幅および道距離幅は，Yamazaki 等によってグラフ同型性判定問題の研究のために導入された．
本研究では，木距離幅に制限を加えた連結木距離幅および更に制限した連結道距離幅を扱う．これらのパラメータは，選ぶ頂点集合を連結グラフを誘導するものに制限したもので，研究代表者によって同型性判定問題の研究のために導入された．

二つの構造が同じかどうか判定するというのは基本的な問題であるが，グラフ同型性判定問題の計算複雑性は，1970 年代初頭からの多くの研究者たちの試みにもかかわらず未だ不明である．この問題は「P vs. NP」問題とも深く関係し，完全に解明することは非常に困難であると考えられる．一方，特殊な場合に対して多項式時間アルゴリズムを開発するという試みが広く行われている．例えば，木幅と呼ばれるグラフの複雑度を表すパラメータがある定数 k で抑えられるグラフに対しては，グラフ同型性判定問題が O(nk+4)時間で解けることが 1990 年代初頭には既に知られていた．
（ここで，n はグラフの頂点数．）一方，この問題が固定パラメータ容易であるか，つまり，ある関数 f と定数 c があって，O(f(k)・nc)時間で解けるかというのは重要な未解決問題であった．

４．研究成果主結果として，連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した．該当論文（次項の学会発表
10 番）では，問題そのものを直接解くのではなく，ある種のメタアルゴリズムを作るという方針をとった．グラフ同型性判定の古典的アルゴリズムとして，Weisfeiler-Lehman アルゴリズムという手法がある．この論文では，この Weisfeiler-Lehman を一般化・高速化し，ある種のグラフ幅パラメータが定数の場合に対する固定パラメータ容易性を示した．

２．研究の目的
本研究ではグラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの開発を行うことを目的とした．未解決である特殊ケースで最も重要なものの一つである，木幅および関連グラフパラメータが制限された場合に対する固定パラメータ容易アルゴリズムの研究を行う．特に具体的な目標として，「木距離幅が固定されたグラフクラスに対する固定パラメータ容易同型性判定アルゴリズムの設計」を目指す．これは木幅に関する未解決問題を部分的に解決するものである．
３．研究の方法
グラフから頂点をいくつか選び，残りの頂点を選ばれた頂点からの距離によってレベル分けする事を考える．このとき出来る構造を道距離構造と呼ぶ（下図参照）．全レベルのサイズの最大値をこの道距離構造の幅と呼ぶ．
aaabbbcdfegcgfdecdfeg

関連結果として，入力グラフがある種の禁止構造を持つ場合に対しても研究した．学会
発表 5 番では，あるグラフ H を誘導マイナーとして含まないグラフクラスに対する同型性判定問題を研究し，計算量二分法を与えた．
この問題は 1980 年代に Ponomarenko によって研究されていたが，与えられていた結果は部分的なもので，さらに証明には本質的な誤りが含まれていた．我々は，その誤りを指摘・修正し，さらに完全な計算量二分法にするべく結果を拡張した．
雑誌論文 1 では，グラフ同型性判定問題の一般化である部分グラフ同型性判定問題を研究した．結果として，幾何的な交差表現を持つグラフクラスに対して，既知の多項式時間可解の場合を拡張子，さらに，既知の場合よりさらに制限した NP 困難性を示した．
５．主な発表論文等（研究代表者、研究分担者及び連携研究者には下線）〔雑誌論文〕（計 12 件）
1. Matsuo Konagaya, Yota Otachi, Ryuhei
Uehara. Polynomial-time algorithms
for Subgraph Isomorphism in small
graph classes of perfect graphs.
Discrete Applied Mathematics (査読有)199 (2016) 37-45.

2. Masashi Kiyomi, Yoshio Okamoto, Yota
Otachi. On the treewidth of toroidalgrids. Discrete Applied Mathematics（査読有） 198 (2016) 303-306.
3. Takehiro Ito, Shin-ichi Nakano,
Yoshio Okamoto, Yota Otachi, Ryuhei
Uehara, Takeaki Uno, Yushi Uno. A
polynomial-time approximation scheme
for the geometric unique coverage
problemonunitsquares.
Computational Geometry: Theory andApplications （査読有） 51 (2016) 2539.
4. Erik D. Demaine, Martin L. Demaine,
Eli Fox-Epstein, Duc A. Hoang,Takehiro Ito, Hirotaka Ono, Yota
Otachi, Ryuhei Uehara, Takeshi Yamada.
Linear-time algorithm for sliding
tokens on trees. Theoretical Computer
Science （査読有） 600 (2015) 132-142.
5. Masayoshi Matsushita, Yota Otachi,Toru Araki. Completely independent
spanning trees in (partial) k-trees.
Discussiones
Mathematicae
GraphTheory （査読有） 35 (2015) 427-437.
6. Pavel Klavík, Jan Kratochvíl, YotaOtachi, Toshiki Saitoh. Extending
partial representations of subclasses
ofchordalgraphs.
TheoreticalComputer Science （査読有） 576 (2015)85-101.
7. Kazuyuki Amano, Kyaw May Oo, Yota
Otachi, Ryuhei Uehara. Secure sets anddefensive alliances in graphs: A
faster algorithm and improved bounds.
IEICE Transactions （査読有） E98-D(2015) 486-489.
8. JinheeChun,Takashi
Horiyama,
Takehiro Ito, Natsuda Kaothanthong,Hirotaka Ono, Yota Otachi, Takeshi
Tokuyama, Ryuhei Uehara, Takeaki Uno.
Base-object location problems forbase-monotone regions. TheoreticalComputer Science （査読有） 555 (2014)
71-84.
9. Meng Li, Yota Otachi, Takeshi Tokuyama.
Efficient algorithms for network
localizationusing
coresofunderlyinggraphs.
TheoreticalComputer Science （査読有） 553 (2014)18-26.
10. Takehiro Ito, Shin-ichi Nakano,
Yoshio Okamoto, Yota Otachi, Ryuhei
Uehara, Takeaki Uno, Yushi Uno. A
4.31-approximation for the geometricunique coverage problem on unit disks.
Theoretical Computer Science 544 （査読有） (2014) 14-31.
11. Yota
Otachi,Toshiki
Saitoh,Katsuhisa Yamanaka, Shuji Kijima,

Yoshio Okamoto, Hirotaka Ono, Yushi
Uno, Koichi Yamazaki. Approximating
the path-distance-width for AT-freegraphs and graphs in related classes.
Discrete Applied Mathematics （査読有）168 (2014) 69-77.
12. Kyohei Kozawa, Yota Otachi, Koichi
Yamazaki. Lower bounds for treewidthof product graphs. Discrete Applied
Mathematics （査読有） 162 (2014) 251258.
〔学会発表〕（計 19 件）
1. Eli Fox-Epstein, Duc A. Hoang, Yota
Otachi, Ryuhei Uehara. Sliding token
on bipartite permutation graphs. 26th
International Symposium on AlgorithmsandComputation(ISAAC2015).
December 9-11, 2015, 名古屋マリオット
ア ソ シ ア ホ テ ル （ 愛 知 県 名 古 屋 市 ）．
Lecture Notes in Computer Science 9472
(2015) 237-247.
2. Erik D. Demaine, Matias Korman, Jason
S. Ku, Joseph S.B. Mitchell, Yota
Otachi, André van Renssen, Marcel
Roeloffzen, Ryuhei Uehara, Yushi Uno.
Symmetric assembly puzzles are hard,beyond a few pieces. 18th JapanConferenceon
DiscreteandComputational Geometry and Graphs(JCDCG2 2015). September 14-16, 2015,
京都大学（京都府京都市）．Lecture Notes
in Computer Science, to appear.
3. Takehiro Ito, Yota Otachi, Toshiki
Saitoh, Hisayuki Satoh, Akira Suzuki,Kei
Uchizawa,
RyuheiUehara,Katsuhisa
Yamanaka,XiaoZhou.
Competitive diffusion on weightedgraphs. 14th International Symposiumon Algorithms and Data Structures(WADS 2015). August 5-7, 2015 inVictoria, BC, Canada. Lecture Notes
in Computer Science 9214 (2015) 422433.
4. Katsuhisa Yamanaka, Takashi Horiyama,David Kirkpatrick, Yota Otachi,
Toshiki Saitoh, Ryuhei Uehara, Yushi
Uno. Swapping colored tokens on graphs.
14th International Symposium onAlgorithms and Data Structures (WADS2015). August 5-7, 2015 in Victoria,BC, Canada. Lecture Notes in Computer
Science 9214 (2015) 619-628.
5. Rémy Belmonte, Yota Otachi, PascalSchweitzer.
Inducedminor
freegraphs: Isomorphism and clique-width.
41st International Workshop on GraphTheoreticConcepts
inComputerScience (WG 2015). June 17-19, 2015

in Munich, Germany. Lecture Notes in
Computer Science, to appear.
6. Takehiro Ito, Hirotaka Ono, YotaOtachi. Reconfiguration of cliques ina graph. 12th Annual Conference on
Theory and Applications of Models ofComputation (TAMC 2015). May 18-20,
2015 in Singapore. Lecture Notes in
Computer Science 9076 (2015) 212-223.
7. Akitoshi Kawamura, Sonoko Moriyama,
Yota Otachi, János Pach. A lower boundon opaque sets. 31st European Workshop
on Computational Geometry (EuroCG2015). March 15-18, 2015 in Ljubljana,Slovenia.
8. Erik D. Demaine, Martin L. Demaine,
Eli Fox-Epstein, Duc A. Hoang,Takehiro Ito, Hirotaka Ono, YotaOtachi, Ryuhei Uehara, Takeshi Yamada.
Polynomial-time algorithm for sliding
tokens on trees. 25th International
Symposium
onAlgorithms
andComputation (ISAAC 2014). December
15-17, 2014 in Jeonju, Korea. Lecture
Notes in Computer Science 8889 (2014)
389-400.
9. Tetsuo Asano, Taisuke Izumi, MasashiKiyomi, Matsuo Konagaya, Hirotaka Ono,Yota Otachi, Pascal Schweitzer, JunTarui, Ryuhei Uehara. Depth-firstsearch using O(n) bits.
25thInternational Symposium on Algorithms
andComputation(ISAAC2014).
December 15-17, 2014 in Jeonju, Korea.
Lecture Notes in Computer Science 8889
(2014) 553-564.
10. Yota Otachi, Pascal Schweitzer.
Reductiontechniques
forgraph
isomorphism in the context of widthparameters.
14th
Scandinavian
Symposium and Workshops on Algorithm
Theory (SWAT 2014). July 2-4, 2014 in
Copenhagen, Denmark. Lecture Notes inComputer Science 8503 (2014) 368-379.
11. Pavel Klavík, Jan Kratochvíl, Yota
Otachi, Ignaz Rutter, Toshiki Saitoh,
MariaSaumell,TomásVyskocil.
Extending partial representations ofproper and unit interval graphs. 14th
Scandinavian Symposium and Workshops
on Algorithm Theory (SWAT 2014). July2-4, 2014 in Copenhagen, Denmark.
Lecture Notes in Computer Science 8503
(2014) 253-264.
12. Yota
Otachi.
Graphisomorphism
problem on the H-subgraph-free graphs(Invited talk). The Japanese-SwissWorkshoponCombinatorics
andComputational Geometry. June 4-6,
2014, 東京大学（東京都文京区）．

13. Steven Chaplick, Pavol Hell, Yota
Otachi, Toshiki Saitoh, Ryuhei Uehara.
Intersection dimension of bipartitegraphs. 11th Annual Conference onTheory and Applications of Models ofComputation (TAMC 2014). April 11-13,
2014, in Chennai, India. Lecture Notes
in Computer Science 8402 (2014) 323340.
14. Matsuo Konagaya, Yota Otachi, Ryuhei
Uehara. Polynomial-time algorithms
for subgraph isomorphism in smallgraph classes of perfect graphs. 11thAnnual Conference on Theory andApplications of Models of Computation(TAMC 2014). April 11-13, 2014, inChennai, India. Lecture Notes inComputer Science 8402 (2014) 216-228.
15. Yota Otachi, Pascal Schweitzer.
Isomorphism on subgraph-closed graphclasses: a complexity dichotomy andintermediate graph classes. 24thInternational Symposium on AlgorithmsandComputation(ISAAC2013).
December 16-18, 2013 in Hong Kong,China. Lecture Notes in Computer
Science 8283 (2013) 111-118.
16. Martin Balko, Pavel Klavík, Yota
Otachi. Bounded representations ofinterval and proper interval graphs.
24th International Symposium onAlgorithms and Computation (ISAAC2013). December 16-18, 2013 in Hong
Kong, China. Lecture Notes in Computer
Science 8283 (2013) 535-546.
17. Akitoshi Kawamura, Sonoko Moriyama,Yota Otachi. On shortest barriers.
16th Japan Conference on Discrete andComputational Geometry and Graphs(JCDCG2 2013). September 17-19, 2013,東京理科大学（東京都新宿区）．
18. Masashi Kiyomi, Yoshio Okamoto, Yota
Otachi. On the treewidth of toroidalgrids. 16th Japan Conference on
Discrete and Computational Geometryand Graphs (JCDCG2 2013). September
17-19, 2013, 東京理科大学（東京都新宿区）．
19. Yota Otachi. On low congestion
spanning trees (Invited talk). 8thJapanese-Hungarian
SymposiumonDiscrete
MathematicsandItsApplications. June 4-7, 2013 inVeszprém, Hungary.
〔図書〕（計 0 件）〔産業財産権〕○出願状況（計 0 件）
○取得状況（計 0 件）

〔その他〕
ホームページ等
http://www.jaist.ac.jp/~otachi/

６．研究組織(1)研究代表者
大舘 陽太（OTACHI YOTA）
北陸先端科学技術大学院大学・情報科学研
究科・助教
研究者番号：80610196(2)研究分担者
研究者番号：(3)連携研究者
研究者番号：