Первое сведение: независимое множество и вершинное покрытие

Задача о независимом множестве, представленная в числе пяти типичных задач в главе 1, послужит первым прототипным примером сложной задачи. Алгоритм с полиномиальным временем для нее неизвестен, но мы также не знаем, как доказать, что такого алгоритма не существует.

Вернемся к формулировке задачи о независимом множестве, так как в нее будет добавлен один нюанс. Вспомните, что в графе G = (V, E) множество узлов S Ӭ V называется независимым, если никакие два узла в S не соединены ребром.

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

В главе 1 была представлена задача нахождения наибольшего независимого множества в графе G. В контексте нашего текущего исследования, направленного на сводимость задач, намного удобнее работать с задачами, на которые можно ответить только «да/нет», поэтому задача о независимом множестве будет сформулирована следующим образом:

Для заданного графа G и числа k содержит ли G независимое множество с размером не менее k?

С точки зрения разрешимости с полиномиальным временем оптимизационная версия задачи (найти максимальный размер независимого множества) не так уж сильно отличается от версии с проверкой условия (решить, существует ли в G независимое множество с размером не менее заданного k, — да или нет). Зная метод решения первой версии, мы автоматически решим вторую (для произвольного k).

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

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

(А при использовании бинарного поиска достаточно применить версию с проверкой условия для O(log n) разных значений k.) Простая эквивалентность между проверкой условия и оптимизацией также встречается в задачах, которые будут рассматриваться ниже.

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

Для заданного графа G = (V, E) множество узлов S Ӭ V образует вершинное покрытие, если у каждого ребра e Ѯ E по крайней мере один конец принадлежит S.

Обратите внимание на один нюанс: в задаче о вершинном покрытии в данном случае вершины «покрывают», а ребра являются «покрываемыми объектами».

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

Для заданного графа G и числа k содержит ли G вершинное покрытие с размером не более k?

Мы не знаем, как решить задачу о независимом множестве или задачу о вершинном покрытии за полиномиальное время; но что можно сказать об их относительной сложности?

Сейчас мы покажем, что эти задачи имеют эквивалентную сложность; для этого мы установим, что Независимое множество ≤P Вершинное покрытие, а также Вершинное покрытие ≤P Независимое множество. Это напрямую вытекает из следующего факта.