問題タブ [clique-problem]

実際のプログラマーとしての私の明らかな数学的欠点をお詫びして、この質問をします。高校の代数でいい成績を取って、それ以上の科目で失敗してから 40 年以上が経ちました。「NP 完全」と「NP 困難」の問題の概念は把握するのが困難でしたが、試してみました。このクラスの問題の元のガイドと思われるもの、Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey と David S. Johnson を購入して研究しました。

https://goodreads.com/book/show/284369.Computers_and_Intractability/

そうかもしれません。質問自体が十分に明確であることが望まれます。すべての一意の完全なサブグラフ (すべての個別のノード (頂点) が (一意のエッジを介して) 相互に接続されている) を抽出するという特定の問題に対して、これまでに公開されている最高のブルート フォース アルゴリズム (効率的なブランチ プルーニングを使用) は何ですか?ランダム無向グラフ？つまり、アルゴリズムは、最大の一意の完全なサブグラフを最初に抽出できる必要がありますが、その数が多くても、その順序で、(定義上、私が思うに) に含まれていないすべての小さな一意の完全なサブグラフを抽出できます。これにより、一意ではない (暗黙の) 結果が重複して生成されるのを回避できます。

痛い、こんなにはっきりとした英語で綴ろうとすると頭が痛くなる。それでもなお、この説明が十分に単純であることが望まれます。64GB/128GB の DRAM を備えた Ryzen 5 3600 ボックスなどの合理的な計算リソースをこの機能に提供する標準の C/C++/(または Python) ライブラリは、特に 1,024 ノードでの完全な分析が1日か2日ですが、たくさんの感謝を込めて、できる限りのことをします。

そして、ウェブ上のどこかに、数学を知らない人でも理解できる英語でこのトピックを扱った FAQ やエッセイがあれば、それはさらに良いことです!

編集:次の論文の文言は確かに私の頭を少し超えていますが、そこにいる計算数学者にとって、それが実際にコアの問題自体に実質的に対処していることを確認できますか? もしそうなら、私はこの「ブロン-ケルボッシュ」アルゴリズムを理解するための英雄的な努力を始めることができます. -_-

「すべての最大クリークを生成するための最悪の時間計算量と計算実験」富田悦司、田中明、高橋治久

(〒182-8585 東京都調布市調布ヶ丘 1-5-1 電気通信大学情報通信工学科) (〒 470-0334 愛知県豊田市花本町今江 1-21 トヨタテクノサービス株式会社) 、 日本）

https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf