Zestaw uderzenia z rodziny jest podzbiorem z taki sposób, do . Problem znalezienia minimalnego zestawu uderzeń z danej rodziny jest ogólnie trudny do przeprowadzenia, ponieważ uogólnia problem pokrycia wierzchołków. Teraz moje pytanie brzmi:⋃ n i = 1 S i H ∩ S i ≠ ∅ 1 ≤ i ≤ n
Czy problem zestawu uderzeń pozostaje trudny do NP, gdy pary elementów przecinają się?
Interesuje mnie również twardość aproksymacyjna tego problemu.
Odpowiedzi:
S ′ i = S i ∪ { e ′ i } S ″ i = S i ∪ { e ″ i }
Następnie, dla każdej pary zestawów w nowym systemie (nazwijmy je i aby uniknąć zamieszania), utwórz fałszywy element i dodaj go zarówno do jak i . Oczywiście w wynikowym systemie zestawów wszystkie zestawy przecinają się parami, ale oryginalny optymalny zestaw uderzeń jest nadal optymalnym zestawem uderzeń dla tego najnowszego systemu.T j x i j T i T j
Bez dalszych ograniczeń problem wygląda tak samo, jak problem pierwotny.
BTW, udowodnienie, że rzeczywiście optymalne rozwiązanie nie wykorzystałoby żadnego z fałszywych elementów, nie jest trywialne. Po pierwsze, możemy założyć, że dany zestaw uderzeń dla nowego systemu nie zawiera żadnych lub , ponieważ w przeciwnym razie możemy przenieść elementy do oryginalnych elementów zestawów i uzyskać zestaw uderzeń o podobnej wielkości. Nieco subtelniej jest zrozumieć, dlaczego elementy nie są w optymalnym zestawie uderzeń. Ponieważ jest to żmudne, zostawię tylko wskazówkę: zbuduj wykres łączący dwa zestawy i w oryginalnym systemie, jeśli połączy dwa zestawy pochodzące z tych zbiorów. Argumentuj, że ten wykres w zestawie minimalnego trafienia musi wynosićregularna i jako taka liczba krawędzi ściśle przekracza liczbę zbiorów obecnych jako wierzchołki. Jako taki, można znaleźć mniejszy zestaw uderzeń dla tych zestawów.