ในวิทยาการคอมพิวเตอร์ปัญหาคลิก (Clique problem)คือปัญหาการคำนวณในการหาคลิก (เซตย่อยของจุดยอดที่อยู่ติดกันทั้งหมด หรือเรียกว่ากราฟย่อยสมบูรณ์ ) ในกราฟ ปัญหานี้มีหลายรูปแบบขึ้นอยู่กับว่าควรหาคลิกใด และข้อมูลเกี่ยวกับคลิกเหล่านั้นคืออะไร รูปแบบทั่วไปของปัญหาคลิก ได้แก่ การหาคลิกสูงสุด (คลิกที่มีจำนวนจุดยอดมากที่สุดเท่าที่จะเป็นไปได้) การหาคลิกน้ำหนักสูงสุดในกราฟถ่วงน้ำหนัก การแสดงรายการคลิกสูงสุด ทั้งหมด (คลิกที่ไม่สามารถขยายได้อีก) และการแก้ปัญหาการตัดสินใจว่ากราฟมีคลิกที่มีขนาดใหญ่กว่าขนาดที่กำหนดหรือไม่

ปัญหากลุ่มคนสนิท (Clique problem) เกิดขึ้นในบริบทจริงดังต่อไปนี้ พิจารณาเครือข่ายสังคม ออนไลน์ ที่ จุดยอดของกราฟ แทนบุคคล และ เส้นเชื่อมของกราฟแทนความรู้จักซึ่งกันและกัน กลุ่มคนสนิทจึงหมายถึงกลุ่มย่อยของบุคคลที่รู้จักกันทั้งหมด และสามารถใช้อัลกอริธึมในการค้นหากลุ่มคนสนิทเพื่อค้นหากลุ่มเพื่อนร่วมกันเหล่านี้ได้ นอกเหนือจากการประยุกต์ใช้ในเครือข่ายสังคมออนไลน์แล้ว ปัญหากลุ่มคนสนิทยังมีการประยุกต์ใช้มากมายในชีวสารสนเทศศาสตร์และเคมีเชิงคำนวณอีก ด้วย

ปัญหาคลิกส่วนใหญ่ยาก ปัญหาการตัดสินใจคลิกเป็นปัญหาNP-complete (หนึ่งใน21 ปัญหา NP-complete ของ Karp ) ปัญหาการหาคลิกสูงสุดนั้นทั้งยากต่อการแก้ไขด้วยพารามิเตอร์คงที่และยากที่จะประมาณค่าและการแสดงรายชื่อคลิกสูงสุดทั้งหมดอาจต้องใช้เวลาแบบเลขชี้กำลังเนื่องจากมีกราฟที่มีคลิกสูงสุดจำนวนมหาศาล ดังนั้น ทฤษฎีเกี่ยวกับปัญหาคลิกส่วนใหญ่จึงมุ่งเน้นไปที่การระบุประเภทพิเศษของกราฟที่ยอมรับอัลกอริทึมที่มีประสิทธิภาพมากขึ้น หรือการกำหนดความยากในการคำนวณของปัญหาทั่วไปในแบบจำลองการคำนวณต่างๆ

ในการค้นหาคลิกที่ใหญ่ที่สุด เราสามารถตรวจสอบเซตย่อยทั้งหมดอย่างเป็นระบบได้ แต่การค้นหาแบบใช้กำลัง ทั้งหมดนี้ ใช้เวลานานเกินไปจนไม่เหมาะสมสำหรับเครือข่ายที่มีจุดยอดมากกว่าสองสามสิบจุด แม้ว่าจะไม่มี อัลกอริทึมที่มีประสิทธิภาพ ในเวลาพหุนามสำหรับปัญหานี้ แต่ก็มี อัลกอริทึม ที่มีประสิทธิภาพมากกว่า การค้นหาแบบใช้กำลังทั้งหมดนี้ ตัวอย่างเช่นอัลกอริทึม Bron–Kerboschสามารถใช้ในการแสดงรายการคลิกที่ใหญ่ที่สุดทั้งหมดได้ในเวลาที่ดีที่สุดในกรณีที่เลวร้ายที่สุด และยังสามารถแสดงรายการเหล่านั้นได้ในเวลาพหุนามต่อคลิกอีกด้วย

การศึกษาเกี่ยวกับกราฟย่อยสมบูรณ์ในทางคณิตศาสตร์มีมาก่อนคำศัพท์ "คลิก" ตัวอย่างเช่น กราฟย่อยสมบูรณ์ปรากฏขึ้นครั้งแรกในวรรณกรรมทางคณิตศาสตร์ในการปรับปรุงทฤษฎีแรมซีย์ใหม่โดยใช้ทฤษฎีกราฟโดยErdős & Szekeres (1935)แต่คำว่า "คลิก" และปัญหาของการจัดทำรายการคลิกด้วยอัลกอริทึมนั้นมาจากสังคมศาสตร์ ซึ่งกราฟย่อยสมบูรณ์ถูกใช้เพื่อจำลองกลุ่มทางสังคมกลุ่มคนที่รู้จักกันทั้งหมดLuce & Perry (1949)ใช้กราฟเพื่อจำลองเครือข่ายสังคม และปรับคำศัพท์ทางสังคมศาสตร์ให้เข้ากับทฤษฎีกราฟ พวกเขาเป็นคนแรกที่เรียกกราฟย่อยสมบูรณ์ว่า "คลิก" อัลกอริทึมแรกสำหรับการแก้ปัญหาคลิกคือของ Harary & Ross ( 1957) ^{[ 1 ]}ซึ่งได้รับแรงบันดาลใจจากการประยุกต์ใช้ทางสังคมวิทยา นักวิจัยด้านสังคมศาสตร์ยังได้กำหนดประเภทของกลุ่มย่อยและกลุ่มย่อยสูงสุดในเครือข่ายสังคมไว้อีกหลายประเภท ซึ่งเป็น "กลุ่มย่อยที่เหนียวแน่น" ของบุคคลหรือผู้กระทำในเครือข่ายที่ต่างก็มีความสัมพันธ์ในการเชื่อมต่อกันในรูปแบบต่างๆ แนวคิดทั่วไปเกี่ยวกับกลุ่มย่อยเหล่านี้จำนวนมากสามารถพบได้โดยการสร้างกราฟแบบไม่มีทิศทางซึ่งขอบแสดงถึงคู่ของผู้กระทำที่เกี่ยวข้องจากเครือข่ายสังคม จากนั้นจึงนำอัลกอริทึมสำหรับปัญหากลุ่มย่อยมาใช้กับกราฟนี้^{[ 2 ]}

นับตั้งแต่ผลงานของ Harary และ Ross นักวิจัยคนอื่นๆ ก็ได้คิดค้นอัลกอริทึมสำหรับปัญหาคลิกหลายเวอร์ชัน^{[ 1 ]}ในช่วงทศวรรษ 1970 นักวิจัยเริ่มศึกษาอัลกอริทึมเหล่านี้จากมุมมองของการวิเคราะห์กรณีที่เลวร้ายที่สุดดูตัวอย่างเช่นTarjan & Trojanowski (1977)ซึ่งเป็นงานในช่วงแรกๆ เกี่ยวกับความซับซ้อนของกรณีที่เลวร้ายที่สุดของปัญหาคลิกสูงสุด นอกจากนี้ ในช่วงทศวรรษ 1970 นักวิจัยเริ่มใช้ทฤษฎีความสมบูรณ์ของ NPและผลลัพธ์ความยากในการแก้ปัญหาที่เกี่ยวข้องเพื่ออธิบายทางคณิตศาสตร์ถึงความยากลำบากที่รับรู้ได้ของปัญหาคลิก โดย เริ่มจากผลงานของ Cook (1971 )และKarp (1972) ในช่วงทศวรรษ 1990 ชุดบทความที่ก้าวล้ำซึ่งเริ่มต้นด้วย Feige et al. (1991)แสดงให้เห็นว่า (โดยสมมติว่าP ≠ NP ) เป็นไปไม่ได้เลยที่จะประมาณปัญหาได้อย่างแม่นยำและมีประสิทธิภาพ

