|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
|
|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
グラフアルゴリズムの最先端
小特集 3.
グラフの性質検査
Property Testing on Graphs
abstract
性質検査とは，入力が所望の性質を満たしているかどうかを，定数時間で近似的に判定する枠組みである．ここで定数時間とは，入力サイズに依存しない計算時間を指す．グラフに対する性質検査は理論的に非常に豊かな分野であり「どのような性質であれば定数時間で検査できるのか」という問いを軸に大きく発展してきた．本稿ではグラフに対する基礎的な検査アルゴリズムと最先端の成果を紹介する．
キーワード：グラフ，定数時間アルゴリズム，性質検査，正則性補題
与えられた入力がある性質を満たすか満たさないかを判定する問題は判定問題と呼ばれる．例えば「数列がソートされているか」「文字列が回文か」「グラフが2部グラフか」などは全て判定問題である．古典的には，判定問題に多項式時間アルゴリズムが存在すれば，その問題は効率的に解けるとみなしてきた．しかし，入力が巨大な場合や，多数の入力を処理する場合には，多項式時間アルゴリズムでさえ遅すぎる場合がある．例えばWebグラフ，すなわちWebサイトを頂点，その間のハイパリンクを枝とみなして作られるグラフでは頂点数や枝数は数十億にもなる．このような巨大なグラフに対して，例えば
時間のアルゴリズムを実行すると，現在の計算機をもってしても数年の時間を要する．では多項式時間よりも速いアルゴリズムとは一体どんなものであろうか．この問いを突き詰めた枠組みが，本稿で紹介する性質検査である．
極端なアルゴリズムを考えよう．多項式時間などと言わず，問題を定数時間で解くことはできないだろうか？ここで定数時間とは，どんなに入力サイズが大きくても一定の時間で計算を終えることを指す．定数時間では入力の一部しか見られないので，もちろん正確に問題を解くことはできない．しかし以下の三つの条件を認めることで，様々な判定問題が定数時間で「近似的に」解けることが分かってきている．
（１） 入力は最初からメモリ等に格納されており，入力に対するランダムアクセスができる．
（２）「性質を満たす入力」と「満たさない入力」を区別するのではなく「性質を満たす入力」と「満たすには程遠い入力」を区別する．どちらでもない入力にはどんな動作をしても構わない．後者の区別を検査と呼ぶことにする．
（３） 乱択アルゴリズムを用いる．すなわちアルゴリズムは乱数を用いて動作し，高い確率で成功すればよい．
続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。
電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。
電子情報通信学会 - IEICE会誌アプリをダウンロード
