בעיית כיסוי קודקודים

מתוך ויקיפדיה, האנציקלופדיה החופשית

במדעי המחשב, בעיית כיסוי הקודקודים היא בעיה NP-שלמה בתורת הסיבוכיות.

כיסוי בתורת הגרפים משמעותו מציאת קבוצת עצמים שאיחודם הוא כל הגרף. כיסוי קודקודים הוא כיסוי הגרף באמצעות קבוצת קודקודים, כל אחד עם הקשתות שיוצאות ממנו, כך שזה יכסה את כל הקשתות של הגרף. כיסוי קשתות זה כיסוי כל קודקודי הגרף באמצעות הקשתות, כל אחת והקודקודים אותם הוא מחבר. כיסויים קשורים קשר הדוק למושגי השידוך והקבוצה הבלתי תלויה שבתורת הגרפים.

בעיית כיסוי הקודקודים היא זו: האם, בהינתן גרף נתון ומספר טבעי , קיים לגרף כיסוי קודקודים שמכיל לכל היותר צמתים? (השאלה האם קיים כיסוי קודקודים מגודל כלשהו היא טריוויאלית, כי ניתן תמיד לבחור בתור כיסוי את כל קודקודי הגרף).

ניתן להראות כי הבעיה היא NP-שלמה על ידי רדוקציה מבעיית SAT.

הבעיה של מציאת כיסוי קודקודים מגודל מינימלי גם היא NP-שלמה, אך קיים לה אלגוריתם קירוב כפלי פשוט: מוצאים שידוך מקסימלי בגרף ולוקחים את כל צמתיו. קל להראות כי בצורה זו הכיסוי שנקבל לא יהיה גדול יותר מאשר פי 2 הכיסוי האופטימלי.