Есть ли хорошо известная NP-полная проблема, до которой я могу уменьшить проблему «размещения узлов»?

Question

У меня есть следующая NP-полная проблема:

Дано:

• набор местоположений в поле N × N,
• набор из m узлов и
• граф связности узлов (то есть неориентированный граф, ребра которого представляют каждую пару узлов, контактирующих друг с другом), и
• диапазон контакта R (в той же единице длины, что и поле N × N),

найти расположение узлов в поле относительно графа связности (т. Е. Расположить узлы так, чтобы любая пара в контакте была ближе, чем R, а любая пара, не находящаяся в контакте, дальше, чем R), или показать, что такого размещения не существует .

Является ли хорошо известной NP-полной проблемой, до которой эта проблема может быть уменьшена?

(Также можно рассмотреть вариант оптимизации задачи, т. Е. Найти наиболее оптимальное размещение)

Answer 1

Установка обложки звучит очень похоже на эту проблему.На самом деле, это может быть почти именно эта проблема.Еще лучше: алгоритм аппроксимации гарантированно находится в пределах O (log n) оптимального решения.