Definir capa com tamanho de interseção delimitada

Portanto, o problema da cobertura do conjunto é trivial se nenhum dos conjuntos candidatos se cruzar.

No entanto, e se o tamanho da interseção para qualquer par de conjuntos de candidatos fosse no máximo 1? Este problema é NP-difícil?

Eu apreciaria qualquer insight.

Obrigado, Garrett

Se não estiver faltando alguma coisa, você pode usar uma redução da TAMPA EXATA RESTRITA POR UM ÚLTIMO SOBRELAP EM 3 CONJUNTOS (ÚNICO SOBRELAP RX3C), que eu provei ser o NPC nessa questão de história .

COBERTURA EXATA POR TRÊS CONJUNTOS (X3C):

Instância : Set e uma coleção de subconjuntos 3 elementos de . Pergunta : C contém uma cobertura exata para , ou seja, uma subcoleção modo que todo elemento de ocorra exatamente em um membro de ?C = { C 1 , . . . , C m } X X C ' ⊆ C X C $X=\{x_1,x_2,...,x_{3q}\}$$C=\{C_1,...,C_m\}$$X$
$X$$C′\subseteq C$$X$$C′$

$x_i$$C$

$C$$i\neq j$$|C_i \cap C_j|\leq 1$

$X$$C_1,...C_m$$q$

$< q$$3q$$X$$q$$3q$

[1] Teofilo F. Gonzalez: Clustering para minimizar a distância máxima do intercluster. Theor. Comput. Sci. 38: 293-306 (1985).