文献

J-GLOBAL ID：202002233342563767   整理番号：20A2687674

グラフスペクトルによる多項式時間最大クリーク抽出

Polynomial-time Extraction of the Maximum Clique Using Eigenvalue Relation

著者 (1件)： 大戸康紀 (情報処理学会)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2020  号： AL-180  ページ： Vol.2020-AL-180,No.23,1-10 (WEB ONLY)  発行年： 2020年11月18日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： グラフ理論 ,  *計算理論 ,  最大化問題 ,  NP完全問題 ,  有理数 ,  無向グラフ ,  アルゴリズム ,  部分グラフ ,  行列 ,  計算量 ,  固有値 ,  定理証明 ,  完全グラフ ,  クリーク
準シソーラス用語： *グラフスペクトル ,  *多項式時間 ,  *最大クリーク問題 ,  多項式時間アルゴリズム ,  隣接行列

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (7件)：

• Singh, K. K. and Pandey, A. K.: Survey of Algorithms on Maximum Clique Problem, International Advanced Research Journal in Science, Engineering and Technology, Vol. 2, No. 2, pp. 18-20 (2015).
• Zhang, X.-D.: The Laplacian eigenvalues of graphs: a survey, arXiv preprint arXiv:1111.2897 (2011).
• Haemers, W. H.: Interlacing eigenvalues and graphs, Linear Algebra and its applications, Vol. 226, pp. 593-616 (1995).
• Howell, J. A.: An algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. I, mathematics of computation, Vol. 27, No. 124, pp. 887-904 (1973).
• Howell, J. A.: An algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. II, Mathematics of Computation, Vol. 27, No. 124, pp. 905-920 (1973).

タイトルに関連する用語 (4件)： グラフ ,  スペクトル ,  多項式時間 ,  最大クリーク