อัลกอริทึมการค้นหาคลิกถูกนำมาใช้ในวิชาเคมีเพื่อค้นหาสารเคมีที่ตรงกับโครงสร้างเป้าหมาย^{[ 3 ]}และเพื่อจำลองการเชื่อมต่อโมเลกุลและตำแหน่งการจับของปฏิกิริยาเคมี^{[ 4 ]}นอกจากนี้ยังสามารถใช้เพื่อค้นหาโครงสร้างที่คล้ายกันภายในโมเลกุลที่แตกต่างกันได้^{[ 5 ]}ในการใช้งานเหล่านี้ จะมีการสร้างกราฟขึ้นมา โดยที่แต่ละจุดยอดแทนอะตอมคู่ที่ตรงกัน ซึ่งมาจากโมเลกุลสองโมเลกุล จุดยอดสองจุดจะเชื่อมต่อกันด้วยขอบ หากการจับคู่ที่แสดงนั้นเข้ากันได้ ความเข้ากันได้อาจหมายความว่า ระยะห่างระหว่างอะตอมภายในโมเลกุลทั้งสองนั้นใกล้เคียงกัน โดยมีค่าความคลาดเคลื่อนที่กำหนดไว้ คลิกในกราฟนี้แทนชุดของอะตอมคู่ที่ตรงกัน ซึ่งการจับคู่ทั้งหมดเข้ากันได้^{[ 6 ]}กรณีพิเศษของวิธีนี้คือการใช้ผลคูณแบบโมดูลาร์ของกราฟเพื่อลดปัญหาการค้นหากราฟย่อยที่เหนี่ยวนำร่วมกันสูงสุดของกราฟสองกราฟให้เหลือเพียงปัญหาการค้นหาคลิกสูงสุดในผลคูณของกราฟทั้งสอง^{[ 7 ]}

ในการสร้างรูปแบบการทดสอบอัตโนมัติการค้นหาคลิกสามารถช่วยจำกัดขนาดของชุดทดสอบได้^{[ 8 ]}ในชีวสารสนเทศศาสตร์ อัลกอริทึมการค้นหาคลิกถูกนำมาใช้เพื่ออนุมานต้นไม้วิวัฒนาการ^{[ 9 ]}ทำนายโครงสร้างโปรตีน [ ^{10 ] และ}ค้นหากลุ่มโปรตีนที่มีปฏิสัมพันธ์กันอย่างใกล้ชิด^{[ 11 ]}การแสดงรายการคลิกในกราฟความสัมพันธ์เป็นขั้นตอนสำคัญในการวิเคราะห์กระบวนการสุ่มบางอย่าง^{[ 12 ]}ในทางคณิตศาสตร์ข้อสันนิษฐานของ Keller เกี่ยวกับการปูพื้น ไฮเปอร์คิวบ์แบบหน้าต่อหน้าถูกหักล้างโดยLagarias & Shor (1992)ซึ่งใช้อัลกอริทึมการค้นหาคลิกบนกราฟที่เกี่ยวข้องเพื่อค้นหาตัวอย่างค้าน^{[ 13 ]}

กราฟแบบไม่มีทิศทางประกอบด้วย เซต ของจุดยอดจำนวนจำกัดและเซตของคู่จุดยอดที่ไม่มีลำดับ ซึ่งเรียกว่าขอบตามธรรมเนียมในการวิเคราะห์อัลกอริทึม จำนวนจุดยอดในกราฟจะใช้สัญลักษณ์nและจำนวนขอบจะใช้สัญลักษณ์mกลุ่มคลิก (clique)ในกราฟGคือกราฟย่อยสมบูรณ์ของGกล่าวคือ เป็นเซตย่อยKของจุดยอด โดยที่จุดยอดสองจุดใดๆ ในKเป็นจุดปลายทั้งสองของขอบในGกลุ่มคลิกสูงสุด (maximal clique)คือกลุ่มคลิกที่ไม่สามารถเพิ่มจุดยอดเข้าไปได้อีก สำหรับแต่ละจุดยอดvที่ไม่ได้เป็นส่วนหนึ่งของกลุ่มคลิกสูงสุด จะต้องมีจุดยอดw อีกจุดหนึ่ง ที่อยู่ในกลุ่มคลิกและไม่ติดกับvซึ่งจะป้องกันไม่ ให้ vถูกเพิ่มเข้าไปในกลุ่มคลิก กลุ่มคลิกสูงสุด (maximum clique)คือกลุ่มคลิกที่ประกอบด้วยจำนวนจุดยอดมากที่สุดเท่าที่จะเป็นไปได้ จำนวนคลิกω ( G )คือจำนวนจุดยอดในคลิกสูงสุด^ของ G ^{[ 1} ]

ปัญหาการค้นหากลุ่มที่เกี่ยวข้องอย่างใกล้ชิดหลายปัญหาได้รับการศึกษาแล้ว^{[ 14 ]}

• ในปัญหาคลิกสูงสุด อินพุตคือกราฟแบบไม่มีทิศทาง และเอาต์พุตคือคลิกสูงสุดในกราฟ หากมีคลิกสูงสุดหลายรายการ สามารถเลือกรายการใดรายการหนึ่งได้ตามอำเภอใจ^{[ 14 ]}
• ในปัญหาคลิกสูงสุดแบบถ่วงน้ำหนัก อินพุตคือกราฟแบบไม่มีทิศทางที่มีน้ำหนักบนจุดยอด (หรือขอบ ซึ่งพบได้น้อยกว่า) และเอาต์พุตคือคลิกที่มีน้ำหนักรวมสูงสุด ปัญหาคลิกสูงสุดเป็นกรณีพิเศษที่น้ำหนักทั้งหมดเท่ากัน^{[ 15 ]}นอกจากปัญหาการหาค่าเหมาะสมที่สุดของผลรวมน้ำหนักแล้ว ยังมีการศึกษาปัญหาการหาค่าเหมาะสมที่สุดแบบสองเกณฑ์ที่ซับซ้อนกว่านี้อีกด้วย^{[ 16 ]}
• ในปัญหาการแสดงรายการคลิกสูงสุด อินพุตคือกราฟแบบไม่มีทิศทาง และเอาต์พุตคือรายการคลิกสูงสุดทั้งหมดของกราฟนั้น ปัญหาคลิกสูงสุดอาจแก้ไขได้โดยใช้อัลกอริทึมสำหรับปัญหาการแสดงรายการคลิกสูงสุดเป็นขั้นตอนย่อย เนื่องจากคลิกสูงสุดจะต้องรวมอยู่ในคลิกสูงสุดทั้งหมด^{[ 17 ]}
• ใน ปัญหา k -clique อินพุตคือกราฟแบบไม่มีทิศทางและตัวเลขkเอาต์พุตคือ clique ที่มีk จุดยอด หากมีอยู่ หรือค่าพิเศษที่ ^ระบุว่าไม่มีk -clique มิฉะนั้น ในบางรูปแบบของปัญหานี้ เอาต์พุตควรแสดงรายการ clique ทั้งหมดที่มีขนาดk [ ^{18 ]}
• ในปัญหาการตัดสินใจเกี่ยวกับคลิก อินพุตคือกราฟแบบไม่มีทิศทางและตัวเลขkและเอาต์พุตคือค่าบูลีน : จริงถ้ากราฟมี คลิก kและเป็นเท็จในกรณีอื่น^{[ 19 ]}

ปัญหาสี่ข้อแรกเหล่านี้ล้วนมีความสำคัญในการใช้งานจริง ปัญหาการตัดสินใจคลิกไม่มีความสำคัญในทางปฏิบัติ มันถูกกำหนดขึ้นในลักษณะนี้เพื่อนำทฤษฎีความสมบูรณ์ของ NP ไปใช้ กับปัญหาการค้นหาคลิก^{[ 19 ]}

ปัญหาคลิกและปัญหาเซตอิสระเป็นส่วนเติมเต็มกัน กล่าวคือ คลิกในGเป็นเซตอิสระในกราฟส่วนเติมเต็มของGและในทางกลับกัน^{[ 20 ]}ดังนั้น ผลลัพธ์การคำนวณจำนวนมากจึงสามารถนำไปใช้กับปัญหาทั้งสองได้อย่างเท่าเทียมกัน และเอกสารวิจัยบางฉบับไม่ได้แยกความแตกต่างระหว่างสองปัญหานี้อย่างชัดเจน อย่างไรก็ตาม ปัญหาทั้งสองมีคุณสมบัติที่แตกต่างกันเมื่อนำไปใช้กับตระกูลกราฟที่จำกัด ตัวอย่างเช่น ปัญหาคลิกอาจแก้ไขได้ในเวลาพหุนามสำหรับกราฟระนาบ^{[ 21 ]}ในขณะที่ปัญหาเซตอิสระยังคงเป็น NP-hard บนกราฟระนาบ^{[ 22 ]}

