是否有任何知名的NP完全問題，我可以減少「節點佈局」問題？

Question

我有以下NP完全問題： 給定一組N個N字段中的一組位置，以及一組m個節點，還有一個節點的連通圖（即一個無向圖，其邊緣代表每對與每個節點接觸的節點）以及接觸範圍R（與N×N字段具有相同的長度單位），在關於連接圖的字段中找到節點的位置（即放置節點，接觸的任何對接近比R和eny對不接觸比R更遠），或者表明這種放置不存在。

我們是否有任何知名的NP完全問題，這個問題可以簡化爲？ （也可以考慮優化版本的問題，即找到最優化的位置）

Answer 1

Set cover聽起來很像這個問題。事實上，這可能幾乎就是這個問題。甚至更好：它有一個approximation algorithm保證在最佳解決方案的O（log n）之內。