Ustaw osłonę z ograniczonym rozmiarem przecięcia

Problem pokrycia zestawu jest więc trywialny, jeśli żaden z zestawów kandydujących się nie przecina.

Co jednak, jeśli rozmiar przecięcia dowolnej pary zestawów kandydujących wynosił co najwyżej 1? Czy ten problem jest trudny NP?

Byłbym wdzięczny za każdy wgląd.

Dzięki, Garrett

Jeśli czegoś mi nie brakuje, możesz użyć redukcji z POJEDYNCZEGO OGRANICZONEGO DOKŁADNEGO POKRYWY O 3 ZESTAWY (POJEDYNCZY OKRĄGŁY RX3C), który okazał się być NPC w tym pytaniu cstheory .

DOKŁADNE POKRYCIE PRZEZ TRZY ZESTAWY (X3C):

Przykład : Zestaw oraz zbiór C = { C : 1 , . . . , C m } podzbiorów 3 elementem X . Pytanie : Czy C zawierają dokładne pokrycie X , czyli subcollection C ' ⊆ C takie, że każdy element X występuje dokładnie jeden członek $X=\{x_1,x_2,...,x_{3q}\}$$C=\{C_1,...,C_m\}$$X$
$X$$C′\subseteq C$$X$ ?$C′$

X3C jest NP-kompletny (patrz G&J) i jak pokazano w [1] pozostaje NP-kompletny, nawet jeśli każdy element jest zawarty dokładnie w 3 podzbiorach C (OGRANICZONA DOKŁADNA POKRYWA PRZEZ TRZY ZESTAWY, RX3C).$x_i$$C$

Udowodniłem, że pozostaje NP-kompletny, nawet jeśli każda para podzbiorów w ma co najwyżej jeden element; tj. dla wszystkich i ≠ j , | C i ∩ C j | ≤ 1 (nazwałem tę ograniczoną wersję SINGLE OVERLAP RX3C).$C$$i\neq j$$|C_i \cap C_j|\leq 1$

SIZE SET COVER Z ograniczonym INTERSECTION 1 (jego wersja decyzja) jest po prostu uogólnieniem pojedynczych OBSZARU RX3C, rzeczywiście można odebrać tego samego wszechświata i ten sam zbiór podzbiorów C 1 , . . . C m z jednolitego OBSZARU RX3C i poprosić o pokrywy q podzbiorów lub mniej.$X$$C_1,...C_m$$q$

Oczywiście okładka z podzbiorami nie może istnieć, ponieważ każdy podzbiór zawiera trzy elementy, aw X są 3 elementy q . Okładka z q podzbiorami musi być dokładna: jeśli dwa podzbiory zawierają wspólny element, to obejmuje mniej niż 3 q elementów.$< q$$3q$$X$$q$$3q$

[1] Teofilo F. Gonzalez: Klastrowanie w celu zminimalizowania maksymalnej odległości między klastrami. Teoria Comput. Sci. 38: 293–306 (1985).