ปัญหากลุ่มพรรคพวก

ปัญหากลุ่มพรรคพวก (อังกฤษ: Clique problem) เป็นหนึ่งในปัญหากราฟที่เป็นเอ็นพีบริบูรณ์ (พิสูจน์โดยริชาร์ด คาร์ปในปี 2515) โดยที่กลุ่มพรรคพวก (clique) ภายในกราฟหมายถึงเซ็ตของจุดที่ระหว่างคู่ใดๆมีด้านเชื่อมกัน หรือพูดอีกอย่างก็คือ กลุ่มพรรคพวกเป็น complete induced subgraph ให้ดูตัวอย่างได้ในรูป ซึ่งจะเห็นได้ชัดเจนว่า ระหว่างจุด 1 2 และ 5 มีด้านเชื่อมถึงกันหมด ในกรณีนี้เราเรียกว่าทั้งสามจุดนี้เป็นกลุ่มพรรคพวกที่มีขนาดเท่ากับ 3

ปัญหากลุ่มพรรคพวกคือ ปัญหาที่ตัดสินว่ากราฟที่กำหนดมีกลุ่มพรรคพวกที่มีขนาด ${\displaystyle k}$ หรือไม่ เราสามารถพิสูจน์ได้ไม่ยากนักว่าปัญหานี้อยู่ในเอ็นพี เพราะว่าถ้าเรากำหนดจุดที่อยู่ในกลุ่มพรรคพวกมาให้ เราสามารถตรวจสอบได้ในเวลา ${\displaystyle O(k^{2})}$ ว่าจุดที่กำหนดมาให้เป็นกลุ่มพรรคพวกจริงหรือไม่ เราอาจจะนิยามปัญหานี้ได้อีกแบบในเชิงของ optimization problem ก็คือ ให้หากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟที่กำหนด

ปัญหากลุ่มพรรคพวกเป็นเอ็นพีบริบูรณ์เนื่องมาจากความเป็นเอ็นพีบริบูรณ์ของปัญหาเซตอิสระ เนื่องมาจากว่าถ้ามีกลุ่มพรรคพวกที่มีขนาด k ในกราฟ G จะมีเซตอิสระขนาด k ในกราฟ ${\displaystyle {\bar {G}}}$เสมอ เพราะฉะนั้นเราสามารถเห็นได้อย่างชัดเจนว่าปัญหากลุ่มพรรคพวกกับปัญหาเซตอิสระสามารถ ลดรูป ระหว่างสองปัญหาได้

ขั้นตอนวิธี

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

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

อ้างอิง

• Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0716710455. A1.2: GT19, pg.194.