(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 15

Ш:!</<«},гдедалее,полагаем:Л - Ы / 1: 1 < К Ч I < / < « } ,G) ~ Gfi ■[/]'■ 1У— BUSj UCj .гдеВ = (btil}S ‘2 ~ ($ 2 [/]• lCi** {&[/]■.и!)};IЩ.Заметим, что каждая тройка из М есть элементмножества W Y X X Y, что и требовалось. Кроме того,посколькумножествоМсодержиттолько+ Зт 4 — 1 ) Тр0ек и множество М в терминахиндивидуальной задачи из 3-ВЫП определяется явнымобразом, легко видеть, что М может быть построено заполиномиальное время. Из комментариев, которымисопровождалось описание множества М, немедленно следует,что оно не может содержать трехмерного сочетания, еслинабор С невыполним.

Теперь необходимо доказать, чтосуществование выполняющего набора значений истинностидля набора дизъюнкций С влечет за собой существование в Мтрехмерного сочетания.Пусть t: {/—>{Т, F} - произвольный выполняющий наборзначений истинности для С. Построим трехмерное сочетаниеM t М следующим образом. Для каждой дизъюнкции с,еСрассмотрим некоторый литерал г>е1i ^ л} f) fy 5принимающий значение «истина» при отображении / (такое г,должно существовать, поскольку t выполняет с,). Затем по­ложимМгде G' — соответствующее подмножество множества G,выбранное так, что оно содержит все gi[k], g3[i<] и оставшиесяu,\J] и «,[/]. Нетрудно проверить, что такое множество G'всегда можно выбрать и что полученное в результатемножество W будет трехмерным сочетанием.Вместо задачи 3-С для доказательства результатов об NPполноте часто пользуются следующей, более общей и болеенаглядной, версией этой задачи.ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ (ТП-3)УСЛОВИЕ.

Задано конечное множествоX, такое, что \X\=3q, исемейство С трехэлементных подмножеств множества X.ВОПРОС. Верно ли, что семейство С содержит тонное покры­тие множествах, т. е. такое подсемейство C t С, что каждыйэлемент из X содержится ровно в одном элементе из С?Заметим, что любую индивидуальную задачу из 3-Сможно рассматривать как индивидуальную задачу из ТП-3,считая, что М состоит из неупорядоченных троек элементовмножества W u X и Y.

При этом трехмерные сочетания дляиндивидуальной задачи из 3-С взаимно однозначносоответствуютточнымпокрытиямсоответствующейиндивидуальной задачи из ТП-3. Таким образом, задача 3-Сесть ограниченная версия задачи ТП-3 и NP-полнота ТП-3следует из естественного сведения к ней задачи 3-С.ВЕРШИННОЕ ПОКРЫТИЕ И КЛИКАНесмотря на то, что задачи ВЕРШИННОЕ ПОКРЫТИЕ иКЛИКА при доказательстве результатов об NP-полнотеиспользуютсянезависимо,вдействительностионипредставляют собой всего лишь разные способы рассмотренияодной и той же задачи. Для того чтобы это понять, удобнорассмотреть их вместе с третьей задачей, которая называетсяНЕЗАВИСИМОЕ МНОЖЕСТВО.Независимым множеством в графе G - (V, Е)называется такое подмножество V’ из V, что для любых и, v еV, ребро {и, у} не принадлежит Е.

В задаче НЕЗАВИСИМОЕМНОЖЕСТВО для заданного графа G = (V, Е) иположительного целого числа J < \V\ спрашивается, верно ли,что G содержит независимое множество V такое, что | V'\>J.Легко убедиться, что независимые множества, клики ивершинные покрытия связаны между собой следующимобразом.Лемма 5.3. Для любого графа G(V,E) и подмножестваV'cz V следующие утверждения эквивалентны:(а) V'есть вершинное покрытие G;(б) V\V’есть независимое множество в G;(в) V\V' есть клика в дополнении CG графа G, гдеCG=(V,CE),CE={(u,v): u, v g Vк (u,v)i Е}Таким образом, эти три задачи можно рассматривать в не­котором смысле как различные версии одной и той же задачи.Более того, взаимосвязи между задачами, указанные в лемме5.3, делают тривиальным вопрос о сводимости между любымидвумя из них.Сведем, например, задачу ВЕРШИННОЕ ПОКРЫТИЕ кзадаче КЛИКА. Пусть G = ( V,E) и К < |Е| - произвольная ин­дивидуальнаязадачаизВП.Соответствующаяиндивидуальная задача из КЛИКИ получается, если взятьграф G и целое число J = | F) - К.Отсюда следует, что NP-полнота всех трех задач следуетиз NP-полноты любой из них.

Докажем, что задача ВЕРШИН­НОЕ ПОКРЫТИЕ NP-полна.Теорема 5.4. Задача ВЕРШИННОЕ ПОКРЫТИЕ NPполна.Доказательство. Легко видеть, что задача BHeNP. Этоследует из того, что недетерминированному алгоритму доста­точно угадать подмножество вершин и за полиномиальноевремя проверить, что это подмножество содержит хотя быодин конец любого ребра и имеет соответствующее числоэлементов.

