היפרגרף 3-אחיד הוא זוג H=(V,E), כאשר V קבוצת קודקודים ו-E אוסף תת־קבוצות של V, כל אחת בגודל 3. כל קבוצה כזו הי…

היפרגרף $3$-אחיד הוא זוג $H=(V,E)$, כאשר $V$ קבוצת קודקודים ו-$E$ אוסף תת־קבוצות של $V$, כל אחת בגודל $3$. כל קבוצה כזו היא היפר־קשת.

כיסוי קודקודים של $H$ הוא $S\subseteq V$ כך שבכל היפר־קשת יש קודקוד מ-$S$; כלומר,

$$e\cap S\ne\varnothing \qquad\text{לכל }e\in E.$$

1. תהא $3H\text{-}VC$ שפת הזוגות $(H,k)$ של היפרגרף $3$-אחיד $H$ ומספר טבעי $k$, שעבורם קיים ב-$H$ כיסוי קודקודים בגודל $k$. הוכיחו כי $3H\text{-}VC$ היא $NP$-קשה.
2. בבעיית המינימיזציה הקלט הוא היפרגרף $3$-אחיד והמטרה היא למצוא כיסוי קטן ככל האפשר. הוכיחו כי קיים אלגוריתם פולינומי בעל יחס קירוב $3$.