線形代数によるサブグラフ同型問題の解法

摘要

本研究ではNP完全問題の一つであるサブグラフ同型問題が多項式時間で解けることを示した．平面グラフ等においては多項式時間で解けるものの，一般的には多項式時間で解けるかは分からなかった．我々は，ライングラフを用いることで誘導サブグラフ同型問題として扱えること，接続行列間に置換行列が存在するとき誘導サブグラフが存在すること，固有値と固有ベクトルを比較することで置換行列の有無を同定できることを証明した．この結果を用いて多項式時間によるサブグラフ同型問題を解くアルゴリズムを構築した．この結果はNP完全問題の一つが多項式時間で解けることを示しており，計算量クラスNPが計算量クラスPと同値となることが示された．