36.13

Сведение задачи CLIQUE к задаче VERTEX-COVER.

(a)Неориентированный граф G = (V, Е) и клика V = {и, v, х, у}.

(b)Его дополнение G, построенное сводящим алгоритмом, имеет вершинное покрытие V \ V = {w, z}.

Сводящий алгоритм получает на вход граф G и число к; вопрос состоит в том, есть ли в графе д клика размера к. Алгоритм строит граф G (дополнение графа G) и даёт на выходе пару (С, \V\ -к). Остаётся заметить, что граф G имеет вершинное покрытие размера \V\ - к тогда и только тогда, когда граф G имеет клику размера к (возможность выполнить это преобразование за полиномиальное время очевидна).

В самом деле, если есть клика размера к, то её дополнение образует вершинное покрытие графа G (любое ребро графа G отсутствует в графе G, поэтому один из концов этого ребра должен быть вне клики).

Напротив, если есть вершинное покрытие графа G размера \V\ - к, то его дополнение является кликой: если какие-то две вершины этого дополнения не связаны ребром в графе G, то они были бы связаны ребром в С, и это ребро не было бы покрыто.

Поскольку задача VERTEX-CLIQUE является КРполной, вряд ли для неё существует эффективный алгоритм. Однако, как мы увидим в разделе 37.1, существует эффективный алгоритм, дающий «приближённое» решение этой задачи - можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.

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

36.5.3 Задача о суммах подмножеств

В этом разделе мы рассмотрим ещё одну NP-полную задачу, на этот раз - арифметическую. Пусть даны конечное множество натуральных чисел S С N и число t £ N. В задаче о суммах подмножеств требуется выяснить, существует ли такое подмножество S С S, сумма элементов которого равна t. Например, если S = {1, 4,16, 64, 256,1040,1093,1284,1344} и t = 3754, то ответ будет положительным - можно взять S = {1,16, 64, 256,1040,1093,1284}.

Соответствующий язык таков:

SUBSET-SUM = {(S,t) : существует такое подмножество S С S, что t = s}.

sES

Напомним, что мы записываем числа в двоичной системе (представляя вход задачи в виде битовой строки).

36.14 Сведение задачи о вершинном покрытии к задаче о суммах подмножеств.

(a)Неориентированный граф G. Светло-серые вершины образуют вершинное покрытие {v\, v3, v4} размера 3.

(b)Матрица инцидентности этого графа. Светло-серые строки соответствуют вершинам покрытия.

(c)Соответствующий вход задачи о суммах подмножеств. Внутри рамки находится матрица инцидентности, Вершинное покрытие {t>i, г>з, u4} размера к = 3 соответствует подмножеству из светло-серых элементов {1,16, 64, 256,1040,1093,1284}, сумма которого есть 3754.

Теорема 36.13

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

Очевидно, эта задача принадлежит классу NP (сертификатом можно считать само подмножество S1).

Теперь покажем, что VERTEX-COVER Р SUBSET-SUM. Сводящий алгоритм преобразует вход (G, к) задачи о вершинном покрытии в пару (S,t) с таким свойством: в графе G существует вершинное покрытие размера к тогда и только тогда, когда в S найдется подмножество с суммой t.

Будем использовать представление графа G матрицей инцидентности. Пусть G = (V, Е) - неориентированный граф; мы считаем, что его вершинами являются числа 0,1, 2,... , \V\ - 1, а рёбрами - числа 0,1, 2,... , \Е\ - 1. Тогда матрицей инцидентности (incidence matrix) графа G будет \V\ X [/-матрица В, определяемая так:

Например, матрица инцидентности рис. 36.14 (Ь) соответствует графу рис. 36.14 (а).

Сводящий алгоритм получает на вход матрицу инцидентности В и число к. Требуется построить множество S и число t. Все числа будем записывать в системе счисления по основанию 4.

Множество S будет состоять из чисел двух типов: одни соответствуют вершинам графа, другие - его рёбрам. Каждой вершине г £ V ставится в соответствие число, которое записывается (в системе по основанию 4) и \Е\ так: сначала идёт единица, а потом г-ая строка матрицы инцидентности В = (68j) (рис. 36.14 (с)), то есть строка, соответствующая этой вершине. Каждому ребру j £ Е сопоставляется число ijj, запись которого содержит единственную единицу в позиции, соответствующей ребру г (т.е. число А3).

Остается указать число t. Старшие разряды числа t совпадают с записью числа к по основанию 4, а последующие \Е\ разрядов

1, если ребро j инцидентно вершине i 0, в противном случае.

t = к • 41 + 2 •4J-

Все построенные числа имеют двоичное представление полиномиального размера и строятся за полиномиальное время.

Теперь нужно проверить, что граф G имеет вершинное покрытие размера к тогда и только тогда, когда в S существует подмножество S с суммой t. Пусть дано вершинное покрытие V с V требуемого размера, содержащее вершины i\, i2, , ik- Включим в множество S числа, соответствующие этим вершинам. Тогда сумма элементов множества S, записанная по основанию 4, будет выглядеть так: в старших разрядах стоит число к, а во всех младших разрядах стоят цифры 1 или 2 (в зависимости от того, оба конца ребра вошли в вершинное покрытие или только один). Взяв те рёбра, у которых только один конец вошёл в вершинное покрытие и добавив соответствующие им числа в множество S, мы превратим единицы в двойки, то есть получим в сумме число t. (На рис. 36.14 (с) потребовалось добавить четыре строки Уо, У2, Уз, У4, чтобы обеспечить недостающие двойки в младших разрядах.)

Обратное рассуждение аналогично. Пусть имеется множество S, сумма элементов которого равна t. Это значит, что в младших разрядах суммы стоят двойки. Поскольку строки, соответствующие рёбрам, могут дать в каждом разряде максимум единицу, но никак не двойку, это значит, что недостающая единица приходит от «вершинных» строк. Следовательно, вершины, соответствующие входящим в S строкам, образуют вершинное покрытие. А старшие разряды гарантируют, что число вершин в этом покрытии равно к.

36.4.3. Задача о гамильтоновом цикле

Вернёмся к задаче о гамильтоновом цикле (HAM-CYCLE; мы говорили о ней в разделе 36.2). Теорема 36.14

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

Мы уже объясняли, почему эта задача принадлежит классу NP (гамильтонов цикл можно считать сертификатом).

Чтобы доказать NP-полноту задачи HAM-CYCLE, мы покажем, что 3-CNF-SAT m athrтоРНАМ-CYCLE. Другими словами, мы опишем алгоритм, преобразующий формулу р> из класса 3-CNF с переменными х\, х2,... , хп в граф G = (V, Е), который имеет гамильтонов цикл в том и только том случае, если если исходная

заполнены двойками. Более точно,