В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 13

Если длина исходной 2-КНФ равна п,то в ней не более п переменных, из которых можно построить не более (2и+ 1) г дизъюнктов с одной или двумя переменными. Поэтому поиск новых резольвент будет повторяться не более (2п+ 1)з раз, при этом число просматриваемых пар дизъюнктов не превосходит (2п + 1)4. Отсюда следует утверждение леммы. Лемма 4.23.

Алэоритм праеилько решает задачу 2-ВЫП. Локаэательство. 1) Пусть К = Р1Рз . Р,— исходная 2-КНФ и пусть в конечной КНФ К' есть сомножитель О. По лемме 4.21 К = К' и, следовательно, К = О, то есть К невыполнима. 2) Пусть в конечной 2-КНФ К' нет О. По построению К' замкнута относительно взятия резольвент, то есть резольвента любых двух дизъюнктов из К' снова содержится в К'. Покажем, что любая 2-КНФ с такам свойством, не содержащая сомножителя О, выполнима. Показательство проведем индукпией по числу переменных и в 2-КНФ К'. Базис икдукиии: п = 1.

Тогда К' = х, или К' = хь В любом случае К' выполнима. Икдуктиекый переход. Пусть утверждение верно для 2-КНФ с п ( т переменными и пусть в К' имеется т переменных хь хз,..., х Тогда (х~п у ь1)(хт Ч ьз) '... ' (х~п '~ ьь)(хт у ~ь)(хт Ч ьз) (*и~~~,') Сь Сэ ... С„ глеь'„ь', — литералы, либо О, и Сь Сз ... ф— 2-КНФс переменными хъ хз,..., х ь замкнутая относительно взятия резолъвент. По предположению индукдии существует набор й = (аы ..,, о 1), на котором СгСэ....

С, равно 1. Если бы существовали Г, и ь' такие, что С,(й) = О и Гз(й) = О, то было бы и й(й) Ч ь' (й) = О. Но ь; Ч С'. — резольвента дкзъювктов хтпг; и х,„'~Р. Так как 2-КНФ К' замкнУта отеосительно взятия револьвент, то г, ь' ь",. содержится среди См Сз,..., С,. Но это противоречит тому, что С,(й) = 1 при всех о. Следовательно, либо все й(й) = 1, либо все г' (й) = 1. В первом случае К' выполнима на наборе (й, О), во втором — на наборе (й, 1). Теорема 4.15 полностью доказана.

4.8. Некоторые ИР-иолиые задачи на графах Теорема 4.16. Задача КЛИКА является МР-полкой. Локаэательство. Покажем, что задача ВЫП полиномиально сводится к задаче КЛИКА. Нля этого каждому слову а в алфавите языка ВЫП сопоставим пару у(а) = (С, х), где С вЂ” некоторый граф и й— натуральное число, так, чтобы в С существовала клика с Й вершинами тогда и только тогда, когда а — выполнимая КНФ. Если а — не КНФ, то положим <р(а) = (Сз, 2), где Сз — граф с 2 вершинами и без ребер (очевидно, в Сз нет клики с 2 вершинами). Пусть теперь а — КНФ и а = Р1 Рз ....Р„где Р, = 991Н8ьзн...'~1.

— дизъюнкты. Построим граФ ~р(а) = Сь — — (1г, Е) с множеством вершин Ъ' и множеством ребер Е следующим образом. Каждому литералу г<, нз а сопоставим вершину и;д и будем считать, что ( Еоз, иво,) б Е Е=Ь (91 М ' ) и (9Ы. Ф Сз,п) Положим й = з, где з — число дизъюнктов в а. Лемма 4.24. В Се есть клика с з еершинами тогда и только тогда, когда КНФ а выполнима.

Локазательстео. Пусть КНФ а принимает значение 1 на наборе й. Тогда Р,(б) = 1 для всех г. Спедовательно, дпя каждого 9 существует р; такое, что 9;д,. — — 1. Тогда среди 91 „992„...,9... нет противопопожных литералов. Поэтому любые вершины из о1 „оз,;,..., о,о соединюотся в Се ребром, то есть образуют клику с з вершинами. Обратно, пусть в графе Се есть клика с з вершинами о;,„„о„„;,..., и,,„,. Тогда ьь ьз,..., ь, все различны, то есть литералы днзьюнкт КНФ а, причем среди этих литералов нет противоположных.

