כל מה שרצית לדעת על בעיית כיסוי קודקודים:
כיסוי בתורת הגרפים משמעותו מציאת קבוצת עצמים שאיחודם הוא כל הגרף.
כיסוי קודקודים הוא כיסוי הגרף באמצעות קבוצת קודקודים, כך שכל קשת בגרף נוגעת לפחות באחד מקודקודים אלו.
כיסוי קשתות הוא כיסוי כל קודקודי הגרף באמצעות הקשתות, כל אחת והקודקודים אותם היא מחברת.
כיסויים קשורים קשר הדוק למושגי השידוך והקבוצה הבלתי תלויה שבתורת הגרפים.
בעיית כיסוי הקודקודים היא זו: האם, בהינתן גרף נתון ומספר טבעי , קיים לגרף כיסוי קודקודים שמכיל לכל היותר צמתים? (השאלה האם קיים כיסוי קודקודים מגודל כלשהו היא טריוויאלית, כי ניתן תמיד לבחור בתור כיסוי את כל קודקודי הגרף).
ניתן להראות כי הבעיה היא NP-שלמה על ידי רדוקציה מבעיית SAT.
הבעיה של מציאת כיסוי קודקודים מגודל מינימלי גם היא NP-שלמה, אך קיים לה אלגוריתם קירוב כפלי פשוט: מוצאים שידוך מקסימלי בגרף ולוקחים את כל צמתיו.
קל להראות כי בצורה זו הכיסוי שנקבל לא יהיה גדול יותר מאשר פי 2 הכיסוי האופטימלי.
עבור כיסוי בקודקודים C ושידוך M כלשהם, כל קשת חייבת לגעת לפחות באחד מן הקודקודים בכיסוי, וכל שתי קשתות שונות ב M לא יכולות לגעת באותו קודקוד מ C ולכן מקבלים ש .
זה גורר שגודל הכיסוי המינימלי בגרף הוא לכל הפחות גודל השידוך מקסימום בגרף.
משפט קוניג (König's theorem) אומר שבגרף דו צדדי גודל הכיסוי המינימלי שווה לגודל שידוך מקסימום, ולכן ניתן למצוא את הכיסוי המינימלי בגרף דו צדדי (Bipartite) בזמן פולינומי.