مسئله پوشش گروهک

در نظریهٔ پیچیدگی محاسباتی، پیدا کردن یک پوشش گروهک کمینه، یک مسئله NP-کامل نظری گراف است. این مسئله یکی از۲۱ مسئله اصلی ریچارد کاپ است که در آن NP-کامل را در مقاله‌اش "کاهش پذیری درمیان مسائل ترکیبی "در سال ۱۹۷۲ نشان داده بود.

مسئله پوشش گروهک(همچنین بعضی اوقات به عنوان دسته‌بندی به گروهک‌ها نامیده می‌شود) مسئله تصمیم‌گیری در مورد راس‌هایی از یک گراف هستند که خواه می‌توانند به Kگروهک دسته‌بندی شوند یا نه. بایک دسته‌بندی داده شده از رئوس به K مجموعه، آن دسته‌بندی می‌تواند در زمان چندجمله‌ای که هرمجموعه یک گروهک را تشکیل می‌دهد، رسیدگی شود، بنابراین این مسئله درNPاست.

کامل بودن NP پوشش گروهک‌ها، به دنبال کاهش از رنگ‌پذیری K گراف می‌آید. برای فهمیدن این موضوع، ابتدا یک نمونه G از گراف ''K'' رنگ پذیری را به گراف G مکمل اش تبدیل کنید. یک دسته بندی از Gبه Kگروهک، سپس با پیدا کردن یک دسته‌بندی ازرئوس G به K مجموعهٔ مستقل ارتباط دارد، هرکدام از این مجموعه‌ها می‌تواند یک رنگ بپذیرند تا یک K رنگ‌پذیری را حاصل کنند.

مسئلهٔ پوشش لبهٔ گروهک مرتبط، مجموعه‌ای از گروهک‌ها را که شامل همهٔ لبه‌هایی از یک گراف داده شده‌است را در نظر می‌گیرد. این مسئله همچنین NP کامل است.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Clique cover problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۱ تیر ۱۳۹۱.

• Karp, Richard (۱۹۷۲), "Reducibility Among Combinatorial Problems" (PDF), in Miller, R. E.; Thatcher, J. W. (eds.), Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, pp. ۸۵–۱۰۳, archived from the original (PDF) on 29 June 2011, retrieved 2008-08-29
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg

.194.