กลุ่ม คลิก สูงสุดบางครั้งเรียกว่ากลุ่มคลิกแบบรวมสูงสุด คือกลุ่มคลิกที่ไม่ใช่กลุ่มคลิกขนาดใหญ่กว่า ดังนั้นทุกกลุ่มคลิกจึงอยู่ในกลุ่มคลิกสูงสุด^{[ 23 ]}กลุ่มคลิกสูงสุดอาจมีขนาดเล็กมาก กราฟอาจมีกลุ่มคลิกที่ไม่ใช่กลุ่มคลิกสูงสุดที่มีจุดยอดจำนวนมาก และกลุ่มคลิกแยกต่างหากที่มีขนาด 2 ซึ่งเป็นกลุ่มคลิกสูงสุด ในขณะที่กลุ่มคลิกสูงสุด (เช่น กลุ่มคลิกที่ใหญ่ที่สุด) จำเป็นต้องเป็นกลุ่มคลิกสูงสุด แต่ในทางกลับกันนั้นไม่เป็นจริง มีกราฟบางประเภทที่ทุกกลุ่มคลิกสูงสุดเป็นกลุ่มคลิกสูงสุด ซึ่งกราฟเหล่านี้เป็นส่วนเติมเต็มของกราฟที่มีการครอบคลุมอย่างดีซึ่งทุกเซตอิสระสูงสุดเป็นกลุ่มคลิกสูงสุด^{[ 24 ]}อย่างไรก็ตาม กราฟอื่นๆ อาจมีกลุ่มคลิกสูงสุดที่ไม่ใช่กลุ่มคลิกสูงสุด

สามารถค้นหาคลิกสูงสุดเพียงคลิกเดียวได้ด้วยอัลกอริทึมโลภ แบบตรงไปตรง มา เริ่มต้นด้วยคลิกใดๆ (เช่น จุดยอดเดียวหรือแม้แต่เซตว่าง) ขยายคลิกปัจจุบันทีละจุดยอดโดยวนซ้ำผ่านจุดยอดที่เหลือของกราฟ สำหรับแต่ละจุดยอดvที่ลูปนี้ตรวจสอบ ให้เพิ่มvลงในคลิกหากมันอยู่ติดกับทุกจุดยอดที่อยู่ในคลิกอยู่แล้ว และทิ้งvมิฉะนั้น อัลกอริทึมนี้ทำงานในเวลาเชิงเส้น [ ^{25 ] เนื่องจาก} การค้นหาคลิกสูงสุดทำได้ง่าย และขนาดที่อาจเล็ก จึงมีการให้ความสนใจกับปัญหาอัลกอริทึมที่ยากกว่ามากในการค้นหาคลิกสูงสุดหรือคลิกขนาดใหญ่ อย่างไรก็ตาม งานวิจัยบางส่วนในอัลกอริทึมแบบขนานได้ศึกษาปัญหาการค้นหาคลิกสูงสุด โดยเฉพาะอย่างยิ่ง ปัญหาการค้นหา คลิกสูงสุดอันดับ แรกตามลำดับตัวอักษร (คลิกที่พบโดยอัลกอริทึมข้างต้น) ได้รับการพิสูจน์แล้วว่าสมบูรณ์สำหรับคลาสของฟังก์ชันเวลาพหุนาม ผลลัพธ์นี้บ่งชี้ว่าปัญหาไม่น่าจะสามารถแก้ไขได้ภายในคลาสความซับซ้อนแบบ^ขนาน NC [ ^{26 ]}

เราสามารถทดสอบได้ว่ากราฟGมี คลิก kจุดยอดหรือไม่ และค้นหาคลิกดังกล่าวที่กราฟ G มีอยู่ โดยใช้อัลกอริทึมแบบบรูทฟอร์ซ อัลกอริทึมนี้จะตรวจสอบกราฟย่อยแต่ละกราฟที่มีkจุดยอดและตรวจสอบว่ามันก่อตัวเป็นคลิกหรือไม่ ใช้เวลาO ( n ^k  k ² )ตามที่แสดงโดยใช้สัญกรณ์บิ๊กโอเนื่องจากมี กราฟย่อย O ( n ^k )ที่ต้องตรวจสอบ ซึ่งแต่ละกราฟย่อยมี ขอบ O ( k ² ) ที่ต้องตรวจสอบ การมีอยู่ของขอบเหล่านั้นในGดังนั้น ปัญหาอาจได้รับการแก้ไขในเวลาพหุนามเมื่อใดก็ตามที่kเป็นค่าคงที่ อย่างไรก็ตาม เมื่อkไม่มีค่าคงที่ แต่สามารถเปลี่ยนแปลงได้ตามส่วนหนึ่งของข้อมูลป้อนเข้าของปัญหา เวลาจะเป็นเลขชี้กำลัง^{[ 27 ]}

กรณีที่ไม่ธรรมดาที่ง่ายที่สุดของปัญหาการค้นหาคลิกคือการค้นหาสามเหลี่ยมในกราฟ หรือเทียบเท่ากับการพิจารณาว่ากราฟนั้นปราศจากสามเหลี่ยม หรือไม่ ในกราฟGที่มี ขอบ mเส้น อาจมีสามเหลี่ยมได้มากที่สุดΘ( m³ ^/² ) รูป (ใช้สัญลักษณ์เธต้าขนาดใหญ่เพื่อระบุว่าขอบเขตนี้แน่น) กรณีที่เลวร้ายที่สุดสำหรับสูตรนี้เกิดขึ้นเมื่อGเป็นคลิกเอง ดังนั้นอัลกอริทึมสำหรับการแสดงรายการสามเหลี่ยมทั้งหมดจะต้องใช้เวลาอย่างน้อยΩ( m³ ^/² )ในกรณีที่เลวร้ายที่สุด (ใช้สัญลักษณ์โอเมก้าขนาดใหญ่ ) และเป็นที่รู้จักอัลกอริทึมที่ตรงกับขอบเขตเวลาดังกล่าว^{[ 28 ]}ตัวอย่างเช่นChiba & Nishizeki (1985)อธิบายอัลกอริทึมที่เรียงลำดับจุดยอดตามลำดับจากดีกรีสูงสุดไปต่ำสุด จากนั้นวนซ้ำผ่านจุดยอดv แต่ละจุด ในรายการที่เรียงลำดับแล้ว เพื่อค้นหาสามเหลี่ยมที่รวมvและไม่รวมจุดยอดก่อนหน้าใดๆ ในรายการ ในการทำเช่นนั้น อัลกอริทึมจะทำเครื่องหมายเพื่อนบ้านทั้งหมดของvค้นหาขอบทั้งหมดที่เชื่อมต่อกับเพื่อนบ้านของvโดยสร้างรูปสามเหลี่ยมสำหรับทุกขอบที่มีจุดปลายสองจุดที่ทำเครื่องหมายไว้ จากนั้นจึงลบเครื่องหมายและลบv ออก จากกราฟ ดังที่ผู้เขียนแสดงให้เห็น เวลาสำหรับอัลกอริทึมนี้เป็นสัดส่วนกับความเป็นต้นไม้ของกราฟ (แทนด้วยa ( G ) ) คูณด้วยจำนวนขอบ ซึ่งคือO ( ma  ( G ))เนื่องจากความเป็นต้นไม้มีค่าสูงสุดO ( m¹ / ^² )อัลกอริทึมนี้จึงทำงานในเวลาO ( m³ ^/² )โดยทั่วไปแล้ว กลุ่มคลิก k จุดทั้งหมด สามารถแสดงรายการได้ด้วยอัลกอริทึมที่คล้ายกันซึ่งใช้เวลาเป็นสัดส่วนกับจำนวนขอบคูณด้วยความเป็นต้นไม้กำลัง( k  - 2 ) สำหรับกราฟที่มีจำนวนต้นไม้คงที่ เช่น กราฟระนาบ (หรือโดยทั่วไปกราฟจากตระกูลกราฟปิดไมเนอร์ที่ ไม่ใช่แบบธรรมดา ) อัลกอริทึมนี้ใช้ เวลา O ( m )ซึ่งถือว่าเหมาะสมที่สุด เนื่องจากเป็นเชิงเส้นตามขนาดของอินพุต^{[ 18 ]}