Пусть хм хе...,х„— все переменные из а. Лля каждого 1с 'положим хь = 1, если литерал хь встречается в М, хь = О, если хь встречается в М, и хь — любое, если ни хы ни ххе нет в М. Тогда на построенном наборе сь все питерапы нз М обращаются в 1 и, следоватепьно, все дизъюнкты и вся КНФ а принимают значение 1, то есть КНФ а выполнима. Лемма доказана. Таким образом переход а -+ ьэ(а) является сведением задачи ВЫП к задаче КЛИКА.

Распознать, является пи а КНФ, и построить по а граф Се и число й можно за попнномиапьное время. Поэтому это попиномиапьное сведение. Так как задача ВЫП ХР-панна и КЛИКА е 1э'Р, то по теореме 4.13 получаем, что и задача КЛИКА АР-полна. Теорема 4.16 доказана. Задача о независимом множестве вершин (НМ). Вход: пара (С, й), где С вЂ” граф, й — натуральное число. Вопрос: существуют пи в С lс вершин, образующих независимое множество, то есть множество, в котором никакие вершины не соединевы ребром в С? Лемма 4.25. НМ Е МР. 59 Доказательстлво.

Сертификатом является само независимое множество М с к вершинами (если такое есть). Проверить, что М содержит ровно к вершин и является независимым, можно за полиномиальное время. Задача о вершинном покрытии (ВП). Вход: пара (С, 1с), где С вЂ” граф, 1с — натуральное число. Вопрос: существует ли в С множество М из /с вершин, образующих вершинное покрытие, то есть такое, что любое ребро из С имеет хотя бы один конец в Мт Лемма 4.26. ВПЕ ХР. Докаэатаельспсво.

Сертификатом является само вершинное покрытие М с к вершинами (если такое есть). Проверить, что М со. держит ровно к вершин и является вершинным покрытием, можно за полиномиальное время. Теорема 4.17. Задачи НМ и ВД А?Р-оолиьь Воказатпельстлво, Сопоставим паре (С, lс) пару (С, к), где С вЂ” граф, являющийся дополнением к С (то есть в С то же множество вершин У, что и в С, и две вершины соединяются ребром в С тогда и только тогда, когда они не соединяются ребром в С). При этом подмножество М С У является клихой с к вершинами в С тогда и только тогда, когда М является независимым множеством с к вершинами в С.

Получаем сведение (очевидно, полиномиэльное) задачи КЛИКА к задаче НМ. Так как задача КЛИКА ХР-лалла и НМ Е 1т'Р, то задача НМ ЖР-полная. Сопоставим паре (С, й) пару (С, л — к), где и = ٠— число вершин в графе С. При этом подмножество М С У является независимым множеством с к вершинами в С тогда и только тогда, когда У ~ М является вершинным покрытием с л — к вершинами в С. Получаем полиномиэльное сведение задачи НМ к задаче ВП. Так как задача НМ Ат Р-полная и ВП Е ХР, то и задача ВП ттт Р-полная.

Определение. Цикл в графе, проходящий через каждую вершину ровно 1 рэз, называется гамильтаоновьтм циклом. Гамильтионовой цепью называется незамхнутая цепь, проходящая через каждую вершину ровно 1 раз. Задача о гамильтоновом пикле (ГЦ). Вход: произвольный граф С. Волрост есть ли в С гамильтонов цикл? Лемма 4.27. ГЦ Е?7Р. Локазатаельство. Для данного графа С с и вершинами сертификатом является последовательность вершин (опон..., о„). Алгоритм проверки сертификата должен убедиться, что в этом списке столько же вершин, сколько в графе С, что все они различны и что для всех у = 1, 2,..., п — 1 в графе С есть ребро (о;, иль), а также есть ребро (о„, оь).

Все это можно выполнить за полиномиальное время. Теорема 4.18. Задача ГЦ МР-полна. Нонаэательство. Построим полиномиальное сведение задачи 3-ВЫП к задаче ГЦ. Рассмотрим 2 вспомогательных графа: сь-граф и 33-граф, изображенные на рис. 1 и 2, соответственно. Аь в, Ва Рис. 2 Рис, 1 Пусть а-граф (рис. 1) является подграфом некоторого графа С, причем с другими вершинами графа могут соелиняться только вершины Аь Аз, Вь Вг, и пусть в С сушествует гамильтонов цикл. Нетрудно проверить, что если этот цикл входит внутрь о-графа, то он обязан сразу обойти все внутренние вершины а-графа.

