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'| 内，或者反过来，或者两者以某种方式结合。

如果您在成本边缘上进行优化，那么它就是 Steiner 最小树 (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 是图中边成本的上限。

刚看到问题。希望能帮助到你。