Для каких особых случаев этот алгоритм обложки вершины проваливается или работает?

Question

Я пытаюсь найти алгоритм полиномиального времени для поиска минимальной вершинной крышки для графика. Я написал алгоритм ниже; Я знаю, что эта проблема-$ mathsf {np} $-сложно, что означает, что, вероятно, есть некоторые графики, для которых этот алгоритм не будет работать.

Мне нужна помощь в поиске недостатка в этом алгоритме, а также указывает на то, какие ограничения должны быть наложены на графики, так что этот алгоритм работает.

В алгоритме ниже у меня есть график $ g = (v, e) $. Я также определяю функцию $ text {Приоритет} (v) $; С грубыми терминами это количество краев, покрытых вершиной $ V $. У функции есть свойство, которое

$$ sum_ {v in v} text {Приоритет} (v) = text {количество ребер}. $$

Другими словами, преимущество считается только одной из его вершин, а не обеими.

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

Попытка принять «высокий приоритет», то есть вершины высокой степени над своими соседями, не будет работать во всех случаях. Этот алгоритм выбирает $ n-1 $ для $ c_n $ (Цикл график на вершинах $ n $). Он должен выбрать либо $ (n-1)/2 $, либо $ n/2 $, если его нечетное или даже. Это также не удается Идеальные графики.

Я почти уверен, что это дает приближение $ O ( log n) $. Если вы заказываете вершины по степени и жадно выбираете вершины до тех пор, пока все края не будут покрыты, это в основном тот же жадный алгоритм, что и обложка $ O ( log n) $.