Установите крышку с ограниченным размером пересечения

11

Таким образом, проблема покрытия множеств является тривиальной, если ни один из наборов кандидатов не пересекается друг с другом.

Однако что, если размер пересечения для любой пары наборов кандидатов был не больше 1? Эта проблема NP-сложная?

Я был бы признателен за любое понимание.

Спасибо Гаррет

Гарретт Андерсен
источник
9
Этот документ может быть актуальным: hariharan-ramesh.com/papers/setco.pdf
Сянь-Чи Чанг 張顯 之

Ответы:

5

Если я чего-то не пропустил, вы можете использовать сокращение от ОДНОГО НАКЛАДНОГО ОГРАНИЧЕННОГО ТОЧНОГО ПОКРЫТИЯ НА 3 КОМПЛЕКТА (SINGLE OVERLAP RX3C), которое я доказал как NPC в этом историческом вопросе .

Точная обложка с тремя наборами (X3C):

X={x1,x2,...,x3q}C={C1,...,Cm}X
XCCXC

xiC

Cij|CiCj|1

XC1,...Cmq

<q3qXq3q

[1] Теофило Ф. Гонсалес: кластеризация для минимизации максимального межкластерного расстояния. Теор. Вычи. Sci. 38: 293-306 (1985).

Марцио де Биаси
источник