Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/ Title 混雑度の低い疎なネットワークの設計 Author(s) 大舘, 陽太 Citation 科学研究費助成事業研究成果報告書: 1-4 Issue Date 2013-04-11Type Research Paper Text version publisher
URL http://hdl.handle.net/10119/11374 Rights Description 研究種目：研究活動スタート支援, 研究期間 ：2011∼2012, 課題番号：23800004, 研究者番号 ：80610196, 研究分野：グラフアルゴリズム, 科研費 の分科・細目：情報学基礎
様式Ｃ－１９
科学研究費助成事業（科学研究費補助金）研究成果報告書
平成２５年４月１１日現在 研究成果の概要（和文）： 混雑度の低い疎なネットワークの設計問題のうち，特に全域木混 雑度問題と呼ばれるグラフに対する最適化問題を研究し，計算理論的に難しい場合と易し い場合に対してある種の線引きを行った．また，1990 年代から注目されている「固定パラ メータ計算量」という計算理論的概念も研究し，いくつかの基準に対して困難な場合と容 易な場合の 2 分法を与えた．研究結果から，この問題は多くの場合で非常に難しいという ことが分かったので，発見的手法や近似手法などの研究にも取り組み，部分的な成果を得 た．研究成果の概要（英文）： We studied the problem of designing low-congestion sparse networks. Especially, we studied the computational complexity of an optimization problem on graphs called “the spanning tree congestion problem.” We presented sharp contrasts between hard cases and easy cases. We also investigated the parameterized complexity of the problem and gave some dichotomies for the problem. Our results imply the problem is really hard to solve for most of the cases. Thus we designed some heuristic and approximation algorithm and obtained some partial results.
交付決定額 （金額単位：円） 直接経費 間接経費 合 計 2011 年度 1,300,000 390,000 1,690,000 2012 年度 1,200,000 360,000 1,560,000 年度 年度 年度 総 計 2,500,000 750,000 3,250,000 研究分野：グラフアルゴリズム 科研費の分科・細目：情報学基礎 キーワード：全域木混雑度問題，グラフアルゴリズム，計算複雑性 １．研究開始当初の背景 物理的・論理的の区別なく，ネットワーク 構造はグラフで表わされることが多い．本研 究では，ネットワークのリンクが故障した場 合に効率的に一部のリンクを復旧する問題 を考え，グラフでモデル化する．例えば，道 路網がグラフで表されている場合，大雪の後 にどの道を雪かきするかという実例がある． このような問題はグラフアルゴリズムの分 野で広く研究されている．最もよく研究され ているのは，最も単純な「全てのリンクが故 障」，「連結にするために必要最低限のリンク 機関番号：13302 研究種目：研究活動スタート支援 研究期間：2011～2012 課題番号：23800004 研究課題名（和文） 混雑度の低い疎なネットワークの設計 研究課題名（英文） Designing low-congestion sparse networks
研究代表者
大舘 陽太（OTACHI YOTA）
北陸先端科学技術大学院大学・情報科学研究科・助教 研究者番号：80610196
しか復旧しない」という設定である．このと き，復旧するリンクのコスト（長さなど）の 和を最小化するだけであれば，古くからよく 研究されている最小全域木問題と同じ問題 になり，効率的な解法が知られている．また， 距離の増加率を最小化するという問題もよ く研究されているが，一般には計算理論的に 困難であるということが知られている． 別の指標として，「混雑度」と呼ばれるも のが知られている．これは，一部のリンクし か使えないために起こる輻輳の度合いの事 である．非常に自然な概念であるが，本研究 以前にはある種の特別なグラフに対するグ ラフ理論的な結果しか知られていなかった． この指標を最小化する問題「全域木混雑度問 題」に対して，効率的な解法や計算理論的難 しさを判明させるために本研究を開始した． ２．研究の目的 研究の目的は主に以下の三つである． ・全域混雑度問題の計算理論的複雑さ解明 ・特殊な場合に対する効率的解法開発 ・発見的手法や近似手法の開発 (1) 全域混雑度問題の計算理論的複雑さ解 明 本研究で最も重要なのがこの計算理論的 複雑さの解明である．計算困難性の理論によ り，ある種の問題に対して「現実的な計算時 間の解法の発見は期待できない」という事が 証明できる．研究計画立案時より，この問題 はそのような難しい問題である事を予想し ていた．まずは，これをはっきりさせること により，その後の研究の方向を定めることが 重要である． (2) 特殊な場合に対する効率的解法開発 計算困難性理論により，多くのグラフ上の 問題が「難しい」という事が知られている一 方，それらの問題がある種の「性質の良い」 グラフに対して効率的に解けるという事が 知られている場合も多い．代表的な結果とし て，理想グラフ理論 (perfect graph theory) や グ ラ フ マ イ ナ ー 理 論 (graph minor theory) がある．本研究で扱う問題は一般に は難しいことを予想していたので，次の段階 としてやるべきことは，難しさをはっきりさ せた後で，つまり，困難性を証明した後で， どんな場合ならば易しいのかを研究するこ とである． (3) 発見的手法や近似手法の開発 計算理論的には困難な問題でも，発見的な 手法で多くの問題例が解ける場合がある．最 も有名な例は充足可能性判定 (SAT) 問題で ある．多くの SAT ソルバと呼ばれるソフトウ ェアが開発されており，非常に大きな問題例 でもたいていの場合は現実的な時間で解け る事が報告されている．全域混雑度問題に対 しても，最小全域木問題などよく研究されて いる関連問題に対する手法などを組み合わ せることで，「性能の保証はないが，たいて いうまくいく」アルゴリズムの開発を目標と する．また，そこから得られた知見を用いて， 精度保証のある近似アルゴリズムの開発も 目指す． ３．研究の方法 ここでも以下の三つに分けて説明する． ・全域混雑度問題の計算理論的複雑さ解明 ・特殊な場合に対する効率的解法開発 ・発見的手法や近似手法の開発 (1) 全域混雑度問題の計算理論的複雑さ解 明 まず，一般の場合に対して計算理論的に難 しいことを示す．より具体的には NP 困難性 を示す．これに成功した場合，より限定され たグラフクラス（交差グラフや平面的グラ フ）に対しても困難性が示せるか確かめる． 古典的な意味での計算複雑性が判明した 後には，固定パラメータ計算量理論の意味で の困難性の証明に取り組む．具体的には，与 えられたグラフの全域混雑度がある定数ｋ 以下であるか判定する問題の難しさを調べ る．この問題が難しいと分かった場合，その 難しさはグラフクラスをどれだけ限定した 場合に示せるかを更に調べる． (2) 特殊な場合に対する効率的解法開発 難しい場合が判明したら，グラフクラスの 制限をどれだけ強くすれば簡単になるかを 調べる．困難な場合と易しい場合のギャップ がなるべく小さくできるように限定条件を 設定することを目指す． (3) 発見的手法や近似手法の開発 何らかの基準を最適化する全域木を求め る問題はよく研究されており，様々な厳密・ 発見的・近似手法が開発されている．それら のうちより，全域木混雑度問題と相性が良さ そうなものをいくつか選び，計算機実験を通 して採用候補を決定する．近似手法に関して は，問題同士の関係をもちいて近似率を理論 的に証明することも試みる． ４．研究成果 (1) 全域混雑度問題の計算理論的複雑さ解 明 一般の場合は計算理論的に難しいことを 予想していたが，それだけではなく，非常に 制限された場合でも難しいということを確 かめた．古典的計算複雑性理論の観点からは，
グラフが完全グラフや完全 2 部グラフに近い 単純な形をしていても難しいことを示した． また，平面に辺の交差なく描画できる平面的 グラフに限定しても難しいということを示 した． 次に，固定パラメータ計算量について研究 し，多くの困難性の結果を得た．まず初めに， 与えられたグラフがある定数 k 以下の全域混 雑度を持つかという問題が，k が 8 以上のと き，一般の問題と同じ難しさを持つことを示 した．（一般の場合は k は入力変数である．） さらに，この難しさが非常に限定されたグラ フでも成り立つことを示した．その限定とは， ・ 1 頂点を除く全頂点が定数次数を持つ， ・ 6 頂点以上の完全グラフをマイナとして 持たない， の 2 条件である．これらを同時に満たすグラ フでも難しいことから，後述する易しい場合 とのある種の 2 分を与えていることとなる． (2) 特殊な場合に対する効率的解法開発 あるグラフクラスに対して，全域混雑度問 題が易しいかという問に対しては多くの結 果は得られなかった．示すことができたのは， 外 平 面 的 グ ラ フ お よ び 自 明 理 想 グ ラ フ （trivially perfect graph）に対しては， 全域木混雑度が高速に計算できるというこ とである． 一方，固定パラメータ計算量の観点からは 多くの易しい場合を発見することができた． 以下のそれぞれ場合に対しての容易性を示 した． ・ k が 3 以下の場合, ・ グラフの木幅が定数の場合， ・ グラフの最大次数が定数の場合， ・ Apex グラフと呼ばれる種類のグラフをマ イナとして含まない場合 これらは，前述の難しい場合と合わせてある 種の 2 分を与えていることになる．例えば， 全ての頂点の次数が小さければ易しいが，1 頂点でも次数が大きい頂点があると難しく なる． (3) 発見的手法や近似手法の開発 発見的手法に関しては，幅優先探索全域 木と既存のメタヒューリスティクスアルゴ リズムの組合せによって比較的良い解を得 ることができるという，実験的な考察を得た． 近似手法に関しては，平面的グラフに対する 対数倍近似アルゴリズムおよび一般の場合 に対する線形倍近似アルゴリズムの開発を 行った． ５．主な発表論文等 （研究代表者、研究分担者及び連携研究者に は下線） 〔雑誌論文〕（計 9 件）
① Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, and Koichi Yamazaki, “Approximating the path-distance-width for AT-free graphs and graphs in related classes”, Discrete Applied Mathematics, to appear. 査 読 有 ． doi:10.1016/j.dam.2012.11.015
② Yota Otachi, The path-distance-width of hypercubes, Discussiones Mathematicae Graph Theory, to appear. 査読有. doi:10.7151/dmgt.1682
③ Shuji Kijima, Yota Otachi, Toshiki Saitoh, and Takeaki Uno, Subgraph isomorphism in graph classes, Discrete Mathematics 312 (2012) 3164-3173. 査読有.
doi:10.1016/j.disc.2012.07.010
④ Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara, On bipartite powers of bigraphs, Discrete Mathematics & Theoretical Computer Science 14:2 (2012) 11-20. 査読有.
http://www.dmtcs.org/dmtcs-ojs/inde x.php/dmtcs/article/view/2132
⑤ Katsuhisa Yamanaka, Yota Otachi, and Shin-ichi Nakano, Efficient enumeration of ordered trees with k leaves, Theoretical Computer Science 442 (2012) 22-27. 査読有.
doi:10.1016/j.tcs.2011.01.017
⑥ Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, and Erik Jan van Leeuwen, Parameterized complexity of the spanning tree congestion problem, Algorithmica 64 (2012) 85-111. 査読有.
doi:10.1007/s00453-011-9565-7
⑦ Masanobu Ishikawa, Katsuhisa Yamanaka, Yota Otachi, and Shin-ichi Nakano, Enumerating all rooted trees including k leaves, IEICE Transactions E95-D (2012) 763-768. 査読有.
doi:10.1587/transinf.E95.D.763
Katsuhisa Yamanaka, and Ryuhei Uehara, Random generation and enumeration of bipartite permutation graphs, Journal of Discrete Algorithms 10 (2012) 84-97. 査読有.
doi:10.1016/j.jda.2011.11.001
⑨ Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno, Hardness results and an exact exponential algorithm for the spanning tree congestion problem, Journal of Graph Algorithms and Applications 15 (2011) 727-751. 査読有.
doi:10.7155/jgaa.00246
〔学会発表〕（計 5 件）
① Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, and Takeaki Uno, Base location problems for base-monotone regions, 7th International Workshop on Algorithms and Computation (WALCOM 2013), February 14-16, 2013 in Kharagpur, India. Lecture Notes in Computer Science, 7748 (2013) 53-64.
② Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, A 4.31-approximation for the geometric unique coverage problem on unit disks, 23rd International Symposium on Algorithms and Computation (ISAAC 2012), December 19-21, 2012 in Taipei, Taiwan. Lecture Notes in Computer Science, 7676 (2012) 372-381.
③ Pavel Klavík, Jan Kratochvíl, Yota Otachi, and Toshiki Saitoh, Extending partial representations of subclasses of chordal graphs, 23rd International Symposium on Algorithms and Computation (ISAAC 2012), December 19-21, 2012 in Taipei, Taiwan. Lecture Notes in Computer Science, 7676 (2012) 444-454.
④ Yota Otachi, Isomorphism for graphs of bounded connected-path-distance-width, 23rd International Symposium on Algorithms and Computation (ISAAC
2012), December 19-21, 2012 in Taipei, Taiwan. Lecture Notes in Computer Science, 7676 (2012) 455-464.
⑤ Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares, 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), July 4-6, 2012, in Helsinki, Finland. Lecture Notes in Computer Science, 7357 (2012) 24-35. 〔図書〕（計 0 件） 〔産業財産権〕 ○出願状況（計 0 件） ○取得状況（計 0 件） 〔その他〕 ホームページ等 ６．研究組織 (1)研究代表者 大舘 陽太（OTACHI YOTA） 北陸先端科学技術大学院大学・情報科学研 究科・助教 研究者番号：80610196 (2)研究分担者 (3)連携研究者
