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

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

Вернемся к формулировке задачи о независимом множестве, так как в нее будет добавлен один нюанс. Вспомните, что в графе G = (V, E) множество узлов S !Ξ V называется независимым, если никакие два узла в S не соединены ребром. Найти малое независимое множество в графе несложно (например, одиночный узел об- разует независимое множество); трудности возникают при поиске больших неза- висимых множество так как требуется построить большой набор узлов, в котором нет соседних узлов. Например, множество узлов {3, 4, 5} является независимым множеством размера 3 в графе на рис. 8.1, тогда как множество узлов {1, 4, 5, 6} является независимым множеством большего размера.

Рис. 8.1. Граф, для которого размер наибольшего независимого множества равен 4, а наименьшее вершинное покрытие имеет размер 3


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

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

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

Но также существует чуть менее очевидный обратный факт: если мы можем решить версию задачи о независимом множестве с проверкой условия для всех к, то мы также можем найти максимальное независимое множество. Для заданного графа G с n узлами версия с проверкой условия просто проверяется для каждого к; наибольшее значение к, для которого ответ будет положительным, является разме- ром наибольшего независимого множества в G. (А при использовании бинарного поиска достаточно применить версию с проверкой условия для О(log n) разных значений к.) Простая эквивалентность между проверкой условия и оптимизацией также встречается в задачах, которые будут рассматриваться ниже.

Теперь для демонстрации нашей стратегии по установлению связи между сложными задачами будет рассмотрена другая фундаментальная задача из тео- рии графов, для которой неизвестен эффективный алгоритм: задача о вершин- ном покрытии. Для заданного графа G = (V, E) множество узлов S ίΞ Vобразует вершинное покрытие, если у каждого ребра e E по крайней мере один конец принадлежит S.

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

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

Например, для графа на рис. 8.1 множество узлов {1, 2, 6, 7} является вершин- ным покрытием с размером 4, а множество {2, 3, 7} является вершинным покры- тием с размером 3.

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Йога на вершине холма
  2. Статья 422. Разглашение сведений военного характера, составляющих государственную тайну, или потеря документов или материалов, содержащих такие сведения
  3. 16.3. Перечни сведений, составляющих государственную тайну, и сведения, которые не могут относиться к государственной тайне
  4. II. 1. 1. Множества.
  5. II. 2. 2. От единого к множеству.
  6. Вариантов множество.
  7. Великое множество «я»
  8. II. 2. 7. Тетрады и дальнейшее разбиение множеств.
  9. Обида порождает множество болезней
  10. Если вы заблокированы” вас расстраивает сразу множество вещей.
  11. Статья 158. Фальсификация избирательных документов, документов референдума или фальсификация итогов голосования, предоставление ложных сведений в органов Государственного реестра избирателей или фальсификация сведений Государственного реестра избирателей
  12. 16.6. Рассекречивание сведений и их носителей