动态规划：简单图的顶点覆盖

Question

我正在寻找一种有效的算法来找到两个特定图的最小成本顶点覆盖，其中顶点具有不同的成本。

第一个图是排序的链表，其中我们有 V={1...n} 和 E={{1,2},{2,3},{3,4}。 ..{n-1,n}}

第二张图是一个简单的循环。与上面基本相同，但 {n,1} 也是一条边。

我找到了一种递归地执行第一个方法的方法，只需详尽地检查每个节点是否应该在顶点覆盖中。

VC(Graph G(V,E)):
  if(|V|=0) return 0
  u=first node of V
  v=second node of V
  return min(VC(Graph.remove(u)+cost(u),   //Case where the first node is in VC
             VC(Graph.remove(v,u))+cost(v)) //Case where second node is in VC

然而这确实是低效的，有没有办法使用动态规划来改进它？

Answer 1

对于链，动态规划解决方案非常简单。状态是(number of vertices processed, is the last vertex taken)。状态的值是覆盖这部分图的最小成本。
对于一个循环，我们可以使用以下观察：第一个或第二个顶点在封面中。所以我们可以通过删除第一个或第二个顶点并选择最佳答案将其简化为 1) 问题。

这两个解决方案都具有线性时间复杂度。

第 1 部分的一些伪代码：

f(1, false) = 0 // do not take the first vertex
f(1, true) = cost(1) // take it
for v <- 2 ... n:
    f(v, false) = f(v - 1, true) // do not take the current vertex
    f(v, true) = min(f(v - 1, true), f(v - 1, false)) + cost(v) // take it
print(min(f(n, false), f(n, true)))

动态规划：简单图的顶点覆盖

Dynamic Programming: Vertex Cover of simple graphs

algorithm

graph

dynamic-programming