Ниже — компактное практическое руководство: простой жадный алгоритм для Vertex Cover с доказательством аппроксимации, замечания по реализации для больших разреженных/плотных графов и критерии выбора между точными, эвристическими и аппроксимационными методами.

1) Алгоритм $классика:2-аппроксимациячерезмаксимальнуюнепересекающуюсяпарувершин,т.е.максимальноесовпадениеребер$

Идея: пока есть ребро $u,v$ — берём оба конца в покрытие и удаляем все инцидентные им ребра.

Псевдокод:

C ← ∅Пока E ≠ ∅:
выбери любое ребро $u,v$ ∈ EC ← C ∪ {u,v}удалить из графа все ребра, инцидентные u или vвернуть C

Корректность и аппроксимационный коэффициент $2$:

Пусть мы выбрали k различных ребёр $u_i,v_i$ $онипопарнонепересекаютсяпоребрам,потомучтопослевыбораребравсеинцидентныеудаляются$.В нашем покрытии |C| = 2k.Любое допустимое вершинное покрытие должно покрыть каждое из этих k ребёр, значит по крайней мере одна вершина из каждой пары должна быть в оптимуме OPT. Так OPT ≥ k.Следовательно |C| = 2k ≤ 2·OPT. То есть алгоритм даёт 2-аппроксимацию.Пример, показывающий точность оценки: граф, состоящий из k независимых ребёр. OPT = k, алгоритм возвращает 2k — фактор 2 достигается.

Сложность: реализация на основе списков смежности — O$m$ времени $каждоереброудаляется/обрабатываетсямаксимумодинраз$, O$n+m$ памяти.

2) Варианты и улучшения на практике

LP-округление: решить линейную релаксацию Vertex Cover, затем взять все вершины с x_v ≥ 1/2. Это тоже даёт 2-аппроксимацию, иногда даёт лучшие практические решения, но требует решения линейной задачи $дорожедляоченьбольшихграфов$.Жадный по степени: на каждой итерации брать вершину с максимумом степени, добавлять её в покрытие и удалять инцидентные ребра. Быстро и часто даёт хорошие эмпирические результаты, но не имеет формального коэффициента 2 $иможетхуженанекоторыхвходах$.Локальный поиск $локальныеулучшения$, табу-поиск, simulated annealing — хорошие эвристики для больших графов, но без гарантии качества.

3) Реализация для больших разреженных графов

Структуры данных:
списки смежности (vector<vector> / adjacency lists), булевы массивы visited/removed для вершин/рёбер;для жёсткой производительности — хранить список всех ребер и флаг «удалено» для каждого; при выборе ребра пропускать уже удалённые.Сложность: O$m$ время и O$n+m$ память — работает при m ~ O$n$.Параллельность/распределённость:
можно строить максимально независимое множество ребёр $maximalmatching$ параллельно $локальныеалгоритмыпотипуLuby$, что даёт тот же фактор 2.в потоковой модели $semi-streaming$ можно в один проход сохранять ребра, пока обе вершины ещё не захвачены — тоже 2-аппрокс.

4) Реализация для плотных графов

Проблема: при m ≈ n^2 списки смежности занимают много памяти; перебор инцидентных ребер может быть дорогим.Подходы:
битовые векторы $bitset/SIMD$ для строк матрицы смежности: операции удаления/сканирования ускоряются битовыми операциями.представление матрицей смежности если n достаточно мало $памятьO(n^2)$.альтернативная стратегия: работать с дополнительной структурой «флаг вершины в покрытии», при выборе вершины обходить соседей; при плотном графе обходы дороги, но бит-представления помогают.Для плотных графов иногда выгодно рассмотреть дополнение и задачи, связанные с независимым множеством: максимальное независимое множество в плотном графе обычно мало, что может упростить ветвление/ограничение в точных алгоритмах.

5) Практические оптимизации и предобработка

Удаление изолированных вершин $ониневлияют$.Правило для вершин степени 1: если v имеет единственного соседа u, то безопасно включить u в покрытие $иудалитьуиегоребра$.Краун-редукция, foldings и другие kernelization-правила значительно уменьшают граф перед основным алгоритмом $особеннополезнодляFPT/точныхметодов$.Сначала запустить быстрое эвристическое правило (например, степень>threshold), затем локальный поиск / LP на остатке.

6) Когда выбирать точный, эвристический или аппроксимационный алгоритм — критерии

Требуется ли гарантия качества?
Да, и допускается фактор 2 $илистрогоеверхнееограничение$ → используйте 2-аппрокс $максимальноепаросочетаниеилиLP-округление$.Нужна гарантированная близость к OPT лучше 2 — для больших общих графов это NP-трудно; если размер покрытия k мал, используйте FPT/точные методы.Размер графа и плотность:
Малые графы $n\le несколькодесятков—сотен$: можно применять точные методы $branch-and-bound,ILP$.Средние по размеру $несколькотысячвершин,mумеренное$: ILP/LP с хорошими предобработками или FPT, если ожидается small k.Очень большие разреженные графы $n,mдомиллионов$: эвристики и простые аппрокс $максимальноесовпадение$ — за скорость и память.Очень плотные графы: возможно выгоднее использовать битовые представления, LP/ILP $еслиnневелик$, или предобработку, чтобы уменьшить граф.Время/память/ресурсы:
Ограниченные ресурсы → простые жадные/streaming алгоритмы.Доступен кластер/распределённая обработка → распределённый maximal matching.Нужна воспроизводимость/объяснимость: аппрокс-алгоритмы и формальные редукции лучше, эвристики с рандомизацией могут давать разный результат.Зависимость от параметра k:
Если ожидается, что OPT = k относительно мал, применяют FPT-алгоритмы $вероятноэффективныхотябыдляk\le 50–100взависимостиотреализации$.

7) Рекомендации по выбору в типичных сценариях

Нужна быстрая грубая гарантия качества на больших графах: используйте алгоритм «выбрать произвольное ребро — добавить оба конца» $2-approx$.Хотите лучшее практическое качество без строгих гарантий: greedy by degree + локальный поиск, возможно повторённый с рандомизацией.Нужен $почти$ оптимум для умеренных n: LP-решатель или ILP $CPLEX/Gurobi$ с kernelization.OPT мал и нужен точный ответ: FPT/branch & bound с редукциями.В распределённой/streaming среде: алгоритмы для максимального matching/streaming 2-approx.

8) Заключение

Простейший и надежный выбор для больших задач — алгоритм на основе максимального совпадения $pickedge,takebothendpoints$ — простая реализация, O$m$ времени и строгая гарантия 2·OPT.Для лучшего практического качества сочетайте предобработку $правилаудаления$, LP-округление и локальный поиск; для маленьких или параметрически «малых» случаев — точные или FPT-алгоритмы.Улучшение гарантии ниже 2 в общем графе — сложная теоретическая задача; в практике стоит сочетать предобработку, точные методы на ядре и эвристики.

Если нужно, могу:

Привести готовую реализацию на C++/Python для разреженных или для битовых матриц $плотныеграфы$.Описать набор kernelization-правил и их сложность/эффект.