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

混雑度の低い疎なネットワークの設計

Author(s)大舘, 陽太Citation

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

Issue Date

2013‑04‑11

TypeResearch Paper

Text version

publisher

URL

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

RightsDescription

研究種目：研究活動スタート支援, 研究期間
：2011〜2012, 課題番号：23800004, 研究者番号：80610196, 研究分野：グラフアルゴリズム, 科研費の分科・細目：情報学基礎

Japan Advanced Institute of Science and Technology

様式Ｃ－１９
科学研究費助成事業（科学研究費補助金）研究成果報告書
平成２５年４月１１日現在
機関番号：13302
研究種目：研究活動スタート支援
研究期間：2011～2012
課題番号：23800004
研究課題名（和文） 混雑度の低い疎なネットワークの設計
研究課題名（英文） Designing low-congestion sparse networks
研究代表者
大舘 陽太（OTACHI YOTA）
北陸先端科学技術大学院大学・情報科学研究科・助教
研究者番号：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 theproblem and gave some dichotomies for the problem. Our results imply the problem is reallyhard to solve for most of the cases. Thus we designed some heuristic and approximation
algorithm and obtained some partial results.
交付決定額（金額単位：円）2011 年度
2012 年度
年度
年度
年度
総 計

直接経費
1,300,000
1,200,000

間接経費
390,000
360,000

2,500,000

750,000

合計
1,690,000
1,560,000

3,250,000

研究分野：グラフアルゴリズム
科研費の分科・細目：情報学基礎
キーワード：全域木混雑度問題，グラフアルゴリズム，計算複雑性
１．研究開始当初の背景
物理的・論理的の区別なく，ネットワーク構造はグラフで表わされることが多い．本研
究では，ネットワークのリンクが故障した場合に効率的に一部のリンクを復旧する問題を考え，グラフでモデル化する．例えば，道路網がグラフで表されている場合，大雪の後にどの道を雪かきするかという実例がある．
このような問題はグラフアルゴリズムの分野で広く研究されている．最もよく研究されているのは，最も単純な「全てのリンクが故障」，「連結にするために必要最低限のリンクしか復旧しない」という設定である．このとき，復旧するリンクのコスト（長さなど）の和を最小化するだけであれば，古くからよく研究されている最小全域木問題と同じ問題になり，効率的な解法が知られている．また，距離の増加率を最小化するという問題もよく研究されているが，一般には計算理論的に困難であるということが知られている．
別の指標として，「混雑度」と呼ばれるものが知られている．これは，一部のリンクしか使えないために起こる輻輳の度合いの事である．非常に自然な概念であるが，本研究以前にはある種の特別なグラフに対するグラフ理論的な結果しか知られていなかった．
この指標を最小化する問題「全域木混雑度問題」に対して，効率的な解法や計算理論的難しさを判明させるために本研究を開始した．
２．研究の目的
研究の目的は主に以下の三つである．
・全域混雑度問題の計算理論的複雑さ解明
・特殊な場合に対する効率的解法開発
・発見的手法や近似手法の開発(1) 全域混雑度問題の計算理論的複雑さ解
明
本研究で最も重要なのがこの計算理論的複雑さの解明である．計算困難性の理論により，ある種の問題に対して「現実的な計算時間の解法の発見は期待できない」という事が証明できる．研究計画立案時より，この問題はそのような難しい問題である事を予想していた．まずは，これをはっきりさせることにより，その後の研究の方向を定めることが重要である．
(2) 特殊な場合に対する効率的解法開発
計算困難性理論により，多くのグラフ上の問題が「難しい」という事が知られている一方，それらの問題がある種の「性質の良い」
グラフに対して効率的に解けるという事が知られている場合も多い．代表的な結果として，理想グラフ理論 (perfect graph theory)
や グ ラ フ マ イ ナ ー 理 論 (graph minortheory) がある．本研究で扱う問題は一般には難しいことを予想していたので，次の段階としてやるべきことは，難しさをはっきりさせた後で，つまり，困難性を証明した後で，どんな場合ならば易しいのかを研究することである．
(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 件）① YotaOtachi,Toshiki
Saitoh,Katsuhisa Yamanaka, Shuji Kijima,
Yoshio Okamoto, Hirotaka Ono, Yushi
Uno,andKoichiYamazaki,“Approximating
thepath-distance-widthforAT-freegraphs and graphs in relatedclasses”,
Discrete
AppliedMathematics, to appear. 査 読 有 ．
doi:10.1016/j.dam.2012.11.015②

Yota Otachi, The path-distance-widthofhypercubes,
Discussiones
Mathematicae Graph Theory, to appear.
査読有. doi:10.7151/dmgt.1682③

Shuji Kijima, Yota Otachi, Toshiki
Saitoh, and Takeaki Uno, Subgraphisomorphism
ingraphclasses,
Discrete Mathematics 312 (2012)
3164-3173. 査読有.
doi:10.1016/j.disc.2012.07.010④

Yoshio Okamoto, Yota Otachi, andRyuhei Uehara, On bipartite powers ofbigraphs, 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, andShin-ichi
Nakano,Efficientenumeration of ordered trees with kleaves, 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, andErik Jan van Leeuwen, Parameterized
complexity of the spanning treecongestion 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
includingkleaves,
IEICE
Transactions E95-D (2012) 763-768.
査読有.
doi:10.1587/transinf.E95.D.763⑧

Toshiki

Saitoh,Yota

Otachi,Katsuhisa Yamanaka, and Ryuhei Uehara,
Random generation and enumeration ofbipartite
permutationgraphs,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

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.

〔学会発表〕（計 5 件）〔図書〕（計 0 件）①

〔産業財産権〕○出願状況（計 0 件）②

Jinhee Chun, Takashi Horiyama,
Takehiro Ito, Natsuda Kaothanthong,Hirotaka Ono, Yota Otachi, Takeshi
Tokuyama, Ryuhei Uehara, and Takeaki
Uno, Base location problems forbase-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 geometricunique coverage problem on unit disks,
23rd International Symposium on
Algorithms and Computation (ISAAC2012), December 19-21, 2012 in Taipei,Taiwan. Lecture Notes in Computer
Science, 7676 (2012) 372-381.

③

Pavel Klavík, Jan Kratochvíl, YotaOtachi, and Toshiki Saitoh, Extending
partialrepresentationsofsubclasses of chordal graphs, 23rd
International
Symposiumon
Algorithms and Computation (ISAAC2012), December 19-21, 2012 in Taipei,Taiwan. Lecture Notes in Computer
Science, 7676 (2012) 444-454.

④

Yota Otachi, Isomorphism for graphs
ofbounded
connected-path-distance-width, 23rd
International
Symposiumon
Algorithms and Computation (ISAAC○取得状況（計 0 件）
〔その他〕
ホームページ等

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