При этом, если он входит через вершину Аэ, то выходит обязательно через Вз и наоборот. Аналогично, если ои входит через Аи то выходит через Вз и наоборот. Поэтому условно можно считать, что а-граф имеет всего 2 ребра АэВь и АзВз и требуется, чтобы цикл проходил ровно по одному из них. Пусть ф-граф (рис. 2) является подграфом некоторого графа С, причем с другими вершинами графа С могут соединяться только вершины Р и 5. Если гамильтонов цихл входит в ~3-граф через Р или 5, то он должен сразу обойти все вершины этого 33-графа (и выйти через другую вершину пары Р, Я).

В 33-графе (рис. 2) 3 нижних ребра РЯ, ~Н и НЯ будем называть основными, а вершины Р и Я вЂ” граничными. Лемма 4.28. Не существует гамильтоновой цепи в (3-графе иэ вершины Р в вершину 5, проходящей по всем трем основным ребрам РЦ, Я)3,335. Юля любого другого подмножества основных ребер (включая пустпое подмножество) существует гамильтонова цепь иэ Р в Я, проходящая в точности по этому подмножеству основных ребер. Первая часть этой леммы очевидна, для доказательства второй части достаточно рассмотреть все возможные случаи и в каждом построить соответствующую гамильтонову цепь (постройте).

Пусть А — алфавит задачи 3-ВЫП. Каждому слову а к А' мы сопоставим граф С так, чтобы в С существовал гамильтонов цикл тогда и только тогда, когда а — выполнимая 3-КНФ. Если а й А' н а — не 3-КНФ, то сопоставим а граф 6 с двумя вершинами и 1 ребром. Очевидно, в нем нет гамильтонова цикла. Пусть теперь а = К = Рр Рз .... Р, — произвольная 3-КНФ с переменными хь хж, х„.

Пусть Нп Нм, Н, — р3-графы с граничными вершинами Р, 5., р' = 1, 2,..., в. Соединим ребрами вершины Я я Ррил для р' = 1, 2,..., в — 1. Полученный граф обозначим Сь Через Сз обозначим граф (точнее, мультиграф) с вершинами Сш Сп..., С„, в котором для каждого 1 = 1, 2,..., н есть 2 ребра (С, ь Ср) и нет других ребер. Вершину Рр графа Ср соединим ребром с Сб, а Яр соединим ребром с С„. Из двух ребер (С, ь Ср) одно сопоставим переменной х,, а другое — х,.

Первое обозначим е,'., второе еб. В каждом подграфе Н; основные РебРа РДр, Р~рНр, ЯрВр. сопоставим литеРалам 1 Мб З,брб днзъюнкта Р,. Пусть литерал х; встречается в к дизъюнктах Р и в подграфах Нр литералу х; соответствуют lс ребер.ем ем...,еь. Между ребром е," = (С; и С;), соответствующим хи и каждым из ребер ер, ез,..., еь вставим соединительные ребра так, чтобы образовалось к а-графов.

Так поступим для всех х;. Аналогично поступим для всех х; с заменой е,'. на ео. Полученный граф обозначнм Сб. Лемма 4.29. В Св есть гамильтонов цикл тогда и только тогда, когда КНФ К выполнима. Яоказательство. Пусть в Св существует гамильтонов цикл И~. По свойствам о-графа (см.выше) можно условно считать, гго гамильтонов цикл проходит ровно по одному из ребер АрВр или АзВз а-графа.

Следовательно, можно считать, что цикл И' сначала проходит по всем вершинам подграфа Сп потом по всем верпщнам подграфа Сз, при этом выполняется требуемое свойство для каждого бь-графа. Для каждой пары ребер еб, еР в Сз цикл ИР, очевидно, должен проходить ровно по одному из этих ребер. Пля каждого 1 положим х; = О, если И' проходит по ев, и х; = 1, если И' проходит по е,'. Полученный набор обозначим =р = ( рп..., 7„). Рассмотрим один вз подграфов Н; в Ср.