Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique
Задача vcover-clique
Цыганова Светлана, 974 гр.
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
- о поиске максимального по числу вершин полного подграфа (клики) в графе
- и задачи о вершинном покрытии
Решение
Докажем, что каждая задача полиномиально сводима к задаче о независимом множестве (и обратно), следовательно, они будут полиномиально сводимы друг к другу.
1) Вершинное покрытие <-> задача о независимом наборе.
Эти задачи эквивалентны. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение S', где (S' = V\S), а V - это множество всех вершин графа, является независимым множеством. Таким образом, найдя максимальное независимое множество и взяв дополнение от него, мы найдем максимальное вершинное покрытие графа, и наоборот.
2) Задача о независимом наборе <-> максимальная клика.
Известно, что множество независимо тогда и только тогда, когда оно является кликой в дополнении графа. Таким образом, если требуется найти максимальную клику, то нужно построить дополнение к графу, найти в дополнении максимальное независимое множество, и это множество как раз будет составлять максимальную клику в исходном графе. Чтобы найти максимальное независимое множество, нужно построить дополнение к графу, найти в дополнении максимальную клику, и эта клика будет максимальным множеством в исходном графе.
Итак, чтобы найти вершинное покрытие в графе, нужно построить дополнение к графу, найти в нем максимальную клику, и взять оставшиеся вершины, не вошедшие в максимальную клику.
Чтобы найти максимальную клику, нужно построить дополнение к графу, в дополнении найти вершинное покрытие, и взять дополнение к множеству вершин из вершинного покрытия. Это и будет максимальная клика.
Все операции по взятию дополнения к множеству вершин и построению дополнения делаются за полиномиальное время, поэтому задачи полиномиально сводимы.
PS. Все факты об эквивалентностях задач взяты из Википедии, чтобы не доказывать лишний раз.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.