Минимальное вершинное покрытие и жадный алгоритм

Минимальное вершинное покрытие — оптимизационная задача поиска вершинного покрытия наименьшего размера. В варианте курса основной жадный алгоритм на каждом шаге выбирает вершину, инцидентную максимальному числу ещё непокрытых рёбер, добавляет её в покрытие и удаляет покрытые рёбра.1

Алгоритм всегда строит корректное покрытие, но его важное свойство — отсутствие константной гарантии приближения: существуют семейства графов, на которых отношение размера жадного покрытия к оптимальному не ограничено одной постоянной. Это нужно отличать от другого простого локального алгоритма: выбор произвольного непокрытого ребра и добавление обоих его концов даёт 2-аппроксимацию.1, 2

Что важно запомнить
  • Жадная эвристика курса выбирает вершину максимальной текущей степени по непокрытым рёбрам.1
  • После выбора вершины все инцидентные ей рёбра считаются покрытыми и удаляются из текущего графа.
  • Алгоритм полиномиален и всегда возвращает вершинное покрытие.
  • Для этого жадного алгоритма нет универсальной константы \(c\), гарантирующей \(|C_{gr}|\le c\,OPT\) на всех графах.1
  • Алгоритм «взять оба конца произвольного непокрытого ребра» — другой алгоритм. Он имеет гарантию \(|C|\le2OPT\).2

Жадный алгоритм максимальной степени

Начинают с пустого покрытия \(C\). Пока в графе остаются непокрытые рёбра, выбирают вершину \(v\), инцидентную максимальному числу таких рёбер, добавляют \(v\) в \(C\) и удаляют все рёбра, инцидентные \(v\). Когда рёбер не остаётся, множество \(C\) является вершинным покрытием.1

Корректность как покрытия очевидна из правила остановки: алгоритм заканчивает работу только после удаления всех рёбер, а каждое удалённое ребро было покрыто выбранной вершиной.

Что можно гарантировать о качестве

Интуитивно выбор вершины, покрывающей максимум оставшихся рёбер, кажется сильным. Однако для минимального вершинного покрытия эта эвристика может систематически принимать локально привлекательные решения, несовместимые с глобальным оптимумом. В учебном источнике строится семейство «плохих» графов, на котором относительная погрешность жадного алгоритма растёт с размером экземпляра. Поэтому алгоритм 16 не обеспечивает даже постоянного коэффициента аппроксимации.1

Полезное сравнение: локальная 2-аппроксимация

Другой простой алгоритм выбирает произвольное непокрытое ребро \(\{u,v\}\), добавляет в покрытие сразу \(u\) и \(v\), а затем удаляет все рёбра, инцидентные этим вершинам. Выбранные на разных шагах рёбра образуют паросочетание \(M\). Любое вершинное покрытие должно содержать хотя бы один конец каждого ребра \(M\), поэтому \(OPT\ge|M|\). Локальный алгоритм выбирает ровно \(2|M|\) вершин, откуда \(|C|=2|M|\le2OPT\).2

Таким образом, в этой теме принципиально не смешивать два алгоритма: жадный алгоритм максимальной степени изучается как естественная эвристика с плохим худшим случаем, а алгоритм по непокрытому ребру имеет доказанную 2-аппроксимационную гарантию.

Частые ошибки
  • Приписывать жадному выбору вершины максимальной степени коэффициент 2. Такая гарантия относится к другому, локальному алгоритму по непокрытому ребру.
  • Считать полиномиальность жадной эвристики доказательством её близости к оптимуму. Быстрота и качество приближения — разные свойства.
  • Путать NP-полную decision-задачу ВЕРШИННОЕ ПОКРЫТИЕ с оптимизационной задачей поиска минимального покрытия.

Другие вопросы

Источники

  1. 1 Кузюрин Н. Н., Фомин С. А. Эффективные алгоритмы и сложность вычислений М.: МФТИ, 2007. § 2.1.2, задача 12 и алгоритмы 16–17 для минимального вершинного покрытия
  2. 2 MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms Spring 2015. Lecture 17 «Approximation Algorithms», раздел «Approximation Algorithm for Vertex Cover»