שאלה | מה ניתן לומר על בעיית המינימיזציה של הכיסוי על ידי קודקודים Cover Vertex?

מה ניתן לומר על בעיית המינימיזציה של הכיסוי על ידי קודקודים Cover Vertex?

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