algorithm - 是否有任何众所周知的 NP 完全问题可以减少“节点放置”问题？

Question

我有以下NP完全问题：

鉴于：

• N × N 场中的一组位置，
• 一组 m 个节点，和
• 节点的连接图（即无向图，其边表示每对相互接触的节点），以及
• 接触范围 R（与 N × N 字段的长度单位相同），

找到与连接图相关的字段中节点的放置（即放置节点，使任何接触的对比 R 更近，而任何不接触的对比 R 更远），或表明这种放置不存在。

这个问题可以简化为一个众所周知的NP完全问题吗？

（也可以考虑问题的优化版本，即找到最优化的放置）

Answer 1

设置封面听起来很像这个问题。事实上，可能几乎正是这个问题。更好的是：它有一个近似算法，保证在最优解的 O(log n) 范围内。