Таким образом, проблема покрытия множеств является тривиальной, если ни один из наборов кандидатов не пересекается друг с другом.
Однако что, если размер пересечения для любой пары наборов кандидатов был не больше 1? Эта проблема NP-сложная?
Я был бы признателен за любое понимание.
Спасибо Гаррет
Ответы:
Если я чего-то не пропустил, вы можете использовать сокращение от ОДНОГО НАКЛАДНОГО ОГРАНИЧЕННОГО ТОЧНОГО ПОКРЫТИЯ НА 3 КОМПЛЕКТА (SINGLE OVERLAP RX3C), которое я доказал как NPC в этом историческом вопросе .
Точная обложка с тремя наборами (X3C):
[1] Теофило Ф. Гонсалес: кластеризация для минимизации максимального межкластерного расстояния. Теор. Вычи. Sci. 38: 293-306 (1985).
источник