Set Cover mit begrenzter Schnittgröße

Das Set-Cover-Problem ist also trivial, wenn sich keines der Kandidatensets überschneidet.

Was ist jedoch, wenn die Größe der Schnittmenge für ein Paar von Kandidatensätzen höchstens 1 beträgt? Ist dieses Problem NP-schwer?

Ich würde mich über jeden Einblick freuen.

Danke, Garrett

Wenn mir etwas nicht fehlt, können Sie eine Reduktion von SINGLE OVERLAP RESTRICTED EXACT COVER um 3 SETS (SINGLE OVERLAP RX3C) verwenden, die ich in dieser theoretischen Frage als NPC erwiesen habe .

GENAUE ABDECKUNG DURCH DREI SETS (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. Gonzalez: Clustering zur Minimierung der maximalen Intercluster-Entfernung. Theor. Comput. Sci. 38: 293 & ndash; 306 (1985).