Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique

Ссылки сюда (13) →

Задача vcover-clique

Цыганова Светлана, 974 гр.

Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач

• о поиске максимального по числу вершин полного подграфа (клики) в графе
• и задачи о вершинном покрытии

Решение

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

1) Вершинное покрытие <-> задача о независимом наборе.

Эти задачи эквивалентны. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение S', где (S' = V\S), а V - это множество всех вершин графа, является независимым множеством. Таким образом, найдя максимальное независимое множество и взяв дополнение от него, мы найдем максимальное вершинное покрытие графа, и наоборот.

2) Задача о независимом наборе <-> максимальная клика.

Известно, что множество независимо тогда и только тогда, когда оно является кликой в дополнении графа. Таким образом, если требуется найти максимальную клику, то нужно построить дополнение к графу, найти в дополнении максимальное независимое множество, и это множество как раз будет составлять максимальную клику в исходном графе. Чтобы найти максимальное независимое множество, нужно построить дополнение к графу, найти в дополнении максимальную клику, и эта клика будет максимальным множеством в исходном графе.

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

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

Все операции по взятию дополнения к множеству вершин и построению дополнения делаются за полиномиальное время, поэтому задачи полиномиально сводимы.

PS. Все факты об эквивалентностях задач взяты из Википедии, чтобы не доказывать лишний раз.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.