algorithm - 证明顶点覆盖的启发式解至多是最优解的两倍

Question

我得到的启发式解决方案是：

• 在图上执行深度优先搜索
• 删除所有叶子
• 剩下的图形成一个顶点覆盖

我被问到这个问题：“证明这个启发式最多是顶点覆盖的最佳解决方案的两倍”。我怎样才能显示这个？

Answer 1

坏消息：启发式方法不起作用。严格来说，1 个孤立顶点是该问题的反例。然而，启发式根本不提供顶点覆盖解决方案，即使您针对孤立顶点和 2 点团进行校正。看一下顶点数从 1 到 3 的全连接图：

1 - 严格地说，孤立的顶点不是叶子（它的度数为 0，而叶子是度数为 1 的顶点），所以启发式会保留它，而顶点覆盖不会

2 - 启发式将丢弃两片叶子，而顶点覆盖将至少保留其中的一片

3 - 启发式将留下 1 个顶点，而顶点覆盖必须保留该集团的至少 2 个顶点

Answer 2

我假设图是连通的（如果不是这样，我们可以分别为每个组件解决这个问题）。

我还假设 dfs-tree 是有根的，而叶子是一个在有根的 dfs-tree 中没有子节点的顶点（这很重要。如果我们以不同的方式定义它，算法可能不起作用）。

我们需要向事物展示：

1. 算法返回的一组顶点是一个顶点覆盖。实际上，在任何无向图的 dfs-tree 中只能有几种边：树边（这样的边被覆盖，因为它的至少一个端点不是叶子）和后边（同样，它的一个端点不是叶子，因为后边从顶点到它的祖先。叶子不能是叶子的祖先）。

2. 让我们考虑 dfs-tree 并忽略其余的边。我将证明使用少于一半的非离开顶点是不可能覆盖树边缘的。令 S 为最小顶点覆盖。考虑一个 vertex v，它v不是叶子，v也不在S其中（也就是说，v由所讨论的启发式方法返回，但它不在最佳答案中）。v不是叶子，因此v -> udfs-tree 中有一条边（其中u是 的继承者v）。边缘v -> u被 覆盖S。因此，u在S. 让我们从启发式返回的顶点定义一个映射f，这些顶点不在Sas f(v) = u(where vandu与前一句的意思相同）。请注意，它是dfs-tree 中v的父级。u但是树中的任何顶点只能有一个父节点！因此，f是注射。这意味着启发式返回的集合中但不在最优答案中的顶点数不大于最优答案的大小。这正是我们需要展示的。