בבעיית המינימיזציה של כיסוי קדקודים (VC) הקלט הוא גרף (לא מכוון) והפלט הנדרש הוא קבוצת קדקודים בגודל מינימלי כ…

בבעיית המינימיזציה של כיסוי קדקודים (VC) הקלט הוא גרף (לא מכוון) והפלט הנדרש הוא קבוצת קדקודים בגודל מינימלי כך שמכל קשת בגרף לפחות אחד הקדקודים של הקשת שייך לקבוצה. נציע את אלגוריתם הקירוב הבא לבעיה: על קלט <G = (V, E)> נאתחל S = Ø . כל עוד $E \ne$ Ø : אם קיימת בגרף (שנשאר עד עכשיו) קליקה בגודל 3: יהיו v1, v2, v3 קדקודים של קליקה כזו. נוסיף ל- S את v1, v2, v3. נוריד מ- E את הקשתות (v1, x) ,(v2, x) ,(v3, x) לכל $x\in V$. אחרת: תהי $(u,v) \in E$ קשת כלשהי. נוסיף ל- S את u ואת v. נוריד מ- E את הקשתות (u, x) -ו (v, x) לכל $x\in V$. נחזיר את S. הרצנו את האלגוריתם הנ"ל על גרף G ובדיוק בחצי מהאיטרציות של האלגוריתם התנאי שקיימת קליקה בגודל 3 התקיים. יהיה Opt גודל כיסוי קדקודים מינימלי של G. מבין הטענות הבאות מה הטענה החזקה ביותר שידועה כנכונה?