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

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

הבעיה נכללת ב21 הבעיות ה-NP שלמות של קארפ.

תיאור הבעיה

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

קבוצת הקודקודים {1,3,5,6} וכן הקבוצה {1,2,4} מהוות, כל אחת, כיסוי קודקודים של גרף זה.

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

הגדרת הבעיה

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

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

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

עבור כיסוי בקודקודים C ושידוך M כלשהם, כל קשת $e\in M$ חייבת לגעת לפחות באחד מן הקודקודים בכיסוי, וכל שתי קשתות שונות ב M לא יכולות לגעת באותו קודקוד מ C ולכן מקבלים ש $|M|\leq |C|$. זה גורר שגודל הכיסוי המינימלי בגרף הוא לכל הפחות גודל השידוך מקסימום בגרף. משפט קוניג (König's theorem) אומר שבגרף דו צדדי (סופי) גודל הכיסוי המינימלי שווה לגודל שידוך מקסימום, שידוך מקסימום שייך למחלקת סיבוכיות P - בעיות שניתנות לפתרון בזמן יעיל, ולכן ניתן למצוא את הכיסוי המינימלי בגרף דו צדדי (Bipartite) בזמן פולונומיאלי - זמן יעיל.

מציאת קירוב

אפשר למצוא קירוב על ידי לקיחה שוב ושוב שתי נקודות קצה ביחס לכיסוי הקודקודים, ואז להסיר אותן זמנית מהגרף. לאחר מכן, מוצאים $M$ - התאמה מקסימלית בעזרת "אלגוריתם חמדן", ולבנות את $C$ - כיסוי קודקוד שמורכב מכל נקודות הקצה של הקצוות. באיור הבא מתוארים - $M$ התאמה מקסימלית מסומנת באדום, ואת $C$ כיסוי הקודקודים המסומן בכחול.

סט $C$ של כיסוי הקודקודים נבנה בדרך זו: נניח שקצה קשת $e$ אינו מכוסה על ידי $C$; אז $M\cup \{e\}$ הוא התאמה וגם $e\not \in M$, זו סתירה להנחה כי $M$ הוא מקסימלי. כיסוי אופטימלי מכיל נקודות קצה לפחות אחד מכל קצה ב-$M$; בסך הכל, הסט $C$ הוא לכל היותר גדול פי 2 מכיסוי הקודקודים האופטימלי, וזהו הקירוב הטוב ביותר הידוע כיום. אלגוריתם זה התגלה על ידי Fanica Gavril ו - Mihalis Yannakakis.

פסאודו קוד

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

פסאודו קוד לאלגוריתם קירוב הנ"ל:

APPROXIMATION-VERTEX-COVER(G):
C = ∅
E'= G.E

while E'≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v

return C

ראו גם

• סיבוכיות זמן

קישורים חיצוניים

מדיה וקבצים בנושא בעיית כיסוי קודקודים בוויקישיתוף