Введение.
На данный момент не известно полиномиальных по времени алгоритмов точного решения NP-трудных задач. Более того, специалисты по теории сложности склоняются к варианту, что таких алгоритмов не существует. Однако, NP-трудные задачи часто встречаются в жизни. Одним из способов борьбы с NP-трудными задачами на практике является применение приближенных алгоритмов.
Рассмотрим лучший известный приближенный алгоритм решения задачи о вершинном покрытии.
Постановка задачи.
Вершинное покрытие – это такое множество S вершин графа, что у каждого ребра графа хотя бы один конец входит в S.
Задача заключается в том, чтобы выбрать в неориентированном графе минимальное (по количеству вершин) вершинное покрытие.
Цель.
Построим простой алгоритм решения этой задачи, ошибающийся не более чем в два раза. Это означает, что если есть оптимальное решение — множество вершин T, то полученное нами решение S удовлетворяет неравенству |S| <= 2|T|.
Пример.
В приведенном примере вершинным покрытием является, например, множество вершин {0, 1, 2, 4}. Все шесть вершин графа также образуют вершинное покрытие. Однако, минимальным вершинным покрытием в рассматриваемом графе будет множество, состоящее всего из двух вершин. Например, это могут быть вершины с номерами 1 и 3. Действительно, все ребра графа покрываются двумя этими вершинами.
Алгоритм.
На каждом шаге алгоритма производим следующие действия:
- Выбираем случайное ребро графа e=(u, v).
- Добавляем в решение S обе выбранные вершины u и v.
- Удаляем из графа все ребра, инцидентные вершинам u или v.
Повторяем этот шаг до тех пор, пока не удалим все ребра графа.
Пример работы алгоритма.
В приведенном примере минимальное вершинное покрытие содержит три вершины. Например, это могут быть вершины 1, 3 и 6. Рассмотрим работу нашего алгоритма на приведенном примере.
Первая итерация:
- Выбираем случайное ребро. Например, ребро (1, 3).
- Добавляем в решение S обе вершины выбранного ребра: S={1, 3}.
- Удаляем из графа все ребра, инцидентные вершинам 1 или 3.
Вторая итерация:
- Выбираем случайное ребро. Пусть это будет ребро (4, 6).
- Добавляем в решение S обе вершины выбранного ребра: S={1, 3, 4, 6}.
- Удаляем из графа все ребра, инцидентные вершинам 4 или 6.
В графе не осталось ребер. Следовательно, результатом работы нашего алгоритма будет вершинное покрытие S={1, 3, 4, 6}.
Доказательство.
Докажем, что построенное множество является вершинным покрытием. Действительно, на каждом шаге мы удаляли лишь уже покрытые ребра. Мы повторяли эту итерацию, пока в графе еще оставались ребра. Таким образом, мы покрыли все ребра графа.
Докажем, что наш алгоритм ошибается не более, чем в 2 раза.
Все рассматриваемые алгоритмом ребра e не имеют общих вершин. Следовательно, из каждого из этих рёбер в оптимальное решение T должна входить хотя бы одна вершина. Это значит, что 2|T|>=|S|.
Немного истории
В знаменитой работе Ричарда Карпа «Reducibility among combinatorial problems» под названием Node Cover рассматривается соответствующая Vertex Cover задача разрешимости и доказывается ее NP-полнота.
Рассмотренный нами алгоритм был независимо разработан Fanica Gavril и Mihalis Yannakakis в 1974 году.
Лучшая известная на сегодняшний день оценка приближенного алгоритма задачи Vertex Cover
принадлежит George Karakostas. Оценка доказана в работе A better approximation ratio for the vertex cover problem.Заключение.
На данный момент не известно полиномиальных приближенных алгоритмов для Vertex Cover значительно улучшающих полученную нами точность. То есть, не известно полиномиального по времени алгоритма, который бы ошибался не более, чем в 1.999 раза. Таким образом, мы получили простой полиномиальный по времени алгоритм с хорошей точностью для решения NP-трудной задачи.