algorithm - 同様の既知の問題を探しています

Question

この最適化問題のコンピュータの複雑さを証明しようとしています:
連結グラフ G = (V, E) と集合 S ⊊ V が与えられた場合、連結部分グラフ G'= (V', E ') を見つけます。

Min f(G')
Min |V'|

対象:

S ⊊ V’
V’ ⊆ V

すべての頂点をツリーに含める必要がない場合、最小スパニング ツリー問題の一般化のように見えます。この問題の複雑さを還元によって証明するために使用できる既知の問題はありますか?

Answer 1

問題の定式化は、最初に f(G') とその Min|V'| 内、またはその逆、または 2 つを何らかの方法で組み合わせて最適化していることを示しているわけではありません。

コスト エッジで最適化する場合、それはシュタイナー最小ツリー (SMT) 問題であり、NP 完全です。|V'| で最適化すると、次のように多項式時間で SMT をそれに減らすことができます。

ノード u と v の間のエッジ (u,v) のコストを k とします。このエッジを次のパスに置き換えます。

(u, i_1), (i_1, i_2), ..., (i_k, v) 

したがって、このパスの各エッジのコストは 1 です。コスト (u, v) のエッジを、k-1 個の中間ノードを持つパスに置き換え、すべてのエッジのコストは 1 です。

グラフのすべてのエッジに対してこれを行います。それはSMTをあなたの問題に還元し、あなたの問題が|V'|で最適化されていることを証明します。は NP 完全です。あなたの削減はかかります

O(C*|V|^2) 

C はグラフのエッジのコストの上限です。

ちょうど問題を見ました。それが役に立てば幸い。