小特集 3. グラフの性質検査

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 3.

グラフの性質検査

Property Testing on Graphs

𠮷田悠一

𠮷田悠一 国立情報学研究所情報学プリンシプル研究系

Yuichi YOSHIDA, Nonmember (Principles of Informatics Research Division, National Institute of Informatics, Tokyo, 101-8430 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.253-257 2018年3月

©電子情報通信学会2018

abstract

 性質検査とは,入力が所望の性質を満たしているかどうかを,定数時間で近似的に判定する枠組みである.ここで定数時間とは,入力サイズに依存しない計算時間を指す.グラフに対する性質検査は理論的に非常に豊かな分野であり「どのような性質であれば定数時間で検査できるのか」という問いを軸に大きく発展してきた.本稿ではグラフに対する基礎的な検査アルゴリズムと最先端の成果を紹介する.

キーワード:グラフ,定数時間アルゴリズム,性質検査,正則性補題

1.は じ め に

 与えられた入力がある性質を満たすか満たさないかを判定する問題は判定問題と呼ばれる.例えば「数列がソートされているか」「文字列が回文か」「グラフが2部グラフか」などは全て判定問題である.古典的には,判定問題に多項式時間アルゴリズムが存在すれば,その問題は効率的に解けるとみなしてきた.しかし,入力が巨大な場合や,多数の入力を処理する場合には,多項式時間アルゴリズムでさえ遅すぎる場合がある.例えばWebグラフ,すなわちWebサイトを頂点,その間のハイパリンクを枝とみなして作られるグラフでは頂点数や枝数は数十億にもなる.このような巨大なグラフに対して,例えばmath時間のアルゴリズムを実行すると,現在の計算機をもってしても数年の時間を要する.では多項式時間よりも速いアルゴリズムとは一体どんなものであろうか.この問いを突き詰めた枠組みが,本稿で紹介する性質検査である.

1.1 性質検査

 極端なアルゴリズムを考えよう.多項式時間などと言わず,問題を定数時間で解くことはできないだろうか?ここで定数時間とは,どんなに入力サイズが大きくても一定の時間で計算を終えることを指す.定数時間では入力の一部しか見られないので,もちろん正確に問題を解くことはできない.しかし以下の三つの条件を認めることで,様々な判定問題が定数時間で「近似的に」解けることが分かってきている.

 (1) 入力は最初からメモリ等に格納されており,入力に対するランダムアクセスができる.

 (2)「性質を満たす入力」と「満たさない入力」を区別するのではなく「性質を満たす入力」と「満たすには程遠い入力」を区別する.どちらでもない入力にはどんな動作をしても構わない.後者の区別を検査と呼ぶことにする.

 (3) 乱択アルゴリズムを用いる.すなわちアルゴリズムは乱数を用いて動作し,高い確率で成功すればよい.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。