หากต้องการเพียงสามเหลี่ยมเดียว หรือต้องการให้แน่ใจว่ากราฟไม่มีสามเหลี่ยม ก็สามารถใช้อัลกอริธึมที่เร็วกว่าได้ ดังที่Itai & Rodeh (1978)สังเกต กราฟจะมีสามเหลี่ยมก็ต่อเมื่อเมทริกซ์ประชิดและกำลังสองของเมทริกซ์ประชิดมีค่าที่ไม่เป็นศูนย์ในเซลล์เดียวกัน ดังนั้น เทคนิค การคูณเมทริกซ์ที่รวดเร็วสามารถนำมาใช้เพื่อหาสามเหลี่ยมได้ในเวลาO ( n 2.376 ⁾ Alon , Yuster & Zwick (1994)ใช้การคูณเมทริกซ์ที่รวดเร็วเพื่อปรับปรุงอัลกอริธึ ม O ( m ^3/2 )สำหรับการหาสามเหลี่ยมให้เป็นO ( m ^1.41 ) อั ลกอริธึมเหล่านี้ที่ใช้การคูณเมทริกซ์ที่รวดเร็วยังได้รับการขยายไปยังปัญหาการหาk -cliques สำหรับค่าkที่ มากขึ้นด้วย ^{[ 29 ]}

จากผลงานวิจัยของMoon & Moser (1965)กราฟที่มี n จุดยอดทุกกราฟจะมีคลิกสูงสุดอย่างมากที่สุด³ⁿ / 3 คลิก^{สามารถ}แสดงรายการคลิกเหล่านี้ได้โดยใช้อัลกอริทึม Bron–Kerbosch ซึ่งเป็นกระบวนการ ย้อนกลับแบบเรียกซ้ำของBron & Kerbosch (1973)รูทีนย่อยแบบเรียกซ้ำหลักของกระบวนการนี้มีอาร์กิวเมนต์สามตัว ได้แก่ คลิกที่สร้างขึ้นบางส่วน (ไม่ใช่คลิกสูงสุด) ชุดของจุดยอดที่อาจถูกเพิ่มเข้าไปในคลิก และอีกชุดของจุดยอดที่ไม่ควรเพิ่มเข้าไป (เพราะการเพิ่มเข้าไปจะทำให้ได้คลิกที่เคยพบแล้ว) อัลกอริทึมจะลองเพิ่มจุดยอดที่เป็นตัวเลือกทีละจุดเข้าไปในคลิกที่สร้างขึ้นบางส่วน โดยเรียกซ้ำสำหรับแต่ละจุดยอด หลังจากลองแต่ละจุดยอดแล้ว จะย้ายจุดยอดนั้นไปยังชุดของจุดยอดที่ไม่ควรเพิ่มเข้าไปอีก สามารถแสดงให้เห็นว่าอัลกอริธึมรูปแบบต่างๆ นี้มีเวลาในการรันกรณีเลวร้ายที่สุดO (3 ^{n /3} )ซึ่งตรงกับจำนวนคลิกที่อาจต้องแสดงรายการ^{[ 30 ]}ดังนั้น นี่จึงเป็นวิธีแก้ปัญหาที่ดีที่สุดในกรณีเลวร้ายที่สุดสำหรับการแสดงรายการคลิกสูงสุดทั้งหมด นอกจากนี้ อัลกอริธึม Bron–Kerbosch ยังได้รับการรายงานอย่างกว้างขวางว่าเร็วกว่าอัลกอริธึมทางเลือกอื่นๆ ในทางปฏิบัติ^{[ 31 ]}

อย่างไรก็ตาม เมื่อจำนวนคลิกมีน้อยกว่ากรณีที่เลวร้ายที่สุดอย่างมีนัยสำคัญ อัลกอริทึมอื่นๆ อาจเหมาะสมกว่า ดังที่Tsukiyama et al. (1977)แสดงให้เห็นว่า เป็นไปได้ที่จะแสดงรายการคลิกสูงสุดทั้งหมดในกราฟในเวลาที่เป็นพหุนามต่อคลิกที่สร้างขึ้น อัลกอริทึมเช่นของพวกเขาซึ่งเวลาในการทำงานขึ้นอยู่กับขนาดของผลลัพธ์เรียกว่าอัลกอริทึมที่ไวต่อผลลัพธ์ อัลกอริทึมของพวกเขามีพื้นฐานมาจากการสังเกตสองประการต่อไปนี้ ซึ่งเชื่อมโยงคลิกสูงสุดของกราฟG ที่กำหนด ให้กับคลิกสูงสุดของกราฟG  \  vที่เกิดจากการลบจุดยอดv ใดๆ ออก จากG :

• สำหรับคลิกสูงสุดK ทุกตัว ในG  \  vนั้นKจะยังคงเป็นคลิกสูงสุดในG ต่อไป หรือK  ⋃ { v }จะเป็นคลิกสูงสุดในGดังนั้นG จึง มีคลิกสูงสุดอย่างน้อยเท่ากับจำนวนคลิกสูงสุดในG  \  v
• แต่ละคลิกสูงสุดในGที่ไม่มีv อยู่ภายใน จะเป็นคลิกสูงสุดในG  \  vและแต่ละคลิกสูงสุดในGที่มีv อยู่ภายใน สามารถสร้างขึ้นได้จากคลิกสูงสุดKในG  \  vโดยการเพิ่มv เข้าไป และลบสมาชิกที่ไม่ใช่เพื่อนบ้านของvออกจากK

จากการสังเกตเหล่านี้ พวกเขาสามารถสร้างคลิกสูงสุดทั้งหมดในGได้โดยใช้อัลกอริทึมแบบเรียกซ้ำ ซึ่งจะเลือกจุดยอดvอย่างสุ่ม และจากนั้น สำหรับแต่ละคลิกสูงสุดKในG  \  vจะส่งออกทั้งKและคลิกที่เกิดจากการเพิ่มvเข้าไปในKและลบจุดที่ไม่ใช่เพื่อนบ้านของv ออก อย่างไรก็ตาม คลิกบางคลิกของGอาจถูกสร้างขึ้นด้วยวิธีนี้จากคลิกแม่มากกว่าหนึ่งคลิกในG  \  vดังนั้นพวกเขาจึงกำจัดรายการที่ซ้ำกันโดยการส่งออกคลิกในGก็ต่อเมื่อคลิกแม่ในG  \  vมีค่าสูงสุดตามลำดับตัวอักษรในบรรดาคลิกแม่ที่เป็นไปได้ทั้งหมด บนพื้นฐานของหลักการนี้ พวกเขาแสดงให้เห็นว่าคลิกสูงสุดทั้งหมดในGอาจถูกสร้างขึ้นได้ในเวลาO ( mn )ต่อคลิก โดยที่mคือจำนวนขอบในGและnคือจำนวนจุดยอดChiba & Nishizeki (1985)ปรับปรุงสิ่งนี้เป็นO( ma )ต่อคลิก โดยที่aคือความเป็นต้นไม้ของกราฟที่กำหนดMakino & Uno (2004)เสนออัลกอริทึมทางเลือกที่ไวต่อผลลัพธ์โดยอาศัยการคูณเมทริกซ์อย่างรวดเร็วJohnson & Yannakakis (1988)แสดงให้เห็นว่าเป็นไปได้ที่จะแสดงรายการคลิกสูงสุดทั้งหมดตามลำดับพจนานุกรมโดยมีการหน่วงเวลาพหุนามต่อคลิก อย่างไรก็ตาม การเลือกการเรียงลำดับมีความสำคัญต่อประสิทธิภาพของอัลกอริทึมนี้: สำหรับการเรียงลำดับย้อนกลับ จะไม่มีอัลกอริทึมที่มีการหน่วงเวลาพหุนามเว้นแต่P = NP

จากผลลัพธ์นี้ เป็นไปได้ที่จะแสดงรายการคลิกสูงสุดทั้งหมดในเวลาพหุนาม สำหรับตระกูลของกราฟที่จำนวนคลิกมีขอบเขตพหุนาม ตระกูลเหล่านี้ได้แก่กราฟคอร์ดัลกราฟสมบูรณ์กราฟที่ไม่มีสามเหลี่ยม กราฟช่วงกราฟ ที่ มีกล่องจำกัดและกราฟระนาบ^{[ 32 ]}โดยเฉพาะอย่างยิ่ง กราฟระนาบมี คลิก O ( n )ซึ่งมีขนาดคงที่อย่างมาก และสามารถแสดงรายการได้ในเวลาเชิงเส้น เช่นเดียวกันนี้เป็นจริงสำหรับตระกูลของกราฟใดๆ ที่ทั้งเบาบาง (มีจำนวนขอบไม่เกินค่าคงที่คูณจำนวนจุดยอด) และปิดภายใต้การดำเนินการของการเลือกกราฟย่อย^{[ 18 ] [ 33 ]}

เป็นไปได้ที่จะหาคลิกสูงสุด หรือจำนวนคลิก ของ กราฟ nจุดยอดใดๆ ในเวลาO (3 ^{n /3} ) = O (1.4422 ⁿ )โดยใช้อัลกอริทึมใดอัลกอริทึมหนึ่งที่อธิบายไว้ข้างต้นเพื่อแสดงรายการคลิกสูงสุดทั้งหมดในกราฟและส่งคืนคลิกที่ใหญ่ที่สุด อย่างไรก็ตาม สำหรับปัญหาคลิกรูปแบบนี้ อาจมีขอบเขตเวลาในกรณีที่เลวร้ายที่สุดที่ดีกว่า อัลกอริทึมของTarjan & Trojanowski (1977)แก้ปัญหานี้ได้ในเวลาO (2 ^{n /3} ) = O (1.2599 ⁿ )เป็นวิธีการย้อนกลับแบบเรียกซ้ำคล้ายกับอัลกอริทึม Bron–Kerboschแต่สามารถกำจัดการเรียกซ้ำบางส่วนได้เมื่อสามารถแสดงได้ว่าคลิกที่พบในการเรียกนั้นจะไม่เหมาะสมที่สุดJian (1986)ปรับปรุงเวลาเป็นO (2 ^{0.304 n} ) = O (1.2346 ⁿ )และRobson (1986)ปรับปรุงเป็น เวลา O (2 ^{0.276 n} ) = O (1.2108 ⁿ )โดยแลกกับการใช้พื้นที่มากขึ้น อัลกอริทึมของ Robson ผสมผสานรูปแบบการย้อนกลับที่คล้ายกัน (ด้วยการวิเคราะห์กรณีที่ซับซ้อนกว่า) และ เทคนิค การเขียนโปรแกรมแบบไดนามิกซึ่งคำนวณโซลูชันที่เหมาะสมที่สุดล่วงหน้าสำหรับกราฟย่อยที่เชื่อมต่อขนาดเล็กทั้งหมดของกราฟส่วนเติมเต็มโซลูชันบางส่วนเหล่านี้ใช้เพื่อย่นระยะเวลาการเรียกซ้ำแบบย้อนกลับ อัลกอริทึมที่เร็วที่สุดที่รู้จักในปัจจุบันคือเวอร์ชันที่ปรับปรุงแล้วของวิธีนี้โดยRobson (2001)ซึ่งทำงานในเวลาO (2 ^{0.249 n} ) = O ( ^{1.1888 n} ) [ ^{34 ]}

นอกจากนี้ยังมีการวิจัยอย่างกว้างขวางเกี่ยวกับอัลกอริธึมฮิวริสติกสำหรับการแก้ปัญหาคลิกสูงสุดโดยไม่มีการรับประกันเวลาการทำงานในกรณีที่เลวร้ายที่สุด โดยอิงตามวิธีการต่างๆ เช่นการแบ่งสาขาและขอบเขต [ ^{35 ] การ}ค้นหา แบบโลคอ ล^{[ 36 ]}อัลกอริธึม โลภ ^{[ 37 ]}และ การ เขียนโปรแกรมแบบมีข้อจำกัด^{[ 38 ]}วิธีการคำนวณที่ไม่เป็นมาตรฐานที่ได้รับการแนะนำสำหรับการค้นหาคลิก ได้แก่การคำนวณ DNA ^{[ 39 ]}และการคำนวณควอนตัมแบบอะเดียแบติก^{[ 40 ]}ปัญหาคลิกสูงสุดเป็นหัวข้อของการท้าทายการใช้งานที่ได้รับการสนับสนุนโดยDIMACSในปี 1992–1993 ^{[ 41 ]}และชุดของกราฟที่ใช้เป็นเกณฑ์มาตรฐานสำหรับการท้าทาย ซึ่งเผยแพร่สู่สาธารณะ^{[ 42 ]}

กราฟระนาบและตระกูลอื่นๆ ของกราฟเบาบางได้รับการกล่าวถึงข้างต้นแล้ว: กราฟเหล่านี้มีคลิกสูงสุดจำนวนเชิงเส้นที่มีขนาดจำกัดซึ่งสามารถแสดงรายการได้ในเวลาเชิงเส้น^{[ 18 ]}โดยเฉพาะอย่างยิ่งสำหรับกราฟระนาบ คลิกใดๆ สามารถมีจุดยอดได้ไม่เกินสี่จุด ตามทฤษฎีบทของ Kuratowski ^{[ 21 ]}

กราฟสมบูรณ์ถูกกำหนดโดยคุณสมบัติที่ว่าจำนวนคลิกเท่ากับจำนวนสีและความเท่าเทียมกันนี้ยังคงใช้ได้กับกราฟย่อยที่เหนี่ยวนำ แต่ละ กราฟด้วย สำหรับกราฟสมบูรณ์ สามารถหาคลิกสูงสุดได้ในเวลาพหุนาม โดยใช้อัลกอริทึมที่อิงตามการเขียนโปรแกรมแบบกึ่งกำหนด [ ^{43 ] อย่างไรก็ตาม} วิธีนี้ซับซ้อนและไม่ใช่เชิงการจัดเรียง และได้มีการพัฒนาอัลกอริทึมการค้นหาคลิกเฉพาะสำหรับกราฟสมบูรณ์หลายคลาสย่อย^{[ 44 ]}ในกราฟส่วนเติมเต็มของกราฟสอง ส่วน ทฤษฎีบท ของKőnigอนุญาตให้แก้ปัญหาคลิกสูงสุดได้โดยใช้เทคนิคการจับคู่ในกราฟสมบูรณ์อีกคลาสหนึ่งคือกราฟการเรียงสับเปลี่ยนคลิกสูงสุดคือลำดับย่อยที่ลดลงยาวที่สุดของการเรียงสับเปลี่ยนที่กำหนดกราฟ และสามารถหาได้โดยใช้อัลกอริทึมที่รู้จักสำหรับปัญหาลำดับย่อยที่ลดลงยาวที่สุด ในทางกลับกัน ปัญหาลำดับย่อยที่ลดลงที่ยาวที่สุดทุกกรณีสามารถอธิบายได้อย่างเทียบเท่ากับปัญหาการค้นหาคลิกสูงสุดในกราฟการเรียงสับเปลี่ยน^{[ 45 ]}แม้แต่ Pnueli & Lempel (1972) ก็ยังเสนออัลกอริทึมทางเลือกแบบใช้เวลากำลังสองสำหรับคลิกสูงสุดในกราฟเปรียบเทียบซึ่งเป็นกราฟที่สมบูรณ์แบบในวงกว้างกว่าที่รวมกราฟการเรียงสับเปลี่ยนไว้เป็นกรณีพิเศษ^{[ 46 ]}ในกราฟคอร์ดัลสามารถค้นหาคลิกสูงสุดได้โดยการเรียงลำดับจุดยอดตามลำดับการกำจัด และตรวจสอบบริเวณใกล้เคียง คลิก ของแต่ละจุดยอดตามลำดับนี้^{[ 47 ]}

ในบางกรณี อัลกอริทึมเหล่านี้สามารถขยายไปยังกราฟประเภทอื่นที่ไม่สมบูรณ์แบบได้เช่นกัน ตัวอย่างเช่น ในกราฟวงกลมบริเวณใกล้เคียงของแต่ละจุดยอดเป็นกราฟการเรียงสับเปลี่ยน ดังนั้นสามารถค้นหาคลิกสูงสุดในกราฟวงกลมได้โดยการใช้อัลกอริทึมกราฟการเรียงสับเปลี่ยนกับบริเวณใกล้เคียงแต่ละแห่ง^{[ 48 ]}ในทำนองเดียวกัน ในกราฟดิสก์หน่วย (ที่มีการแสดงทางเรขาคณิตที่ทราบ) มีอัลกอริทึมเวลาพหุนามสำหรับคลิกสูงสุดโดยอาศัยการใช้อัลกอริทึมสำหรับส่วนเติมเต็มของกราฟสองส่วนกับบริเวณใกล้เคียงร่วมกันของคู่จุดยอด^{[ 49 ]}

ปัญหาเชิงอัลกอริทึมของการค้นหาคลิกสูงสุดในกราฟสุ่มที่ดึงมาจากแบบจำลอง Erdős–Rényi (ซึ่งแต่ละขอบปรากฏด้วยความน่าจะเป็น1/2โดยไม่ขึ้นกับขอบอื่นๆ) ได้รับการเสนอแนะโดยKarp (1976)เนื่องจากคลิกสูงสุดในกราฟสุ่มมีขนาดลอการิทึมด้วยความน่าจะเป็นสูง จึงสามารถค้นหาได้ด้วยการค้นหาแบบ brute force ในเวลาที่คาดหวัง2 ^{O (log 2 n )}ซึ่งเป็นขอบเขตเวลาแบบกึ่งพหุนาม^{[ 50 ]}แม้ว่าจำนวนคลิกของกราฟดังกล่าวโดยทั่วไปจะใกล้เคียงกับ2 log ₂ n มาก แต่ อัลกอริทึมแบบโลภอย่างง่ายรวมถึงเทคนิคการประมาณค่าแบบสุ่มที่ซับซ้อนกว่าจะพบคลิกที่มีขนาดlog ₂ nเพียงครึ่งเดียวเท่านั้น จำนวนคลิกสูงสุดในกราฟดังกล่าวมีความน่าจะเป็นสูงแบบเลขชี้กำลังในlog ² nซึ่งป้องกันไม่ให้วิธีการที่แสดงรายการคลิกสูงสุดทั้งหมดทำงานในเวลาพหุนาม^{[ 51 ]}เนื่องจากความยากลำบากของปัญหานี้ ผู้เขียนหลายคนจึงได้ศึกษา ปัญหา คลิกแบบฝังซึ่งเป็นปัญหาคลิกบนกราฟสุ่มที่ได้รับการเสริมด้วยการเพิ่มคลิกขนาดใหญ่^{[ 52 ]}ในขณะที่วิธีการสเปกตรัม^{[ 53 ]}และการเขียนโปรแกรมแบบกึ่งกำหนด^{[ 54 ]}สามารถตรวจจับคลิกที่ซ่อนอยู่ที่มีขนาดΩ( √ n )ได้ แต่ปัจจุบันยังไม่มีอัลกอริทึมแบบพหุนามเวลาที่สามารถตรวจจับคลิกที่มีขนาดo ( √ n ) ได้ (แสดงโดยใช้สัญกรณ์ little-o ) ^{[ 55 ]}

ผู้เขียนหลายท่านได้พิจารณาอัลกอริธึมการประมาณค่าที่พยายามค้นหาคลิกหรือเซตอิสระซึ่งแม้จะไม่ใช่ค่าสูงสุด แต่ก็มีขนาดใกล้เคียงกับค่าสูงสุดมากที่สุดเท่าที่จะหาได้ในเวลาพหุนาม แม้ว่างานส่วนใหญ่จะมุ่งเน้นไปที่เซตอิสระในกราฟแบบเบาบาง ซึ่งเป็นกรณีที่ไม่สมเหตุสมผลสำหรับปัญหาคลิกเสริม แต่ก็มีงานเกี่ยวกับอัลกอริธึมการประมาณค่าที่ไม่ใช้สมมติฐานความเบาบางดังกล่าวด้วย^{[ 56 ]}

Feige (2004)อธิบายอัลกอริทึมเวลาพหุนามที่ค้นหาคลิกขนาดΩ((log  n /log log  n ) ² )ในกราฟใดๆ ที่มีจำนวนคลิกΩ( n /log ^k n )สำหรับค่าคงที่k ใดๆ โดยการใช้อัลกอริทึมนี้เมื่อจำนวนคลิกของกราฟอินพุตที่กำหนดอยู่ระหว่างn /log  nและn /log ³ nเปลี่ยนไปใช้อัลกอริทึมอื่นของBoppana & Halldórsson (1992)สำหรับกราฟที่มีจำนวนคลิกสูงกว่า และเลือกคลิกสองจุดยอดหากทั้งสองอัลกอริทึมล้มเหลวในการค้นหาอะไรFeigeได้นำเสนออัลกอริทึมประมาณค่าที่ค้นหาคลิกที่มีจำนวนจุดยอดภายในปัจจัยO( n (log log  n ) ² /log ³ n )ของค่าสูงสุด แม้ว่าอัตราส่วนการประมาณค่าของอัลกอริทึมนี้จะอ่อนแอ แต่ก็เป็นอัลกอริทึมที่ดีที่สุดที่รู้จักในปัจจุบัน^{[ 57 ]}ผลลัพธ์เกี่ยวกับความยากของการประมาณค่าที่อธิบายไว้ด้านล่างแสดงให้เห็นว่าไม่มีอัลกอริทึมการประมาณค่าใดที่มีอัตราส่วนการประมาณค่าน้อยกว่าเชิงเส้นอย่างมีนัยสำคัญ

ปัญหาการตัดสินใจคลิกเป็นปัญหาNP-completeเป็นหนึ่งใน21 ปัญหาดั้งเดิมของ Richard Karpที่แสดงให้เห็นว่าเป็น NP-complete ในบทความปี 1972 ของเขาเรื่อง "Reducibility Among Combinatorial Problems" ^{[ 59 ]} ปัญหานี้ยังถูกกล่าวถึงในบทความของStephen Cook ที่แนะนำทฤษฎีของปัญหา NP-complete ^{[ 60 ]}เนื่องจากความยากของปัญหาการตัดสินใจ ปัญหาการค้นหาคลิกสูงสุดจึงเป็น NP-hard เช่นกัน หากสามารถแก้ปัญหานี้ได้ ก็จะสามารถแก้ปัญหาการตัดสินใจได้เช่นกัน โดยการเปรียบเทียบขนาดของคลิกสูงสุดกับพารามิเตอร์ขนาดที่กำหนดเป็นอินพุตในปัญหาการตัดสินใจ

การพิสูจน์ความสมบูรณ์ของ NP ของ Karp เป็นการลดแบบ many-oneจากปัญหาความพึงพอใจของ Booleanโดยอธิบายวิธีการแปลสูตร Boolean ในรูปแบบปกติแบบเชื่อมโยง (CNF) ไปเป็นอินสแตนซ์ที่เทียบเท่าของปัญหาคลิกสูงสุด^{[ 61 ]}ในทางกลับกัน ความพึงพอใจได้รับการพิสูจน์ว่าเป็น NP-complete ในทฤษฎีบท Cook–Levinจากสูตร CNF ที่กำหนด Karp สร้างกราฟที่มีจุดยอดสำหรับทุกคู่( v , c )โดยที่vเป็นตัวแปรหรือนิเสธของมัน และcเป็นข้อความในสูตรที่มีvจุดยอดสองจุดนี้จะเชื่อมต่อกันด้วยขอบหากพวกมันแสดงถึงการกำหนดค่าตัวแปรที่เข้ากันได้สำหรับข้อความที่แตกต่างกัน นั่นคือ มีขอบจาก( v , c )ไปยัง( u , d )เมื่อใดก็ตามที่c  ≠  dและuและvไม่ใช่นิเสธของกันและกัน ถ้าkแทนจำนวนข้อความในสูตร CNF แล้ว กลุ่มคลิก kจุดยอดในกราฟนี้แสดงถึงวิธีที่สอดคล้องกันในการกำหนดค่าความจริงให้กับตัวแปรบางตัวเพื่อให้เป็นไปตามสูตร ดังนั้น สูตรจึงสามารถหาคำตอบได้ก็ต่อเมื่อ มีกลุ่มคลิก kจุดยอดอยู่^{[ 59 ]}

ปัญหา NP-complete บางอย่าง (เช่นปัญหาพนักงานขายเดินทางในกราฟระนาบ ) อาจแก้ได้ในเวลาที่เป็นเลขชี้กำลังในฟังก์ชันย่อยเชิงเส้นของพารามิเตอร์ขนาดอินพุตnซึ่งเร็วกว่าการค้นหาแบบใช้กำลังทั้งหมดอย่างมีนัยสำคัญ^{[ 62 ]}อย่างไรก็ตาม ไม่น่าเป็นไปได้ที่ขอบเขตเวลาย่อยเลขชี้กำลังดังกล่าวจะเป็นไปได้สำหรับปัญหาคลิกในกราฟใดๆ เนื่องจากจะหมายถึงขอบเขตย่อยเลขชี้กำลังที่คล้ายกันสำหรับปัญหา NP-complete มาตรฐานอื่นๆ อีกมากมาย^{[ 63 ]}

ความยากลำบากในการคำนวณของปัญหาคลิกทำให้มีการนำไปใช้เพื่อพิสูจน์ขอบเขตล่างหลายประการในความซับซ้อนของวงจรการมีอยู่ของคลิกที่มีขนาดที่กำหนดเป็นคุณสมบัติของกราฟแบบโมโนโทนหมายความว่า ถ้าคลิกมีอยู่ในกราฟที่กำหนด คลิกนั้นก็จะมีอยู่ในซูเปอร์กราฟ ใดๆ ด้วย เนื่องจากคุณสมบัตินี้เป็นแบบโมโนโทน จึงต้องมีวงจรแบบโมโนโทน โดยใช้เฉพาะเกต ANDและเกต ORเพื่อแก้ปัญหาการตัดสินใจของคลิกสำหรับขนาดคลิกที่กำหนดไว้ อย่างไรก็ตาม ขนาดของวงจรเหล่านี้สามารถพิสูจน์ได้ว่าเป็นฟังก์ชันซูเปอร์พหุนามของจำนวนจุดยอดและขนาดของคลิก ซึ่งเป็นเลขชี้กำลังของรากที่สามของจำนวนจุดยอด^{[ 64 ]}แม้ว่า จะอนุญาตให้ใช้ เกต NOT จำนวนเล็กน้อย ความซับซ้อนก็ยังคงเป็นซูเปอร์พหุนาม^{[ 65 ]}นอกจากนี้ ความลึกของวงจรแบบโมโนโทนสำหรับปัญหาคลิกโดยใช้เกตที่มีfan-in ที่จำกัด จะต้องมีอย่างน้อยพหุนามในขนาดของคลิก^{[ 66 ]}

ความซับซ้อนของต้นไม้ตัดสินใจ (แบบกำหนด) ในการกำหนดคุณสมบัติของกราฟคือจำนวนคำถามในรูปแบบ "มีขอบระหว่างจุดยอดuและจุดยอดvหรือไม่?" ที่ต้องตอบในกรณีที่เลวร้ายที่สุดเพื่อกำหนดว่ากราฟมีคุณสมบัติเฉพาะหรือไม่ นั่นคือ เป็นความสูงขั้นต่ำของต้นไม้ตัดสินใจ แบบบูลีน สำหรับปัญหา มี คำถามที่เป็นไปได้ที่จะถาม n ( n  − 1)/2 ข้อดังนั้น คุณสมบัติของกราฟใดๆ ก็สามารถกำหนดได้ด้วยคำถามอย่างมากที่สุดn ( n  − 1)/2ข้อ นอกจากนี้ยังสามารถกำหนดความซับซ้อนของต้นไม้ตัดสินใจแบบสุ่มและควอนตัมของคุณสมบัติได้ ซึ่งเป็นจำนวนคำถามที่คาดหวัง (สำหรับอินพุตกรณีที่เลวร้ายที่สุด) ที่อัลกอริทึมแบบสุ่มหรือควอนตัมต้องตอบเพื่อให้สามารถกำหนดได้อย่างถูกต้องว่ากราฟที่กำหนดมีคุณสมบัติหรือไม่^{[ 67 ]}

เนื่องจากคุณสมบัติของการมีคลิกเป็นแบบโมโนโทน จึงครอบคลุมโดยสมมติฐาน Aanderaa–Karp–Rosenbergซึ่งระบุว่าความซับซ้อนของต้นไม้ตัดสินใจแบบกำหนดในการกำหนดคุณสมบัติของกราฟโมโนโทนที่ไม่ธรรมดาใดๆ นั้นเท่ากับn ( n  − 1)/2 พอดี สำหรับคุณสมบัติของกราฟโมโนโทนใดๆ สมมติฐานนี้ยังไม่ได้รับการพิสูจน์ อย่างไรก็ตาม สำหรับต้นไม้ตัดสินใจแบบกำหนด และสำหรับk ใดๆ ในช่วง2 ≤ k ≤ nคุณสมบัติของการมีk-คลิกได้รับการแสดงให้เห็นว่ามีความซับซ้อนของต้นไม้ตัดสินใจเท่ากับn ( n  − 1)/2 พอดีโดยBollobás (1976)ต้นไม้ตัดสินใจแบบกำหนดยังต้องการขนาดเลขชี้กำลังเพื่อตรวจจับคลิก หรือขนาดพหุนามขนาดใหญ่เพื่อตรวจจับคลิกที่มีขนาดจำกัด^{[ 68 ]}

ข้อสันนิษฐานของ Aanderaa–Karp–Rosenberg ยังระบุอีกว่าความซับซ้อนของต้นไม้ตัดสินใจแบบสุ่มของฟังก์ชันโมโนโทนที่ไม่ธรรมดาคือΘ( n ² )ข้อสันนิษฐานนี้ยังไม่ได้รับการพิสูจน์ แต่ได้รับการแก้ไขสำหรับคุณสมบัติของการมี คลิก kสำหรับ2 ≤ k ≤ nคุณสมบัตินี้เป็นที่ทราบกันว่ามีความซับซ้อนของต้นไม้ตัดสินใจแบบสุ่มΘ( n 2 ⁾ [ ^{69 ] สำหรับ}ต้นไม้ตัดสินใจควอนตัม ขอบล่างที่ทราบดีที่สุดคือΩ( n )แต่ยังไม่มีอัลกอริทึมการจับคู่ใด ๆ ที่ทราบสำหรับกรณีของk ≥ 3 ^{[ 70 ]}

ความซับซ้อนแบบพารามิเตอร์คือ การศึกษา เชิงทฤษฎีความซับซ้อนของปัญหาที่มีพารามิเตอร์จำนวนเต็มขนาดเล็กk ตามธรรมชาติ และปัญหาจะยากขึ้นเมื่อkเพิ่มขึ้น เช่น การค้นหาk-คลิกในกราฟ ปัญหาจะเรียกว่าสามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ หากมีอัลกอริทึมสำหรับการแก้ปัญหาบนอินพุตขนาดnและฟังก์ชันfโดยที่อัลกอริทึมทำงานในเวลาf ( k )  n ^{O (1) นั่นคือ สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ หากสามารถแก้ไขได้ในเวลาพหุ นาม}สำหรับค่าk คงที่ใดๆ และยิ่งไปกว่านั้น เลขชี้กำลังของพหุนามไม่ขึ้นอยู่กับk [ ^{71 ]}

สำหรับการค้นหาคลิกที่มีk จุดยอด อัลกอริทึมการค้นหาแบบบรูทฟอร์ซมีเวลาทำงาน O( n ^k k ² )เนื่องจากเลขชี้กำลังของnขึ้นอยู่กับkอัลกอริทึมนี้จึงไม่สามารถจัดการได้ด้วยพารามิเตอร์คงที่ แม้ว่าจะสามารถปรับปรุงได้ด้วยการคูณเมทริกซ์ อย่างรวดเร็ว แต่เวลาทำงานก็ยังคงมีเลขชี้กำลังที่เป็นเชิงเส้นในkดังนั้น แม้ว่าเวลาทำงานของอัลกอริทึมที่รู้จักสำหรับปัญหาคลิกจะเป็นพหุนามสำหรับk ที่กำหนดไว้ใดๆ อัลกอริทึมเหล่านี้ก็ไม่เพียงพอสำหรับการจัดการด้วยพารามิเตอร์คงที่Downey & Fellows (1995)ได้กำหนดลำดับชั้นของปัญหาที่มีพารามิเตอร์ ลำดับชั้น W ซึ่งพวกเขาสันนิษฐานว่าไม่มีอัลกอริทึมที่สามารถจัดการได้ด้วยพารามิเตอร์คงที่ พวกเขาพิสูจน์ว่าเซตอิสระ (หรือเทียบเท่ากับคลิก) ยากสำหรับระดับแรกของลำดับชั้นนี้W[1]ดังนั้น ตามการสันนิษฐานของพวกเขา คลิกจึงไม่มีอัลกอริทึมที่สามารถจัดการได้ด้วยพารามิเตอร์คงที่ ยิ่งไปกว่านั้น ผลลัพธ์นี้ยังเป็นพื้นฐานสำหรับการพิสูจน์ความยากแบบ W[1] ของปัญหาอื่นๆ อีกมากมาย และด้วยเหตุนี้จึงทำหน้าที่เป็นแบบจำลองของทฤษฎีบท Cook–Levinสำหรับความซับซ้อนแบบพารามิเตอร์^{[ 72 ]}

Chen et al. (2006)แสดงให้เห็นว่าการค้นหา คลิก kจุดยอดไม่สามารถทำได้ในเวลาn ^{o ( k )}เว้นแต่สมมติฐานเวลาเลขชี้กำลังจะล้มเหลว อีกครั้ง นี่เป็นหลักฐานว่าไม่มีอัลกอริทึมที่จัดการได้ด้วยพารามิเตอร์คงที่ที่เป็นไปได้^{[ 73 ]}

แม้ว่าปัญหาการแสดงรายการคลิกสูงสุดหรือการค้นหาคลิกสูงสุดไม่น่าจะสามารถแก้ไขได้ด้วยพารามิเตอร์คงที่โดยใช้พารามิเตอร์kแต่ก็อาจสามารถแก้ไขได้ด้วยพารามิเตอร์คงที่สำหรับพารามิเตอร์อื่นๆ ของความซับซ้อนของอินสแตนซ์ ตัวอย่างเช่น เป็นที่ทราบกันดีว่าทั้งสองปัญหาสามารถแก้ไขได้ด้วยพารามิเตอร์คงที่เมื่อกำหนดพารามิเตอร์โดยความเสื่อมของกราฟอินพุต^{[ 33 ]}

ผลลัพธ์ที่ไม่ชัดเจนซึ่งบ่งชี้ว่าปัญหาคลิกอาจยากต่อการประมาณค่าเป็นที่ทราบกันมานานแล้วGarey & Johnson (1978)สังเกตว่า เนื่องจากจำนวนคลิกมีค่าเป็นจำนวนเต็มขนาดเล็กและคำนวณได้ยากในระดับ NP จึงไม่สามารถมีวิธีการประมาณค่าแบบใช้เวลาพหุนามอย่างสมบูรณ์ได้เว้นแต่ว่า P = NP หากมีการประมาณค่าที่แม่นยำเกินไป การปัดเศษค่าให้เป็นจำนวนเต็มจะให้จำนวนคลิกที่แน่นอน อย่างไรก็ตาม ความรู้เพิ่มเติมมีน้อยมากจนกระทั่งต้นทศวรรษ 1990 เมื่อผู้เขียนหลายคนเริ่มเชื่อมโยงระหว่างการประมาณค่าคลิกสูงสุดกับการพิสูจน์ที่ตรวจสอบได้ทางความน่าจะเป็นพวกเขาใช้การเชื่อมโยงเหล่านี้เพื่อพิสูจน์ความยากของผลลัพธ์การประมาณค่าสำหรับปัญหาคลิกสูงสุด^{[ 74 ]} หลังจากการปรับปรุงผลลัพธ์เหล่านี้หลายครั้ง ปัจจุบันเป็นที่ทราบกันแล้วว่า สำหรับจำนวนจริงε  > 0 ทุกตัว จะไม่มีอัลกอริทึมเวลาพหุนามใดที่สามารถประมาณคลิกสูงสุดได้ดีกว่าO ( n ^{1 −  ε} )เว้นแต่ว่าP = NP ^{[ 75 ]}

แนวคิดคร่าวๆ ของผลลัพธ์ที่ไม่สามารถประมาณค่าได้เหล่านี้คือการสร้างกราฟที่แสดงถึงระบบการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็นสำหรับปัญหา NP-complete เช่น ปัญหาความพึงพอใจของบูลีน ในระบบการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็น การพิสูจน์จะถูกแสดงเป็นลำดับของบิต อินสแตนซ์ของปัญหาความพึงพอใจควรมีการพิสูจน์ที่ถูกต้องก็ต่อเมื่อสามารถพึงพอใจได้ การพิสูจน์จะถูกตรวจสอบโดยอัลกอริทึมที่หลังจากคำนวณเวลาพหุนามบนอินพุตของปัญหาความพึงพอใจแล้ว จะเลือกตรวจสอบตำแหน่งที่เลือกแบบสุ่มจำนวนเล็กน้อยของสตริงการพิสูจน์ ขึ้นอยู่กับค่าที่พบในตัวอย่างบิตนั้น ผู้ตรวจสอบจะยอมรับหรือปฏิเสธการพิสูจน์โดยไม่ต้องดูบิตที่เหลือ ไม่อนุญาตให้เกิดผลลบเท็จ: การพิสูจน์ที่ถูกต้องจะต้องได้รับการยอมรับเสมอ อย่างไรก็ตาม การพิสูจน์ที่ไม่ถูกต้องอาจถูกยอมรับโดยไม่ได้ตั้งใจในบางครั้ง สำหรับการพิสูจน์ที่ไม่ถูกต้องทุกรายการ ความน่าจะเป็นที่ผู้ตรวจสอบจะยอมรับจะต้องต่ำ^{[ 76 ]}

ในการแปลงระบบพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็นประเภทนี้ให้เป็นปัญหาคลิก (clique problem) เราต้องสร้างกราฟที่มีจุดยอดสำหรับแต่ละลำดับการตรวจสอบที่ยอมรับได้ที่เป็นไปได้ กล่าวคือ จุดยอดถูกกำหนดโดยการเลือกแบบสุ่มที่เป็นไปได้ของชุดตำแหน่งที่จะตรวจสอบ และโดยค่าบิตสำหรับตำแหน่งเหล่านั้นที่จะทำให้ตัวตรวจสอบยอมรับการพิสูจน์ สามารถแทนได้ด้วยคำบางส่วนที่มีค่า 0 หรือ 1 ในแต่ละตำแหน่งที่ตรวจสอบ และอักขระตัวแทน (wildcard character ) ในแต่ละตำแหน่งที่เหลือ ในกราฟนี้ จุดยอดสองจุดจะอยู่ติดกัน หากลำดับการตรวจสอบที่ยอมรับได้สองลำดับที่สอดคล้องกันเห็นค่าบิตเดียวกันในทุกตำแหน่งที่ทั้งสองตรวจสอบ แต่ละสตริงการพิสูจน์ (ที่ถูกต้องหรือไม่ถูกต้อง) สอดคล้องกับคลิก ซึ่งเป็นชุดของลำดับการตรวจสอบที่ยอมรับได้ที่เห็นสตริงการพิสูจน์นั้น และคลิกสูงสุดทั้งหมดเกิดขึ้นในลักษณะนี้ คลิกเหล่านี้จะมีขนาดใหญ่ก็ต่อเมื่อมันสอดคล้องกับสตริงการพิสูจน์ที่ตัวตรวจสอบจำนวนมากยอมรับ หากอินสแตนซ์ความพึงพอใจดั้งเดิมมีความพึงพอใจ มันจะมีสตริงพิสูจน์ที่ถูกต้อง ซึ่งได้รับการยอมรับจากการทำงานทั้งหมดของตัวตรวจสอบ และสตริงนี้จะสอดคล้องกับคลิกขนาดใหญ่ในกราฟ อย่างไรก็ตาม หากอินสแตนซ์ดั้งเดิมไม่มีความพึงพอใจ สตริงพิสูจน์ทั้งหมดจะไม่ถูกต้อง สตริงพิสูจน์แต่ละสตริงจะมีเพียงจำนวนเล็กน้อยของการทำงานตัวตรวจสอบที่ยอมรับผิดพลาด และคลิกทั้งหมดจะมีขนาดเล็ก ดังนั้น หากสามารถแยกแยะระหว่างกราฟที่มีคลิกขนาดใหญ่และกราฟที่คลิกทั้งหมดมีขนาดเล็กได้ในเวลาพหุนาม หรือหากสามารถประมาณปัญหาคลิกได้อย่างแม่นยำ การนำการประมาณนี้ไปใช้กับกราฟที่สร้างขึ้นจากอินสแตนซ์ความพึงพอใจจะช่วยให้สามารถแยกแยะอินสแตนซ์ที่มีความพึงพอใจออกจากอินสแตนซ์ที่ไม่มีความพึงพอใจได้ อย่างไรก็ตาม สิ่งนี้เป็นไปไม่ได้เว้นแต่ P = NP ^{[ 76 ]}