Сведем задачу 3-ВЫП к задаче ВП. Пусть U = {uj ,Ui , ... , ип] и С={с/, С2 , ... , с,„} определяют произвольнуюиндивидуальную задачу из 3-ВЫП. Укажем граф G = (V, Е) иположительное целое число К< |Е| такие, что G имеет вер­шинное покрытие с числом элементов не более К тогда итолько тогда, когда выполним набор дизъюнкций С.Как и в предыдущем доказательстве, наша конструкциябудет составлена из нескольких компонент. В данном случаебудут присутствовать только компоненты набора значенийистинности и проверки выполнимости, дополненные неко­торымивспомогательнымиребрами,связывающимиразличные компоненты.

Для каждой переменной м,е U имеетсякомпонента Тi=(Vh Е,) набора значений истинности (здесьУ,={ц, йё,}, Ei~{{uh м,}}), т. е. Т, — это пара вершин,соединенных одним ребром. Заметим, что любое вершинноепокрытие должно покрыть ребро из Еь поэтому оно должносодержать по крайней мере одну из вершин щ или а , . Длякаждой дизъюнкции с,еС имеется компонента проверкивыполнимости Sf=(V'h Е '), состоящая из трех вершин и трехсоединяющих их ребер, образующих треугольник:у ;-К1Л. м л , аМ£ ;= { { « .№ « л л и м / ! . м л ) , ы и «з [/]}}.Отметим, что любое вершинное покрытие должно содержатьхотя бы две вершины из V', чтобы покрыть все три ребра изE'j. Связывающие ребра - это единственная частьконструкции, зависящая от того, какие литералы входят вдизъюнкции.

Их лучше всего рассматривать с точки зрениякомпонент проверки выполнимости. Для каждой дизъюнкцииcteC обозначим через х„ у„ z, три входящих в нее литерала.Тогда связывающие ребра, исходящие из Sh задаютсяследующим образом:Построение индивидуальной задачи из ВП будет закончено,если положить к = п+2т и G=(V,E), гдеНа рис. 5.3 приведен граф, соответствующийиндивидуальной задаче из 3-ВЫП, когда U {и/ , и2, из, и4} иС={{м/ , а з,, и2, а 4}}. Нетрудно видеть, что этуконструкцию можно осуществить за полиномиальное время.Поэтому достаточно показать, что С выполнима тогда итолько тогда, когда у G есть вершинное покрытие с числомэлементов не более К.Предположим вначале, что V'czF - вершинное покрытиеG и \V’\ < К. В силу сделанных выше замечаний, V’ должно со­держать по крайней мере одну вершину каждого 7} и хотя быдве вершины каждого S,. В совокупности это дает по крайнеймере п+2т=К вершин.

Поэтому V’ должно содержать ровноодну вершину каждого I) и ровно две вершины каждого S,.Таким образом, можно использовать пересечение V скомпонентами наборов значений истинности, чтобы получитьотображениеРис. 5.3 Индивидуальная задача из ВЕРШИННОЕ ПОКРЫТИЕ, ккоторойприводит индивидуальная задача из 3-ВЫП при U ~ { u i, и2 , 1 1 3 . 1 1 4 },С= {{г//, и3. го},{ U1 .U 2 , Kj}}. Здесь К=п+2т =&.t: U—*{Т, F}. Для этого положим t(u,)=Т, если u,eV, и t(u)= F,если a,eV . Для доказательства того, что этот набор значенийистинности выполняет каждую дизъюнкцию с,-С, рассмотримтри ребра подграфа Е"г Только два из них могут бытьинцидентны вершинам из V) n V’, поэтому одно из нихдолжно быть инцидентно вершине некоторого подграфа V,,принадлежащейтакжеV.Отсюда следует,чтосоответствующий литерал и, (или а ) дизъюнкции с,принимает значение «истина» при рассматриваемом наборезначений истинности t, и, следовательно, t выполняетдизъюнкциюПоскольку это утверждение имеет место длякаждой дизъюнкции с,еС, то отсюда следует, что t выполняющий набор значений истинности для С.Обратно, предположим, что t: U—>{T,F} - выполняющийнабор значений истинности для С.

Тогда соответствующеевершинное покрытие V’ содержит одну вершину из каждого 7}и две вершины из каждого S,. При этом вершиной из Г,принадлежащей V, будет и, (если t(u,)=T) или а , (если t(u,)-F).Поскольку t выполняет каждую дизъюнкцию с;, то это обеспе­чивает покрытие по крайней мере одного из трех ребер,принадлежащих множеству Е'). Следовательно, осталосьвключить в V концы оставшихся двух ребер из Е"принадлежащие подграфу S, (которые могут быть либоинцидентны, либо не инцидентны вершинам из компонентнаборов значений истинности) и при этом получится искомоевершинное покрытие.ГАМИЛЬТОНОВ ЦИКЛРанее мы видели, что к задаче ГАМИЛЬТОНОВ ЦИКЛ (ГЦ)может быть сведена задача распознавания КОММИВОЯЖЕР,поэтому NP-полнота последней задачи следует из NP-полнотызадачи ГЦ.