Zusammenstellung von sich paarweise überschneidenden Familien

Eine Schlagmenge einer Familie $\mathcal{S} = \{S_1, \dots, S_n\}$ ist eine Teilmenge $H$ von $\bigcup_{i=1}^{n} S_i$ so dass $H \cap S_i \ne \emptyset$ für $1 \le i \le n$ . Das Problem, eine minimale Treffermenge einer gegebenen Familie zu finden, ist im Allgemeinen NP-schwer, da es das Vertex-Cover-Problem verallgemeinert. Jetzt ist meine Frage:

Bleibt das Schlagmengenproblem NP-hart, wenn sich die Elemente von $\mathcal{S}$ paarweise schneiden?

Ich interessiere mich auch für die Approximationshärte (oder Traktabilität) dieses Problems.

Die Antwort lautet ja - das Problem ist immer noch NP-vollständig. für jede Menge ein gefälschten Elemente erstellen e ' i , e " i und erstellen Sie einen neuen Sätze S ' i = S i ∪ { e ' i } und S " i = S i ∪ { e " i } . Es ist leicht zu überprüfen, ob ein Schlagsatz des alten Systems ein Schlagsatz des neuen Systems ist. Ausser den gefälschten Elementen hat jetzt jedes Element mindestens drei Sätze getroffen.$S_i$$e_i', e_i''$$S_i' = S_i \cup \{ e_i'\}$$S_i'' = S_i \cup \{e_i''\}$

Als nächstes erstellen Sie für jedes Paar von Mengen im neuen System (nennen sie und , um Verwirrung zu vermeiden) ein falsches Element und fügen es sowohl zu als auch zu . Es ist klar, dass sich im resultierenden Mengen-System alle Mengen paarweise kreuzen, aber die ursprüngliche optimale Schlagmenge ist immer noch die optimale Schlagmenge für dieses neueste System.$T_i$x i j T i T $T_j$$x_{ij}$$T_i$$T_j$

Ohne weitere Einschränkungen sieht das Problem genauso schwer aus wie das ursprüngliche Problem.

Übrigens, zu beweisen, dass die optimale Lösung keines der gefälschten Elemente verwenden würde, ist nicht trivial. Erstens können wir davon ausgehen, dass eine bestimmte Treffermenge für das neue System kein oder e' ' i enthält , da wir andernfalls die Elemente zu den ursprünglichen Elementen der Sätze verschieben und einen Schlagsatz mit ähnlicher Größe erhalten können. Es ist etwas subtiler zu sehen, warum sich die Elemente x i j nicht in der optimalen Treffermenge befinden. Da es mühsam ist, möchte ich nur einen Hinweis hinterlassen: Erstellen Sie eine Grafik, die zwei Mengen verbindet$e_i'$$e_i''$$x_{ij}$ und S j im ursprünglichen System verbindet, wenn x i $S_i$$S_j$$x_{ij}$Verbindet zwei Mengen, die von diesen Mengen abgeleitet sind. Argumentieren Sie, dass dieses Diagramm in der minimalen Treffermenge regulär sein muss, und die Anzahl der Kanten in ihm als solche die Anzahl der als Eckpunkte vorhandenen Mengen strikt übersteigt. Als solches kann man für diese Sätze einen kleineren Schlagsatz finden.$3$