Uderzanie w zestawy z podrodziny

Pozwolić $F$ być rodziną $d$-elementowe podzbiory skończonego wszechświata $U$przedmiotów. Rodzina$H$ z $k$podzbiory elementów $U$, z $1 \le k < d$, jest $(k,d)$- trafienie ustawione od$F$ jeśli dla każdego $V \in F$ istnieje co najmniej jeden zestaw $W \in H$ takie, że $W \subset V$.

Biorąc pod uwagę kolekcję $F$ jak wyżej, $(k,d)$- problemem zestawu uderzającego jest znalezienie najmniejszego$(k,d)$zestaw uderzeniowy $H$ dla $F$.

Kiedy $k = 1$mamy standardowy problem z zestawem uderzeń i istnieje wiele wcześniejszych wyników. Znam sparametryzowane analizy dla przypadku$k = 1$ i $d \le 3$(patrz na przykład Brankovic i Fernau ).

Czy ktoś zna jakiekolwiek wyniki dotyczące złożoności lub twardości przybliżenia $(k,d)$problem z uderzeniem zestawu:

1. $k = 1$ i $d = 4$?
2. $d = 4$ i $1 < k < d$?
3. $1 \le k < d$ i $d$ arbitralny?

Dla stałej $d$ $(k,d)$- Uderzenie zestawu nie jest trudniejsze niż oryginał $d$- zestaw uderzeniowy (tj $k=1$) zarówno ze względu na przybliżenie, jak i sparametryzowaną złożoność. Istnieje prosta redukcja od$kd$-HS do $d$-HS. Na przykład$(U,\mathcal{F},d,k)$ pierwszego problemu, który otrzymujemy $(U',\mathcal{F'},d)$ drugiego, w którym każdy element $e \in U'$ odpowiada $k$podzbiór elementów $U$i każdy zestaw w $\mathcal{F'}$ odpowiada zestawowi w $\mathcal{F}$ w ten sam sposób (tj. mapowanie wszystkich $k$podzbiory elementów $U$ do elementów w $U'$). Od$k$ jest stałą wielkość nowego wystąpienia jest funkcją wielomianową wielkości pierwszego wystąpienia ($O(n^k)$). Zestaw uderzeń dla pierwszego problemu odpowiada zestawowi uderzeń o tej samej liczności dla drugiego problemu i odwrotnie, dlatego redukcja zachowuje przybliżenie.