שלום לכולם.
אשמח אם מישהו יוכל לעזור לי איך מראים את זה
אני יודע שבשביל להגיע מקליק ל-VC צריך לעבוד על הגרף המשלים אבל איך אני ממשיך מכאן?
עלייך למצוא אלגוריתם קירוב לבעיית הקליק בהנחה שבגרף המשלים (מעלימים את כל הקשתות ומוסיפים את כל הקשתות שלא היו קיימות - בדיוק כמו ברדוקצייה מבעיית הקליק ל VERTEX COVER ) גודל הקבוצה המכסה הוא מקסימום שליש ממספר הצמתים. מה יהיה הקירוב שהתקבל?