集團問題
在計算機科學中，集團問題是在圖中查找集團（頂點的子集，都稱為完整子圖）的計算問題。它具有幾種不同的配方，具體取決於哪些集團以及有關集團的哪些信息。集團問題的常見公式包括查找最大集團（一個可能數量最多的頂點的集團），在加權圖中找到最大的重量集團，列出所有最大集團（無法放大的集團），並解決決策問題測試圖是否包含大於給定尺寸的集團。
集團問題出現在以下實際環境中。考慮一個社交網絡，圖形的頂點代表人，圖表的邊緣代表相互熟人。然後，一個集團代表了彼此認識的人的一部分，並且可以使用尋找集團的算法來發現這些共同的朋友。該集團問題在社交網絡中的應用還具有許多在生物信息學和計算化學中的應用。
集團問題的大多數版本都很難。集團決策問題是NP兼職（ KARP的21個NP完整問題之一）。找到最大集團的問題既是固定參數棘手的，又難以近似。而且，列出所有最大集團可能需要指數時間，因為存在具有指數的最大集團的圖表。因此，有關集團問題的許多理論都致力於確定接受更有效算法的特殊類型的圖形，或在各種計算模型中確定一般問題的計算難度。
為了找到最大的集團，可以系統地檢查所有子集，但是這種蠻力搜索太耗時了，無法實用，對於包含數十個頂點的網絡。儘管沒有以此問題為名的多項式時間算法，但比蠻力搜索更有效的算法。例如， Bron – Kerbosch算法可用於在最差的最佳時間內列出所有最大集團，並且也可以在每個集團的多項式時間中列出它們。
歷史和應用
數學中完整子圖的研究早於“集團”術語。例如，完整的子圖在Ramsey理論的圖理論重新印度的數學文獻中早期出現，Erdős＆Szekeres（1935） 。但是，“集團”一詞和算法列出集團的問題都來自社會科學，其中完整的子圖被用來建模社交集團，彼此認識的人群。 Luce＆Perry（1949）使用圖來建模社交網絡，並將社會科學術語改編為圖理論。他們是第一個將完整子圖稱為“集團”的人。解決集團問題的第一種算法是Harary＆Ross（1957）的算法，他們是受到社會學應用激勵的。社會科學研究人員還定義了社交網絡中其他各種類型的集團和最大集團，網絡中的人或參與者的“凝聚力亞組”，所有這些人都分享了幾種不同類型的連接關係之一。這些集團的廣義概念中的許多也可以通過構造一個無方向的圖來找到，該圖形的邊緣代表社交網絡中的參與者對，然後將算法應用於該圖表。
自Harary和Ross的工作以來，許多其他人都為集團問題的各種版本設計了算法。在1970年代，研究人員從最壞情況分析的角度開始研究這些算法。參見，例如， Tarjan＆Trojanowski（1977） ，這是關於最大集團問題最嚴重的複雜性的早期工作。同樣在1970年代，從Cook（1971）和Karp（1972）的工作開始，研究人員開始使用NP完整性理論和相關的頑固性結果，以提供數學上的解釋，以解決該集團問題的可感知難度。在1990年代，從Feige等人開始的一系列突破性論文。 （1991）表明（假設P≠np ）甚至不可能準確有效地近似問題。
集團找到算法已用於化學中，以找到與靶結構和分子對接建模和化學反應的結合位點相匹配的化學物質。它們也可用於在不同分子中找到相似的結構。在這些應用中，一個形成一個圖，其中每個頂點代表一個匹配的原子，一個來自兩個分子中的每個原子。如果它們代表的匹配彼此兼容，則通過邊緣連接兩個頂點。兼容可能意味著，例如，兩個分子內的原子之間的距離大致相等，而在某些給定的公差之內。該圖中的一個集團代表一組匹配的原子對，其中所有匹配都彼此兼容。該方法的一種特殊情況是使用圖形的模塊化產品來減少發現兩個圖的最大常見誘導子圖的問題，以使其在其產品中找到最大集團的問題。
在自動測試模式生成中，查找集團可以幫助綁定測試集的大小。在生物信息學中，已經使用了共生算法來推斷進化樹，預測蛋白質結構並找到蛋白質的緊密相互作用的簇。在依賴圖中列出集團是對某些隨機過程分析的重要步驟。在數學中， Lagarias＆Shor（1992）拒絕了Keller對超管面對面瓷磚的猜想，後者在相關圖上使用了一個集團找到算法來找到反例。
定義
一組有限的頂點和一組無序的頂點，稱為邊緣，形成了一個無方向的圖。按照慣例，在算法分析中，圖中的頂點的數量用n表示，邊緣的數量用m表示。圖G中的集團是G的完整子圖。也就是說，它是頂點的子集k ，因此k中的每個兩個頂點是g中一個邊緣的兩個端點。最大集團是一個不再添加頂點的集團。對於不屬於最大集團的每個頂點V ，必須有另一個頂點w在c中，而對V則不可變化，從而阻止V添加到該集團中。最大集團是一個包含最大數量的頂點的集團。集團數ω （ g ）是G的最大集團中的頂點數。
已經研究了幾個密切相關的集團找到問題。
- 在最大集團問題中，輸入是一個無向圖，並且輸出是圖中的最大集合。如果有多個最大集團，則可以任意選擇其中一個。
- 在加權最大集團問題中，輸入是一個無向圖，其頂點（或頻率較低的邊緣）上的權重），輸出是一個最大總權重的集團。最大集團問題是所有權重相等的特殊情況。除了優化權重總和的問題外，還研究了其他更複雜的雙晶格優化問題。
- 在最大集團清單問題中，輸入是一個無方向的圖，並且輸出是其所有最大集團的列表。最大集團問題可以用作最大集團列表問題的子例程和算法來解決，因為必須將最大集團包含在所有最大集團之間。
- 在k -Clique問題中，輸入是一個無向圖和數字k 。該輸出是一個具有K頂點的集團，如果存在，則是一個特殊值，表明沒有k -Clique。在此問題的某些變化中，輸出應列出大小k的所有集團。
- 在集團決策問題中，輸入是一個無方向的圖和數字k ，並且輸出是一個布爾值：如果圖形包含k -clique，則為true，否則為false。
這些問題中的前四個在實際應用中都很重要。集團決策問題並不實際重要。它是通過這種方式製定的，以便將NP完整性理論應用於集團找到問題。
集團問題和獨立集問題是互補的： G中的集團是G的補充圖中的獨立集，反之亦然。因此，許多計算結果可能同樣適用於問題，並且一些研究論文並未清楚地區分這兩個問題。但是，當將兩個問題應用於受限的圖表家族時，這兩個問題具有不同的特性。例如，在平面圖的多項式時間內可以解決集團問題，而獨立的集合問題仍然是平面圖上的np-hard。
演算法
找到一個最大集團
最大集團有時稱為包容性最大，是一個不包含在較大集團中的集團。因此，每個集團都包含在最大集團中。最大集團可能很小。圖可能包含一個具有許多頂點的非最大插件和最大尺寸2的單獨集團。雖然最大（即最大）集團必然是最大的，但匡威不保持。在某些類型的圖形中，每個最大集團都是最大的。這些是覆蓋良好的圖的補充，其中每個最大獨立集都是最大的。但是，其他圖具有最大庫，不是最大的。
通過直接的貪婪算法可以找到一個最大集團。從任意集團（例如，任何一個頂點甚至空心集）開始，一次通過循環瀏覽圖的剩餘頂點，從而使當前集團一個頂點增加。對於此循環檢查的每個頂點V ，如果該集團與已經存在的每個頂點相鄰，則將V添加到該集團，否則將V丟棄。該算法以線性時間運行。由於很容易找到最大的集團及其潛在的小尺寸，因此人們對找到最大或以其他方式的算法問題更加困難。但是，一些並行算法中的一些研究研究了找到最大集團的問題。特別地，發現在多項式時間函數的類別中，發現找到詞素上的最大集合（由上面的算法發現的問題）是完整的。該結果意味著在平行複雜性類NC中不可能解決該問題。
固定尺寸的集團
一個人可以使用蠻力算法來測試圖G圖是否包含k vertex clique，並找到所包含的任何此類集團。該算法使用K頂點檢查每個子圖，並檢查它是否形成一個集團。如使用大o符號所示，它需要時間O （ N K K 2 ） 。這是因為需要檢查O （ N K ）子圖，每個子圖都具有O （ K 2 ）邊緣，需要檢查其在G中的存在。因此，每當k為固定常數時，就可以在多項式時間內解決問題。但是，當K沒有固定值，而是作為問題輸入的一部分而變化時，時間是指數級的。
集團找到問題的最簡單的非平凡情況是在圖中找到三角形，或等效地確定圖形是否不含三角形。在具有M邊緣的圖G中，最多可能存在θ（ m 3/2 ）三角形（使用大theta表示法表示該結合是緊密的）。當G本身是一個集團時，最壞的情況是發生。因此，列出所有三角形的算法必須在最壞情況下至少需要ω（ m 3/2 ）時間（使用大歐米茄符號），並且已知算法匹配這段時間。例如， Chiba＆Nishizeki（1985）描述了一種算法，該算法將頂點從最高程度到最低，然後在排序列表中通過每個頂點V進行迭代，尋找包括V的三角形，不包括V ，並且不包含任何以前的頂點列表。為此，算法標記了V的所有鄰居，搜索所有EDGE的搜索到V的鄰居，為每個邊緣輸出一個具有兩個標記端點的邊緣，然後從圖形中刪除標記和刪除V。正如作者所示，該算法的時間與圖形（表示A （ g ） ）乘以邊緣數量（即O （ m a （ g ））的棲息地成正比。由於營養性最多是O （ M 1/2 ） ，因此該算法在時間O （ M 3/2 ）中運行。更一般而言，所有K vertex集團都可以通過類似的算法列出，該算法將時間成比例的邊緣數量乘以支子型的邊緣數（ k -2） 。對於恆定樹木的圖形，例如平面圖（或在任何非平凡的次要閉合圖家族的一般圖中），該算法需要O （ m ）時間，這是最佳的，因為它在輸入的大小上是線性的。
如果只需要一個三角形，或者保證該圖是不含三角形的，則可以更快的算法。正如Itai＆Rodeh（1978）所觀察到的那樣，該圖在且僅當其鄰接矩陣和鄰接矩陣的平方中包含一個三角形時，在同一單元格中包含非零條目。因此，可以應用快速矩陣乘法技術在時間O中找到三角形（ n 2.376 ） 。 Alon，Yuster＆Zwick（1994）使用快速矩陣乘法來改進O （ M 3/2 ）算法，以找到三角形到O （ M 1.41 ） 。這些基於快速矩陣乘法的算法也已擴展到為k較大值尋找k個cliques的問題。
列出所有最大集團
由於Moon＆Moser（1965）的結果，每個N -Vertex圖最多都具有3 N /3最大集團。它們可以由Bron -Kerbosch算法列出，這是Bron＆Kerbosch（1973）的遞歸回溯過程。該過程的主要遞歸子例例程有三個參數：部分構造（非最大）集團，一組可以添加到該集團的候選頂點，以及另一組不應添加的頂點（因為這樣做將引導到已經找到的集團）。該算法嘗試將候選頂點一一添加到部分集團中，對每個集團進行遞歸調用。嘗試了每個頂點後，它將其移至不應再次添加的頂點。該算法的變體可以證明具有最差的運行時間O （3 N /3 ） ，與可能需要列出的集團數量匹配。因此，這為列出所有最大集團的問題提供了最壞的最佳解決方案。此外，據報導，野馬– kerbosch算法在實踐中比其替代方案要快。
但是，當集團的數量明顯小於其最壞情況時，其他算法可能是可取的。作為Tsukiyama等。 （1977年）表明，也有可能在每個生成集團多項式的時間內列出圖中的所有最大集團。像它們的運行時間取決於輸出大小的算法一樣，稱為輸出敏感算法。它們的算法基於以下兩個觀察結果，將給定圖G的最大集團與通過從G：從G ：從G：刪除任意的頂點V形成的圖G \ V的最大簇相關。
- 對於g \ v的每個最大集團k ， k在G中繼續形成最大集團，或者K { v }在G中形成最大集團。因此， g至少具有與g \ v一樣多的最大集團。
- G \ V中不包含V的每個最大集團都是最大列， G \ V中的每個最大列中包含V的每個最大集合可以通過添加V中的g \ v中的最大列中k形成v，並通過添加v並刪除非鄰域來自K的V。
使用這些觀察結果，它們可以通過任意選擇頂點v的遞歸算法來生成G中G中的所有最大列，然後對於G \ V中的每個最大列中的k ，然後輸出K和通過將V添加到K形成的c，並去除非v形成的clique。 - v 。但是， G \ V的多個父群可以以這種方式生成某些G的G ，因此，僅當G \ V中的父級在所有可能的父屬中，它們在g \ v中是詞典上最大的，它們消除了重複。根據該原則，他們表明， G中的所有最大集團都可以在每個集團的時間O （ Mn ）中生成，其中M是G和N中的邊數的數量。 Chiba＆Nishizeki（1985）每個集團將其改進為O（ MA ） ，其中A是給定圖的支撐性。 Makino＆Uno（2004）基於快速矩陣乘法提供了一種替代輸出敏感算法。 Johnson＆Yannakakis（1988）表明，每個集團都可以以多項式延遲以多項式延遲列出所有最大集團。但是，排序的選擇對於該算法的效率很重要：對於此順序的逆轉，除非p = np ，否則沒有多項式 - 延遲算法。
在此結果的基礎上，對於多項式時間的多項式族中，可以列出所有最大列，其中集團數量是多項式界定的。這些家族包括弦圖，完整的圖，無三角形圖，間隔圖，有界框的圖和平面圖。特別是，平面圖具有最多恆定大小的O （ n ）簇，可以在線性時間中列出。對於任何稀疏（最多具有恆定時間的邊緣數量的邊緣數量）並在採取子圖的操作下關閉的任何圖形家族也是如此。
在任意圖中查找最大集團
通過使用上面描述的一種算法來列出時間O （3 n /3 ）= O （3 n /3）= O（1.4422 n ）的最大集團或集團數字，通過使用上述算法之一列出所有最大集團圖並返回最大的圖。但是，對於集團問題的這種變體，最好的最差時間是可能的。 Tarjan＆Trojanowski（1977）的算法解決了這個問題O （2 N /3 ）= O （1.2599 N ） 。這是一種類似於bron -kerbosch算法的遞歸回溯方案，但是當可以證明呼叫中發現的集團是次優的時，能夠消除一些遞歸調用。 Jian（1986）提高了O （2 0.304 N ）= O （1.2346 N ）的時間， Robson（1986）將其改進到O （2 0.276 N ）= O （1.2108 N ）時間，以更大的空間使用為代價。 Robson的算法結合了類似的回溯方案（具有更複雜的案例分析）和動態編程技術，其中對補體圖的所有小型連接子圖的最佳解決方案進行了預定。這些部分溶液用於捷徑遞歸遞歸。今天已知的最快算法是Robson（2001）的精製版本，該版本在時間O （2 0.249 N ）= O （1.1888 N ）中運行。
基於分支機構和界限，本地搜索，貪婪算法和約束編程的方法，也已經對啟發式算法進行了廣泛的啟發式算法研究。建議查找集團的非標準計算方法包括DNA計算和絕熱量子計算。最大的集團問題是DIMAC在1992 - 1993年贊助的實施挑戰的主題，以及用作挑戰基準的圖表集合，這是公開可用的。
特殊類
上面已經討論了平面圖和其他稀疏圖的家族：它們具有線性的許多最大簇，可以在線性時間內列出。特別是，對於平面圖，庫拉托夫斯基定理的任何集團最多都可以具有四個頂點。
完美的圖是由其集團數等於其色數的屬性來定義的，並且此相等性在每個誘導的子圖中也具有。對於完美的圖形，可以使用基於半決賽編程的算法在多項式時間內找到最大集團。但是，該方法是複雜且非組合的，並且已經為許多完美圖的子類開發了專門的結合算法。在雙方圖的補充圖中， Kőnig的定理允許使用用於匹配的技術解決最大集團問題。在另一類的完美圖中，置換圖，最大集團是定義圖的排列的最長降低子序列，可以使用已知算法來發現最長降低子序列問題的已知算法。相反，可以等效地將最長減少子序列問題的每個實例描述為在排列圖中找到最大集團的問題。即使，Pnueli＆Lempel（1972）也為可比性圖中的最大集團提供了一種替代性二次時算法，這是一種更廣泛的完美圖，其中包含置換圖作為特殊情況。在和弦圖中，可以通過在消除順序中列出頂點並在此順序中檢查每個頂點的集團鄰域，從而找到最大集團。
在某些情況下，這些算法也可以擴展到其他不完美的圖形類別。例如，在圓形圖中，每個頂點的鄰域是一個置換圖，因此可以通過將置換圖算法應用於每個鄰域來找到圓形圖中的最大集團。同樣，在單位磁盤圖（具有已知幾何表示）中，基於將算法應用於兩分圖的互補的最大算法的多項式時間算法，將其備份到成對的頂點共享鄰域。
KARP（1976）建議，在從ERDőS -Rényi模型中繪製的最大集合（每個邊緣以1/2的概率出現）中找到最大集合的算法問題（其中每個邊緣都以1/2的形式出現） 。由於隨機圖中的最大集合具有對數大小的高概率，因此可以通過預期時間2 O （log 2 n ）中的蠻力搜索來找到它。這是一個準多功能時間結合。儘管此類圖的集團數量通常非常接近2 log 2 n ，但是簡單的貪婪算法以及更複雜的隨機近似技術只能找到具有大小為log 2 n的集團，一半是大。此類圖中的最大列數的數量在log 2 n中具有很高的概率指數，從而阻止了列出所有最大集團在多項式時間內運行的方法。由於這個問題的困難，幾位作者研究了種植的集團問題，這是在隨機圖上通過添加大量集團增加的隨機圖。雖然光譜方法和半決賽編程可以檢測隱藏的大小ω（ √n ）的隱藏簇，但目前尚無多項式時間算法檢測大小O （ √n ）的算法（使用小O表示法表示）。
近似算法
幾位作者考慮了試圖找到一個集團或獨立集的近似算法，儘管不是最大值，但其大小與多項式時間中的最大值一樣接近最大值。儘管這項工作的大部分集中在稀疏圖中的獨立集上，但這種情況對於互補的集團問題沒有意義，但也有一些不使用此類稀疏假設的近似算法的工作。
Feige（2004）描述了一種多項式時間算法，該算法在任何具有clique numberω （ n /log k n ）的圖中找到了一個大小ω（（log n /log log n ） 2 ）的集團。通過使用此算法時，當給定輸入圖的集合數為N /log N和N /Log 3 N之間，切換到Boppana＆Halldórsson（1992）的不同算法的圖形，用於具有較高集團數字的圖形，並選擇兩個 -頂點集團如果兩種算法都找不到任何東西， Feige提供了一種近似算法，該算法在最大值的O（ n （log log n ） 2 /log 3 n ）內找到了一個具有多個頂點的集團。儘管該算法的近似值很弱，但它是迄今為止最著名的。下面描述的近似硬度的結果表明，不可能有近似值的近似算法明顯小於線性。
下限
NP完整性
集團決策問題是NP完成的。這是理查德·卡普（Richard Karp）最初的21個問題之一，在他的1972年論文“在組合問題中的可降低性”中顯示了NP庫存。斯蒂芬·庫克（Stephen Cook）的論文中也提到了這個問題，引入了NP完整問題的理論。由於決策問題的硬度，找到最大集團的問題也是NP-HARD。如果一個人可以解決它，也可以通過將最大集團的大小與決策問題輸入的大小參數進行比較，也可以解決決策問題。
KARP的NP完整性證明是從布爾可滿足性問題中降低的。它描述瞭如何將布爾公式以結合性正常形式（CNF）轉化為最大集團問題的等效實例。反過來，在庫克湖定理中證明了NP完整的滿意度。從給定的CNF公式中，KARP形成一個圖形，該圖具有每個對（ V ， c ）的頂點，其中V是變量或其否定， C是包含V的公式中的子句。如果這些頂點中的兩個代表不同子句的兼容變量分配，則通過邊緣連接。也就是說，每當c ≠ d ＆ u and v不是彼此的否定時，從（ v ， c ）到（ u ， d ）的邊緣。如果k表示CNF公式中的子句的數量，則該圖中的k -Vertex集團表示將真實值分配給其某些變量以滿足公式的一致方法。因此，僅當存在k -vertex集團時，該公式才能滿足。
可以在輸入大小參數n的sublinear函數中指數的及時解決某些NP完整問題（例如平面圖中的旅行推銷員問題），比蠻力搜索要快得多。但是，在任意圖中的集團問題可能不可能進行這種次指數時間結合，因為對於許多其他標準的NP NP完整問題，這意味著類似的小指數界限。
電路複雜性
集團問題的計算難度已導致它被用來證明電路複雜性中的幾個下限。一個給定大小的集團的存在是單調圖屬性，這意味著，如果在給定圖中存在一個集團，則它將存在於任何超級圖中。由於該屬性是單調的，因此必須使用僅使用門和或門的單調電路，以解決給定固定集團大小的集團決策問題。但是，這些電路的大小可以證明是頂點數量和集團大小的超級物質函數，這是頂點數量的立方根中的指數。即使允許少數不蓋茨，複雜性仍然是超級物質的。此外，使用有界風扇的門的單調電路的深度必須至少在集團大小中是多項式。
決策樹的複雜性
確定圖形屬性的（確定性的）決策樹的複雜性是“頂點u和頂點V之間有邊緣的問題”的數量？在最壞的情況下必須回答，以確定圖形是否具有特定屬性。也就是說，這是該問題布爾決策樹的最小高度。有n （ n -1）/2可能的問題。因此，任何圖形屬性都可以用最多n （ n -1）/2問題確定。還可以定義屬性的隨機和量子決策樹的複雜性，預期的問題數（對於最壞的情況輸入）需要回答，以正確地確定給定的圖是否具有屬性，以確定隨機或量子算法。
由於包含一個集團的特性是單調的，因此它被Aanderaa-Karp – Rosenberg的猜想所覆蓋，該猜想指出，確定確定任何非平凡單調圖屬性的確定性決策樹複雜性正好為N （ n -1） /2 。對於任意單調圖屬性，該猜想仍然未經證實。但是，對於確定性的決策樹，對於2≤k≤n範圍內的任何k ，包含k個clique的特性被Bollobás（1976）證明其具有n （ n -1）/2的決策樹複雜性。確定性決策樹還需要指數尺寸才能檢測集團或大型多項式大小以檢測有界大小的集團。
Aanderaa – Karp – Rosenberg的猜想還指出，非平凡單調函數的隨機決策樹的複雜性為θ（ n 2 ） 。猜想再次尚未證實，但已解決了包含2≤k≤n的k個集團的特性。已知該特性具有隨機決策樹的複雜性θ（ n 2 ） 。對於量子決策樹，最著名的下限是ω（ n ） ，但沒有匹配算法以k≥3為例而聞名。
固定參數的難治性
參數化的複雜性是自然配備小整數參數K的問題的複雜性理論研究，並且隨著K的增加，問題變得更加困難，例如在圖中找到k個cliques。如果存在用於在大小n的輸入和函數f的輸入中求解的算法，則可以說問題是固定參數的，因此該算法在時間f （ k ） n o （1）中運行。也就是說，如果可以在多項式時間內解決k的任何固定值，則可以解決固定參數，並且如果多項式的指數不取決於k 。
為了查找K -Vertex集團，蠻力搜索算法具有運行時間O（ N K K 2 ） 。由於n的指數取決於k ，因此該算法不是固定參數的處理。儘管可以通過快速矩陣乘法來改進它，但運行時間仍然具有k中線性的指數。因此，儘管對於任何固定的k ，對於集團問題的已知算法的運行時間都是多項式，但這些算法對於固定參數的障礙不足。 Downey＆Fellows（1995）定義了一個參數性問題的層次結構，即構造的構造，即他們猜想沒有固定參數可拖動的算法。他們證明，對於該層次結構的第一級， W [1] ，獨立集（或等同於集團）很難。因此，根據他們的猜想，集團沒有固定參數可拖動的算法。此外，該結果為w [1] - hADTINS的證明提供了基礎，因此是庫克– Levin定理的參數化複雜性的類似物。
Chen等。 （2006年）表明，除非指數時間假設失敗，否則在時間n o （ k ）中找到k vertex集團無法完成。同樣，這提供了證據，表明沒有固定參數可拖動算法。
儘管列出最大集團或查找最大集團的問題不太可能與參數k進行固定參數，但它們可能是實例複雜性的其他參數的固定參數。例如，當通過輸入圖的墮落性參數化時，已知兩個問題都是固定參數。
近似的硬度
薄弱的結果暗示，長期以來，很難大致知道集團問題。 Garey＆Johnson（1978）觀察到，由於集團的數字具有小的整數值，並且是NP-HARD的計算，因此它不能具有完全多項式的時間近似方案。如果有太準確的近似值，則將其值舍入整數將提供確切的集團數字。但是，直到1990年代初，幾位作者開始在最大集團的近似和概率可檢查的證據之間建立聯繫。他們使用這些連接證明了最大集團問題的近似結果的硬度。在對這些結果進行了許多改進之後，現在已經知道，對於每個實際數字ε > 0 ，都不可能有多項式時間算法將最大列表近似於比O （ n 1 -ε ）更好的因素，除非p = np = np 。
這些無Ximibibibility結果的粗略想法是形成一個圖形，該圖代表NP完整問題（例如布爾值滿意度問題）的概率可檢查的證明系統。在概率可檢查的證明系統中，證明表示為一系列位。可滿足性問題的實例在且僅當可滿足時才具有有效的證明。通過算法檢查了證明，該算法在對滿意度問題的輸入上進行多項式時間計算後，選擇檢查了證明字符串的少數隨機選擇位置。根據在該位樣本中發現的值，檢查器將接受或拒絕證明，而無需查看其餘部分。不允許虛假負面：必須始終接受有效的證據。但是，有時可能會錯誤地接受無效的證據。對於每個無效的證明，Checker接受它的可能性必須很低。
為了將這種類型的概率可檢查的證明系統轉換為集團問題，一個人形成了一個帶有頂點的圖形，以適用於證明檢查器的每個可能的運行。也就是說，一個頂點是由要檢查的一組位置的可能隨機選擇之一定義的，以及那些會導致檢查人員接受證明的位置的位值。它可以用一個部分單詞表示，每個檢查位置的0或1在每個剩餘位置都有一個通配符。在此圖中，兩個頂點是相鄰的，如果相應的兩個接受運行，請參見它們都檢查的每個位置的相同位值。每個（有效或無效的）證明字符串對應於一個集團，一組接受該證明字符串的運行以及所有最大集團都以這種方式出現。當且僅當它與許多證明檢查員接受的證明字符串相對應時，這些集團之一很大。如果原始的滿足實例可滿足，則它將具有有效的證明字符串，該字符串由Checker的所有運行都接受，並且該字符串將對應於圖中的一個大集團。但是，如果原始實例無法滿足，則所有證明字符串都是無效的，每個證明字符串只有少量的Checker運行會錯誤地接受它，並且所有集團都很小。因此，如果一個人可以在具有較大集團的圖形和所有集團很小的圖形和圖表之間區分多項式時間，或者如果可以準確地近似集團問題，則將此近似值應用於從滿意度實例中生成的圖表，將允許令人滿意的實例與不滿意的實例區分開。但是，除非p = np，否則這是不可能的。