Interesuje mnie sparametryzowana złożoność problemu, który nazywam d-Dimensional Hitting Set: biorąc pod uwagę przestrzeń zakresu (tj. Układ zestawu / hipergraph) S = (X, R) mający wymiar VC co najwyżej d dodatnia liczba całkowita k, czy X zawiera podzbiór wielkości k, który uderza w każdy zakres w R? Sparametryzowana wersja problemu jest parametryzowana przez k.
Dla jakich wartości d jest problemem d-Dimensional Hitting Set
- w FPT?
- w W [1]?
- W [1] - twardy?
- W [2] - twardy?
To, co wiem, można streścić w następujący sposób:
1-wymiarowy zestaw uderzeń jest w P, a zatem w FPT. Jeśli S ma wymiar 1, nie jest trudno wykazać, że albo istnieje zestaw uderzeń o rozmiarze 2, albo macierz występowania S jest całkowicie zrównoważona. W obu przypadkach możemy znaleźć minimalny zestaw uderzeń w czasie wielomianowym.
4-wymiarowy zestaw uderzeniowy ma twardość W [1]. Dom, Fellows i Rosamond [PDF] udowodnili twardość W [1] dla problemu przebijania prostokątów równoległych do osi w R ^ 2 liniami równoległymi do osi. Można to sformułować jako zestaw uderzeniowy w przestrzeni zasięgu wymiaru VC 4.
Jeśli żadne ograniczenie nie zostanie nałożone na d, mamy standardowy problem z zestawem uderzeń, który jest W-2-kompletny i NP-kompletny.
Langerman i Morin [link do cytatu] podają algorytmy FPT dla opcji Ustaw osłonę w ograniczonym wymiarze, chociaż ich ograniczony model wymiarowy nie jest taki sam jak model zdefiniowany przez ograniczony wymiar VC. Wydaje się, że ich model nie obejmuje na przykład problemu trafiania półprzestrzeni punktami, chociaż problem prototypowy dla ich modelu jest równoważny trafianiu w hiperpłaszczyzny punktami.