効率的なアルゴリズム基盤技術の開発と実装

● 研究テーマ

• ❖ 幾何的特徴を持つグラフに対する効率的なアルゴリズムの開発
• ❖ 効率的なグラフ列挙アルゴリズムの開発と実装
• ❖ 大規模データに対応する省領域アルゴリズムの開発

● 分野

情報学基礎、知能情報学

● キーワード

グラフアルゴリズム、列挙アルゴリズム、データ構造、計算複雑さ（NP-困難性など）

● 実施中の研究概要

近年、センサーの高性能化やスマートフォンの普及により、センサーネットワークやソーシャルネットワークなどのビッグデータが存在し、ビッグデータから有用な特徴を抽出するための効率的なアルゴリズムが求められています。例えば、ソーシャルネットワークから一定以上の影響力を持つコミュニティを抽出し、コマーシャルを流すことで、より効果的な広告宣伝ができる可能性があります。こうしたコミュニティを求めることをクリーク問題と呼ばれグラフとして表現できますが、グラフ上で最適な組み合わせを見つけることは計算理論的に非常に難しいといわれています。そこでこうした計算量理論上、困難な問題に対して、様々なアプローチにもとづいて効率的に解くことのできるアルゴリズムの開発や計算複雑性に関する研究を行っています。
アプローチの一つに，入力のグラフが幾何的な構造を持つと制限することがあります。そうした幾何的な構造を持つグラフの一つに区間グラフがあります。区間グラフは数直線上の区間を頂点、区間同士の重なりを頂点間の辺で表すことができるグラフで、区間を DNA 塩基配列や時間とおくことでバイオインフォマティクスにおける DNA の効率的な復元やスケジューリングにおける割当問題を解くことができます。例えば、作業工程表が与えられたとき、その区間グラフ上の彩色問題を解くことによって、何人の作業員が必要かといった問題を効率的に解くことができます。本研究では、区間グラフのような幾何的な構造を持つグラフに対する効率的なアルゴリズムの開発を行っています。
また、グラフからクリークのような構造を１つ抽出するのではなく、すべて抽出するという列挙アルゴリズムの開発を行っています。グラフ上のクリークなどの構造は膨大な数が存在しますが、 ZDD（ゼロサプレス型二分決定グラフ）と呼ばれるデータ構造を用いることにより、高圧縮にすべてのクリークを表現でき、さらには解の絞り込みやサンプリング、数え上げなどを行うことができます。本アルゴリズムを適用して、パズルのソルバー（パズルを解くアルゴリズム）を開発したり、避難所割り当て問題などへ応用しています。

● 今後進めたい研究

多くの実データにはノイズが含まれており、与えられたデータそのままからは適切ではないグラフが生成されてしまいます。例えば、DNA シーケンサーによって重なりの強い部分配列間に辺を引いても，ノイズや読み込みエラーが多く、区間グラフがされることはありません。そこで、グラフを編集し、区間グラフを生成するというアルゴリズムが必要になります。そこで、ZDD による列挙アルゴリズム技法を用いて、区間グラフの生成アルゴリズムについて、理論的かつ応用的な側面で研究を進めていきたいと考えています。

● 過去の業績

[論文] Kazuaki Yamazaki, Toshiki Saitoh, Masashi Kiyomi, and Ryuhei Uehara: “Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs,” Theoretical Computer Science, vol. 806, pp. 310-322, February, 2020.
[論文] Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki and Ryo Yoshinaka: “Colorful Frontier-based Search: Implicit Enumeration of Chordal and Interval Subgraphs,” Special Event on Analysis of Experimental Algorithms, Lecture Notes in Computer Science, vol. 11544, pp. 125-141, June 24-29, 2019

● 関連リンク先

• ❖ 研究室ホームページ
• http://algorithm.ces.kyutech.ac.jp/wp/

❖ 詳しい研究者情報
https://hyokadb02.jimu.kyutech.ac.jp/html/100000980_ja.html