Показать, что эвристическое решение для покрытия вершин не более чем в два раза больше оптимального решения

#algorithm #graph #graph-algorithm #heuristics #vertex-cover

#алгоритм #График #граф-алгоритм #эвристика #покрытие вершин

Вопрос:

Эвристическое решение, которое мне дали, является:

  • Выполните поиск в глубину на графике
  • Удалите все листья
  • Оставшийся граф образует покрытие вершин

Мне был задан вопрос: «Покажите, что это эвристическое решение не более чем в два раза больше оптимального решения для покрытия вершин». Как я могу это показать?

Комментарии:

1. Является ли эвристическая часть вопроса или это ваше собственное предложение в качестве эвристического ответа на вопрос «Покажите, что СУЩЕСТВУЕТ эвристическая …» ?

2. Это дано как часть вопроса, это не тот, который я придумал.

3. Покрытие вершин покрывает ребра . Вам нужна одна из конечных точек каждого ребра. Похоже, вы думаете о другой проблеме.

4. Вы правы, я перепутал его с минимальным связующим деревом. Я отредактирую вопрос. Однако я все еще не уверен, как показать, что эвристическое решение не более чем в два раза больше.

5. Это не оптимизация с коэффициентом 2 для MST.

Ответ №1:

Я предполагаю, что граф связан (если это не так, мы можем решить эту проблему для каждого компонента отдельно).

Я также предполагаю, что dfs-дерево является корневым, а листом является вершина, у которой нет дочерних элементов в корневом dfs-дереве (это важно. Если мы определим его по-другому, алгоритм может не сработать).

Нам нужно показать вещам:

  1. Набор вершин, возвращаемый алгоритмом, является покрытием вершин. Действительно, в dfs-дереве любого неориентированного графа могут быть только типы ребер: ребра дерева (такое ребро покрыто, поскольку по крайней мере одна из его конечных точек не является листом) и заднее ребро (опять же, одна из его конечных точек не является листом, потому что заднее ребро идет от вершины к ее предку. Лист не может быть предком листа).

  2. Давайте рассмотрим dfs-дерево и проигнорируем остальные ребра. Я покажу, что невозможно покрыть ребра дерева, используя менее половины не оставляющих вершин. Пусть S — минимальное покрытие вершин. Рассмотрим вершину, v такую v , которая не является листом и v не входит в S (то есть v возвращается рассматриваемой эвристикой, но не входит в оптимальный ответ). v не является листом, следовательно, в dfs-дереве есть ребро v -> u (где u является преемником v ). Ребро v -> u покрыто S . Таким образом, u находится в S . Давайте определим отображение f из вершин, возвращаемых эвристикой, которые не входят в S as f(v) = u (где v и u имеют то же значение, что и в предыдущем предложении). Обратите внимание, что v является родительским для u в dfs-дереве. Но для любой вершины в дереве может быть только один родительский элемент! Таким образом, f это внедрение. Это означает, что количество вершин в наборе, возвращенном эвристикой, но не в оптимальном ответе, не больше размера оптимального ответа. Это именно то, что нам нужно было показать.

Ответ №2:

Плохие новости: эвристика не работает. Строго говоря, 1 изолированная вершина является контрпримером для вопроса. Тем не менее, эвристика вообще не дает решения для покрытия вершин, даже если вы исправите ее для изолированной вершины и для двухточечных кликов. Взгляните на полносвязные графы с числом вершин от 1 до 3:

1 — строго говоря, изолированная вершина не является листом (она имеет степень 0, в то время как лист — это вершина со степенью 1), поэтому эвристическое решение сохранит ее, в то время как покрытие вершин не будет

2 — эвристическое решение удалит оба листа, в то время как покрытие вершин сохранит по крайней мере 1 из них

3 — эвристическое решение оставит 1 вершину, в то время как покрытие вершин должно содержать не менее 2 вершин этой группы

Комментарии:

1. Эвристика работает, если мы считаем дерево dfs корневым и определяем лист как вершину, у которой нет дочерних элементов.

2. * не имеет дочерних элементов