วิธีแก้ปัญหานี้แบบตรงไปตรงมาก็คือการพิจารณากราฟย่อยทุกรูปแบบของ G ที่ประกอบด้วย k จุด และตรวจสอบว่า กราฟย่อยนั้นเป็นกราฟบริบูรณ์หรือไม่ วิธีนี้ใช้เวลาการทำงานเป็นฟังก์ชันพหุนามกับ n หากเรามองว่า k เป็นค่าคงที่ แต่ในปัญหานี้ k ถูกกำหนดเป็นอินพุตด้วย เพราะฉะนั้นวิธีนี้ใช้เวลานานเกินกว่าจะรับได้หาก n มีค่ามากๆ และ k มีค่าประมาณครึ่งหนึ่งของ n

เราลองมาดูวิธีแก้ปัญหาแบบฮิวริสติกกันบ้าง วิธีฮิวริสติกที่เป็นไปได้แบบหนึ่งก็คือ เริ่มต้นจากกราฟ G มองว่าแต่ละจุดเป็นกลุ่มพรรคพวกที่มีขนาดเท่ากับ 1 เราจะรวมกลุ่มพรรคพวกA และ B เข้าด้วยกันเมื่อมีเส้นเชื่อมระหว่างทุกจุดใน A กับทุกจุดใน B และทำการรวมกลุ่มพรรคพวกที่สามารถรวมกันได้เข้าด้วยกันเรื่อยๆ จนกระทั่งไม่มีกลุ่มพรรคพวกที่สามารถรวมกันได้อีก เราสามารถเห็นได้ชัดเจนว่าด้วยวิธีนี้ เราจะได้ผลลัพธ์เป็นกลุ่มพรรคพวกที่เป็น maximal independent set แต่ไม่จำเป็นว่าจะต้องเป็นกลุ่มพรรคพวกที่ใหญ่ที่สุดบนกราฟ เพราะว่าที่บางขั้นตอนของฮิวริสติกอาจจะทำให้เรารวมกลุ่มสองกลุ่มที่ไม่ควรจะถูกรวมกันในคำตอบที่ดีที่สุด วิธีนี้สามารถทำได้อย่างมีประสิทธิภาพโดยการใช้ขั้นตอนวิธีแบบ union-find