对于哪些特殊情况，该顶点涵盖算法失败或工作？

Question

我正在尝试找到一种多项式时间算法，以查找图形的最小顶点盖。我已经写了下面的算法；我知道这个问题是$ mathsf {np} $ - 硬，这意味着可能有一些图表无法正常工作。

我需要一些帮助来查找该算法中的缺陷，还可以指出应在图上施加哪些限制，以使该算法有效。

在下面的算法中，我有一个图$ g =（v，e）$。我还定义了$ text {Priority}（v）$ function;粗略地说，这是顶点$ v $覆盖的边缘数量。该功能具有属性

$$ sum_ {v in V} text {primity}（v）= text {extges}。$$

换句话说，边缘仅被其一个顶点之一覆盖，而不是两者兼而有之。

Define degree : V -> NaturalNumbers
degree(v) = number of edges connected to v, for all v in V

Define priority : V -> NaturalNumbers
Initialize priority(v) = 0 for all v in V

For all (u, v) in E:
    If degree(u) >= degree(v):
        priority(u) = priority(u) + 1
    Else
        priority(v) = priority(v) + 1

Define S as the solution to the vertex cover problem
Initialize S to the empty set

For all v in V:
    If priority(v) != 0:
        Add v to the set S

Output S as the solution

Answer 1

在所有情况下，试图将“高优先级” IE IE高于邻居的高度无法正常工作。此算法选择$ n-1 $ for $ c_n $（循环图 在$ n $顶点）。如果$（n-1）/2 $或$ n/2 $，则应选择其奇数，甚至$ n/2 $。它也失败了 完美的图.

我很确定这也给出了$ O（ log n）$近似值。如果您按程度订购顶点并贪婪地选择顶点，直到覆盖所有边缘，它基本上是相同的贪婪算法，与$ O（ log n）$ set Cover。