некоторой полиномально разрешимой задаче, связанной с ориентированными графами.)

36.4. NP-полные задачи

В настоящее время известно много NP-полных задач, связанные с самыми разными областями математики и информатики: логикой, теорией графов, компьютерными сетями, множествами и разбиениями, расписаниями, математическим программированием, алгеброй и теорией чисел, играми и головоломками, оптимизацией программ и т.д. и т.п.

В этом разделе мы докажем NP-полноту нескольких задач о графах и множествах с помощью метода полиномиального сведения.

Связь между этими задачами показана на рис. 36.11; стрелки означают сводимость за полиномиальное время (CIRCUIT-SAT сводится к SAT и т.д.) Доказав (в теореме 36.7) NP-полноту задачи SAT, с помощью этих сведений мы убеждаемся в полноте всех перечисленных на рисунке задач.

36.4.1. Задача о клике

Кликой (clique) в неориентированном графе G = (V, Е) называется подмножество вершин V с V, каждые две из которых соединены ребром графа. Другими словами, клика - это полный подграф графа G. Размером (size) клики называется число содержащихся в ней вершин. Рассмотрим оптимизационную задачу: определить максимальный размер клики в данной графе. Её называют задачей о клике (clique problem). Соответствующая задача разрешения формулируется так: даны граф G и число к; требуется установить, есть ли в графе G клика размера к. Формально говоря,

CLIQUE = {(G, к) : в графе G есть клика размера к}.

Как всегда, мы можем перебрать все подмножества размера к в V и проверить, есть ли среди них клика. Для этого требуется Q(k2-Cy) действий (V - число вершин в графе). При любом фиксированном к эта величина полиномиально зависит от размера графа G. Однако в общей постановке задачи к может быть любым числом, не превосходящим \V\, и алгоритм не является полиномиальным. Полиномиального алгоритма скорее всего просто нет, поскольку имеет место следующая Теорема 36.11

Задача CLIQUE является NP-полной. Доказательство

Сначала убедимся, что CLIQUE £ NP. В самом деле, в качестве

36.12 Граф. соответствующий формуле р> = С\ А С2 Л Сз, где С\ = х\\/-1Ж2\/-1Жз, С2 = -1Ж1\/ж2\/жз, Сз = х\\/х2\/хз при сведении 3-CNF-SAT к задаче о клике. Выполняющий набор (х\ = О, Ж2 = 0, жз = 1) выполняет С\ за счёт х2, а Сг и Сз за счёт Ж3. Соответствующие вершины показаны светло-серым и образуют клику.

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

Для доказательства NP-трудности задачи CLIQUE покажем, что 3-CNF-SAT m athrtoPCLIQUE. На первый взгляд это кажется странным - пропозициональные формулы никак не связаны с графами и кликами - но на самом деле сведение построить легко

Сводящий алгоритм получает формулу из класса 3-CNF, выполнимость которой нужно проверить (т.е. свести к задаче о клике). Пусть дана формула

(p = C1AC2A...ACkl

где каждая подформула Сг есть дизъюнкция трех разных литералов I[, lj и lj. Построим граф G = (V, Е), который содержит клику размера к, если и только если формула формула р> выполнима.

Для каждой дизъюнкции Gr = (1V/2V/3) из формулы р> нарисуем три вершины v[, uJJ, v3- Таким образом, граф G будет содержать Зк вершин. (Забегая вперёд, можно сказать, что будущая клика будет образована истинными членами дизъюнкций.) Пока что опишем рёбра графа: две вершины v\ и Vs- соединены ребром в графе G, если выполнены следующие условия:

v\ и Vj принадлежат разным тройкам (г ф s);

литералы /[ и которые соответствуют данным вершинам, совместны (are consistent), то есть не являются отрицаниями друг друга.

Граф G легко построить по формуле р> за полиномиальное время. На рис. 36.12 показан граф, соответствующий формуле

ср = (ж! V -1Ж2 V ->жз) Л (-1Ж1 V ж2 V ж3) Л (ж! V ж2 V ж3).

Покажем, что описанное преобразование действительно является сведением. Сначала предположим, что формула р> имеет выполняющий набор. Тогда каждая дизъюнкция С; содержит хотя бы один истинный литерал; выберем один из таковых (для каждой дизъюнкции). Отметим соответствующие выбранным литералам вершины v\ графа G. Мы утверждаем, что к отмеченных вершин образуют клику. Действительно, два отмеченных литерала совместны, так как оба истинны на одном и том же выполняющем наборе (и потому не могут быть отрицаниями друг друга).

Обратно, пусть в графе G есть клика V размера к. В каждой тройке вершины не соединены ребрами друг с другом, поэтому клика V содержит ровно по одной вершине из каждой тройки. Рассмотрим соответствующие литералы и объявим их истинными. Совместность литералов гарантирует, что для этого не придётся объявлять переменную одновременно истинной и ложной. Если после этого значения некоторых переменных еще не определены, выберем их произвольно. Получим набор значений переменных, который будет выполняющим, так как в каждой из дизъюнкций есть хотя бы один истинный член.

36.4.2. Задача о вершинном покрытии

Множество вершин V с V графа V = (V, Е) называется вершинным покрытием (vertex cover) графа, если у любого ребра графа хотя бы один из концов входит в V. Если считать, что вершина «покрывает» инцидентные ей рёбра, то вершинное покрытие графа G - это множество вершин, которые покрывают все его рёбра. Размером (size) вершинного покрытия называется число входящих в него вершин. Например, граф рис. 36.13 (Ь) имеет вершинное покрытие {w, z} (размера 2).

Задача о вершинном покрытии (vertex-cover problem) требует указать минимально возможный размер вершинного покрытия для заданного графа. Как обычно, мы перейдём от задачи оптимизации к задаче разрешения и будем спрашивать, имеет ли данный граф вершинное покрытие данного размера. Соответствующий язык таков:

VERTEX-COVER = {(G,k) : граф G имеет вершинное покрытие размера Теорема 36.12

Задача VERTEX-COVER является NP-полной. Доказательство

Сначала убедимся, что данная задача принадлежит классу NP. В самом деле, в качестве сертификата годится само вершинное покрытие (легко проверить, что оно имеет требуемый размер и что оно действительно является покрытие, просмотрев все рёбра).

Чтобы доказать, что задача VERTEX-COVER является NP-трудной, сведём к ней задачу о клике. В доказательстве используется понятие дополнения графа. Пусть дан неориентированный граф G = (V,E). Его дополнением (complement) назовём граф G = (V,E), где Е = {(и, v) : (и, v) Е}. Другими словами, граф G имеет те же вершины, что и граф G, а рёбра соединяют те пары вершин, которые не были соединены ребром в графе G. На рис. 36.13 показаны пример графа и его дополнения, появляющиеся при сведении задачи CLIQUE с задаче VERTEX-COVER.