Как доказать правильность моего жадного алгоритма для вершинного покрытия дерева?

Задача вершинного покрытия на деревьях состоит в следующем.

Входные данные: ациклический простой неориентированный граф G
Выходные данные: набор вершин W такой, что для каждого ребра uv u W или v W. Мы хотим минимизировать размер В.

Мой жадный алгоритм состоит в том, чтобы инициализировать W = , затем, пока G не пусто, повторить следующие шаги. Пусть L — листовые вершины G. Пусть N(L) — множество вершин, смежных с некоторой вершиной в L. Обновим W = W N(L). Удалим вершины L N(L) и инцидентные с ними ребра из G.

Этот алгоритм работает во всех случаях, которые я пробовал до сих пор. Как мне доказать правильность? Вот что у меня есть до сих пор.

Предположим, что существует другое множество S, являющееся оптимальным решением. Наоборот, я хочу установить, что либо S не покрывает все ребра, либо что S — это то же множество, что и созданное моим жадным алгоритмом.


algorithm greedy vertex-cover
person Rumen Hristov    schedule 09.10.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Это разумное начало, но я вижу две проблемы. Во-первых, оптимальное решение может быть не единственным. Рассмотрим четырехвершинный путь a-b-c-d, который имеет три оптимальных решения: {a,c}, {b,c}, {b,d}. Во-вторых (и вы, наверное, уже это делаете, но не сказали), необходимо считать дерево укорененным. В противном случае, например, на графе a-b мы имеем L = {a,b} и N(L) = {b,a}, а полученное вершинное покрытие равно W = {b,a}, что не является оптимальным. Обозначая a как корень, он по определению исключается из набора листьев.

Чтобы формально доказать правильность программы, включающей цикл, часто полезно использовать индукцию для установления инварианта цикла. Разрешите предложить два.

  1. Для всех моментов времени t (где время = количество итераций цикла) пусть G(t) будет тем, что осталось от G в момент времени t, и пусть W(t) будет значением W в момент времени t. Для каждого вершинного покрытия X группы G(t) множество W(t) X является вершинным покрытием G(0), где 0 — время начала.

  2. Для всех моментов времени t существует оптимальное решение, содержащее W(t) в качестве подмножества.

Пусть Т будет конечным временем. Поскольку G(T) — пустой граф, X = — допустимое вершинное покрытие G(T), поэтому инвариант № 1 устанавливает, что W(T) — вершинное покрытие G(0). Инвариант № 2 устанавливает, что W(T) содержится в некотором оптимальном решении. Поскольку W(T) само по себе является вершинным покрытием, W(T) само должно быть этим оптимальным решением.

Индуктивный шаг в доказательстве инварианта № 2 состоит в том, чтобы при наличии оптимального решения, содержащего W(t-1), но не содержащего W(t), превратить его в другое оптимальное решение, содержащее W(t). Это включает в себя формализацию вашей интуиции, что всегда, по крайней мере, так же продуктивно, как взять соседа листа вместо листа.

person David Eisenstat    schedule 09.10.2014