著者

大戸 康紀

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2020-AL-180, no.23, pp.1-10, 2020-11-18

---

本論文では,NP 完全問題の一つである k-Clique 問題の最適化バージョンである最大クリーク問題が多項式時間で解けることを証明します.入力グラフ G を辺に有理数の重みを持つ Undirected graph へ拡張します.すべての辺が重み 1 であり,すべての頂点が他の頂点との間に辺を持つ Subgraph をクリークとします.最大クリークの一つを多項式時間で抽出するアルゴリズムを構成する上で必要な証明を行うとともに,そのアルゴリズムを擬似コードの形で与えます.Adjacency matrix の -1 以下の固有値の個数を km(G) とすると,Cauchy Interlacing Theorem により最大クリークの頂点数 k は km(G) +1 以下となります.アルゴリズムでは,km(G) の変化を用いて,頂点を削除したときに最大クリークサイズを変化させない頂点を削除していきます.このアルゴリズムの計算量は O(n8) です.この結果は complexity class NP と P が同じであることを示しています.