树算法上常见的最小顶点覆盖的（可能的）反例和我的方法

Question

过去在网站上快速搜索有很多关于这个主题的帖子，其中很多都使用了这种动态规划循环：

C(x) = min(1 + sum (C(i) for i in x's children), len(x's children) + sum(C(i) for i in x's grandchildren))

假设树的根节点为节点 1，我针对节点链 1-2-3-4-5-6 尝试了此算法，以获得以下 C(i)：

| C(1) | C(2) | C(3) | C(4) | C(5) | C(6) |

| 3 | 2 | 2 | 1 | 1 | 1 |

然而，C(1)的正确答案应该是2，这是通过标记节点2和5来实现的。

我决定尝试自己的方法，详述如下：

int solve(int curr, int height){
    if(dp[curr][height] > -1) return dp[curr][height];
    if(int(children[curr].size()) == 0) return dp[curr][height] = height > 1 ? 1 : 0;
    if(height == 3){
        int ret = 1;
        for(int i = 0; i < int(children[curr].size()); i++){
            int next = children[curr][i];
            ret += solve(next, 1);
        }
        return dp[curr][height] = ret;
    }
    int ret1 = 0; int ret2 = 1;
    if(height == 2){
        for(int i = 0; i < int(children[curr].size()); i++){
            int next = children[curr][i];
            ret1 += solve(next, 3); ret2 += solve(next, 1);
        }
        return dp[curr][height] = min(ret1, ret2);
    }
    for(int i = 0; i < int(children[curr].size()); i++){
        int next = children[curr][i];
        ret1 += solve(next, 2); ret2 += solve(next, 1);
    }
    return dp[curr][height] = min(ret1, ret2);
}

curr 是我们所在的当前节点，height 是距离它上面最近的标记节点的距离。这个想法是，一旦节点的高度 = 3，就必须在该特定路径中对其进行标记。否则，我们可以暂时跳过标记它。叶子节点除外，如果相邻节点没有标记，则必须标记。

有人可以验证我的方法的有效性，并解释为什么第一个算法没有通过链测试吗？

提前致谢！

Answer 1

第一个算法确实有效。在最小顶点覆盖中，每条边必须入射到至少一个顶点。在你的 "counterexample" 中，顶点 3 和 4 都没有被标记，因此边 (3,4) 在集合中没有关联顶点。所以 {2, 5} 不是顶点覆盖。

你的方法根本行不通。首先，我认为您仍然使用错误的最小顶点覆盖定义。我猜，就像您认为的那样，每个顶点都必须被标记顶点的边缘所触及。

而且即使你使用了错误的定义，你的方法也不会奏效。与标记的 parent 顶点的距离为 3 的顶点不必标记。看这个例子：

在这个例子中，如果顶点 0 被标记，那么顶点 3 和 4 也会被标记，因为它们与顶部的距离为 3。但是没有必要标记顶点 4，我们也可以标记顶点 5。显然，在这个例子中这会给出相同数量的顶点，但我相信你可以将它扩展到一个更大的例子，在那里你的方法失败了。

不同定义的解决思路：

我相信贪婪的解决方案有效。（还有一个最小顶点覆盖的贪心算法）。从叶子开始向上到中心。只标记需要标记的节点。

你可以用深度优先搜索和 DP 再次这样做。令 dp[v] 为 v 与 v 的子树中标记节点之间的最短距离。要计算 v，首先计算 children 节点的所有 dp 值，然后决定是否需要对其进行标记或不。如果任何 child 有 dp[child] = 2，那么你需要标记 v 并设置 dp[v] = 0。否则你不必标记它和 dp[v] = min (dp[children] + 1)。最后，您可能还需要标记根节点。

注意：我没有测试过这个。

树算法上常见的最小顶点覆盖的（可能的）反例和我的方法

A (Possible) Counterexample to a Common Minimum Vertex Cover on a Tree Algo and My Approach

tree

dynamic-programming

vertex-cover

不同定义的解决思路：