Establecer cubierta con tamaño de intersección acotada

Entonces, el problema de la cobertura del conjunto es trivial si ninguno de los conjuntos candidatos se cruza entre sí.

Sin embargo, ¿qué pasa si el tamaño de la intersección para cualquier par de conjuntos candidatos era como máximo 1? ¿Es este problema NP-hard?

Agradecería cualquier idea.

Gracias garrett

Si no me falta algo, puede usar una reducción de CUBIERTA EXACTA RESTRINGIDA DE UN SOLO OBSERVACIÓN EN 3 SETS (SINGLE OVERLAP RX3C) que probé ser NPC en esta pregunta básica .

CUBIERTA EXACTA POR TRES JUEGOS (X3C):

$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. González: Agrupación para minimizar la distancia máxima entre clústeres. Theor Comput Sci. 38: 293-306 (1985).