（邦訳：次数を制限したグラフと制約充足問題に対する定数時間アルゴリズムの研究）
| 𠮷田 悠一 国立情報学研究所 ／（株）プリファードインフラストラクチャー |
［背景］Webやゲノムなどの巨大な入力
［問題］入力長に依存しない"定数"時間で問題を解くアルゴリスム
［貢献］疎なグラフと制約充足問題に対する定数時間アルゴリズムの提案と他の理論との関連付け
Webやゲノムなどの巨大な入力が一般的になった昨今では，入力すべてを読み込むだけでも長い時間が必要である．そこで定数時間アルゴリズムという概念が提唱されている．これはその名の通り，入力をすべては読まない，それどころか常に入力長に依存しない“定数”時間で問題を解くアルゴリズムのことである．もちろん，それでは普通の意味で問題を解くことはできないので誤差を許す．主に以下の2種類の定数時間アルゴリズムが考えられている．ある性質に対するε検査アルゴリズムとは，入力がその性質を満たすか，その性質を満たすには入力をε割合書き換えないといけないかε-farを高い確率で正しく出力するもののことを言う（図-1）．
図-1 性質検査の概念図
ある最適化問題に対する(α, β)近似アルゴリズムとは，最適解をx*としたときに，高い確率でα x* - β ≤ x ≤ x*なるxを出力するもののことを言う．典型的にはβ = ε nとする．このように入力長のε倍の誤差を許容することで，さまざまな問題が定数時間で解けるようになることが知られている．
本論文では次数を制限したグラフの問題と制約充足問題（CSP）を扱った．CSPの入力は変数の集合とそれらに対する制約の集合からなり，すべての制約を満たすように変数に値を割り当てられるか充足可能を判定することが目的である．CSPはSAT，線形連立方程式，彩色問題などを含む重要な問題である．CSPを最適化問題に拡張したのがMaxCSPであり，できるだけたくさんの制約を満たす割り当てを求めるのが目的である．次数が制限されているとは，ある頂点（変数）を含む枝（制約）の個数が，ある定数で抑えられていることを言う．この制限は実用的にも頻繁に現れ，理論的にも未解決問題が多く重要である．本論文の目標は，この制限下で定数時間で解ける問題を特徴付けることである．
本論文の結果は以下の4つである．
（1） 最大マッチングに代表される多くの問題に対して，既存の結果と比べて1 / εに関して指数的に高速な定数時間近似アルゴリズムを与えた．
（2） (k, 
)完全性と呼ばれる性質が定数時間で検査できることを示した．これは過去の多くの結果を含んでおり，マトロイドや枝連結度増大など他の理論との関連を明らかにした．
)完全性と呼ばれる性質が定数時間で検査できることを示した．これは過去の多くの結果を含んでおり，マトロイドや枝連結度増大など他の理論との関連を明らかにした．（3） すべてのMaxCSPに対して最良の定数時間近似アルゴリズムを与えた．
（4） CSPの充足可能性が検査可能であるための必要十分条件を与えた．
（3）と（4）の結果から，CSPに対する定数時間アルゴリズムの研究をほぼ終わらせることに成功したと言える．この研究は，結果自体もさることながら，確率的検査可能証明や普遍代数と言った，それぞれの分野でしか応用されていなかった理論を別分野で利用したことが意義深い．グラフでは，定数時間で解ける問題を特徴付けることができておらず，これが将来の課題である．
（2012年7月22日受付）