קלט: קבוצה U, אוסף \F 1, ,F m\ של m תתי-קבוצות של U, שכל אחת מהן בגודל 3, ומספר טבעי k. שאלה: האם קיימת קבוצה…

קלט: קבוצה $U$, אוסף $\{F_1,\ldots,F_m\}$ של $m$ תתי-קבוצות של $U$, שכל אחת מהן בגודל $3$, ומספר טבעי $k$.

שאלה: האם קיימת קבוצה $S\subseteq U$, בגודל $|S|=k$, המקיימת

$$S\cap F_i\ne\varnothing \qquad \text{לכל }1\le i\le m?$$

1. הוכיחו כי הבעיה $NP$-שלמה.
2. נסחו את גרסת האופטימיזציה והציעו אלגוריתם פולינומי בעל יחס קירוב $3$.
3. הוכיחו כי האלגוריתם המוצע אינו משיג יחס קירוב $2.9$.