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

На последнем этапе выделим из ипиз,..., и„группу из и — 1 вершин и соединим ее с новой вершиной (степени и — 1). Заметим, что после добавления новых вершин степени к вершины ам из,..., и„имеют степень не более й — 1, в частности, в заключительном графе С„они имеют степень не более и — 2. Поэтому "жадный" алгоритм, примененный к 0„, сначала выберет добавленную вершину степени и — 1, затем [после удалеюы этой вершины и покрываемых ею ребер) выберет все добавленные вершины степени и — 2, затем все добавленные вершины степени и — 3 и т.д. На последнем этапе он выберет все добавленные вершины степени 2. Таким образом -=[-:) [и [..,1.

[-,-) [-.-) (.,-)= /1 =п~ — + — +..+ — — [и — 2) > [2 3 и — 1/ п ~1 > п~ -Нт — и = п[1пп — 1п2) — п. С другой стороны множество 1ип ии, .., и„) является вершинным по- крытием в С„. Поэтому Гь„, < и и Р > п(1пп — 1п2 — 1) > Г (!пп — 1п2 — 1). Определение. Пусть дана задача оптимизации с фушсционалом Г. Алгоритм для этой задачи называется г- приближенным, если всегда ! ралг ~ют ! где Г „и гь„, — значение функционала, выдаваемое алгоритмом, и оптимальное значение. Если дана задача минимизации и Р > 0, то указанное неравенство эквивалентно неравенству:Р ( (1+ г)Р Следствие.

Жадный алгоритм для МВП не являетсг г-приближенным ни при каком фиксированном г. Спедующгя теорема показывает, что теоретически "жадная" стратегия дпя задачи МВП не яапяется хорошей. Теорема 5.3. Лля задачи МВП сушгстпвуетп 1-приближенный алгоритпм с полиномиальной сложностью. Показательство. Рассмотрим следующий алгоритм. Пусть дан граф С = Я, Е).

Будем формировать верпхиное покрытие А. Возьмем любое ребро еь = (оп из) и вкпючюл оь и ог в А. Выбросим из графа С вершины о~ и оз и все ребра, которые ими покрываются. В полученном графе Сь опять возьмем любое ребро ез = (оз, ол), добавим оз и о4 в А и удаавм из Сь вершины оз и сч и все покрываемые ими ребра. Процесс закончим, когда будут удалены все ребра.

Легко понять, что этот алгоритм можно реализовать с попиномиапьной сложностью. Также по построению очевидно, что полученное множество вершин А покрывает все ребра. Пусть в процессе алгоритма выбирались ребра еь ег,..., еь. Тогда )А~ = 2к. С другой стороны ребра еь, ег,..., еь не имеют общих вершин и, следовательно, любое вершинное покрытие должно содержать не менее й вершин (чтобы покрыть ем ез,..., гь).

Таким образом Е„к )~ й и Рьг„— — ~А~ ( 2Г„. Теорема доказана. Возникает вопрос, а нельзя ци для задачи МВП построить не прибпиженный, а точный алгоритм с попиномиапьной сложностью. Вьппе была доказана МР-полнота задачи о вершинном покрытии (ВП), где по заданному графу С и числу ?с требуется выяснить, есть пи в графе С вершинное покрытие мощности не более й. Теорема 5,4. Если для задачи МВП сутествугт алгоритпм с полиномиальной сложностпью, то и для задачи ВП существует алгоритм с полиномиальной сложностью.

Доказательство. Пусть алгоритм Н решает задачу МВП за попипомиапьное время и пусть в задаче ВП заданы граф С и число ?с. Применяем к графу С алгоритм Н н получаем т — минимапьную мощность вершинного покрытия в С. Если т < lс, то ответ в задаче ВП "да", иначе ответ "нет". Получаем попиномиальный алгоритм для задачи ВП. Замечание. Если дця задачи ВП существует алгоритм Н с полиномиавьной сложностью и в графе С и вершин, то, применяя алгоритм Н к нарам (С, О), (С, 1),..., (С, и — 1), можно за полиномиапьное время определить мощность мивнмапьного вершинного покрытия, однако не ясно, как найти само минимальное вершинное покрытие. Определение. Задачу оптимизации будем называть ФР-трудной, если из существования алгоритма попвнам надькой сложности дпя нее следует существование алгоритма попиномиэльной сложности дпя некоторой ФР-полной задачи (и,спедоватепьно, дпя всех задач из ХР).

Следствие. Задача МВП валяется ЛР-трудной. Следствие. Если Р ф МР, то для задачи МВН не существует алэоритма с полиномиальной сложностью. 5.3. Задача коммивояжера Вьппе мы получили условный результат о трудности нахождения точного решения задачи МВП. Здесь мы покажем, что такие условные отрицатепьные результаты можно попучать и дпя нахождения прибпижевных решений.

Напомним, что цикл в графе называется гамильтоновым, если он проходит через каждую вершину ровно 1 раз. Вьппе было показано, что задача о существовании в графе гамипьтонова цикла (ГЦ) является МР-попкой. Задача коммивояжера (ЗК). Вход: полный граф К„, в котором каждому ребру е = (иной) сопоставпен вес д(е) = д(оь и,) ) О. При этом будем счвтать, что все д(е) — пепые числа и длина входа включает в себя суммарную двину двоичного представления всех а(е).

'Требуется: найти гамильтонов цикл в К„с мивимэльной суммой весов ребер. 'Теорема 5.5. ЗК валяется ХР-трудной. Локаэательство. Пусть существует алгоритм Н дпя ЗК со сложностью, попиномиапьно зависящей от длины входа. Пусть дан граф С = (У, Е) с и вершинами и спрыпивается, есть пи в С гамильтонов цикл. Пусть У = (опия,..., и„).

Построим полный граф К„на множестве вершин У и зададим веса сведующим образом: (1, если (сьо,) б Е, д(оно ) = (2, если (ои о-) ф Е. Применим алгоритм Н дпя ЗК к графу К„с этими весами. Если получим дпя ЗК, что Р йь = и, то в С существует гамильтонов 70 ц икл, иначе в С не существует гамильтонова цикла. Таким образом, получаем алгоритм для задачи о гамильтоновом цикле (ГЦ).

Поскольку в С меньше, чем пз ребер, то суммарная длина двоичной записи всех весов не превосходит сп, где с — некоторая константа, то есть г длина входа для Н не превосходит полинома от п. Так как Н— цолиномиальный (от длины входа) алгоритм, то построенный нами алгоритм для ГЦ имеет полнномиальную от и сложность. Таким образом вз существования алгоритма с полиномиальной сложностью для ЗК вытекает существование агоритма с полиномиельной сложнотью для ГЦ. Поскольку задача ГЦ является ФР-полной, то получаем, что задача ЗК является ФР-трудной. Теорема 5.6.

Если Р ф МР, то ни для какого сколь угодно большого постоянного числа е не су~цестпвует е-приближенного алгоритма для ЗК с полиномиальной сложностью. доказательство. Допустим, что существует е н существует е-приближенный алгоритм Н с полиномиальной сложностью для ЗК. Построим тогда алгоритм с полнномиальной сложностью для ГЦ. Пусть дан граф С = (У,Е) с и вершинами. Построим полный граф К„= (У, Е') и для всех е б Е' положим 1, если е й Е, д(е) = (3+ еп), если е ф Е. Применим к К„с весами д алгоритм Н. Пусть алгоритм Н находит гамильтонов цикл с суммарной длиной Рл. Лемма 5.1. Если в графе С есть гамильтонов цикл, то Рн ( п(1+е). Если в графе С нет гамильтонова цикла, то Рн ~ п(1+е)+1.

Доказательство. Если в С есть гамильтонов цикл, то в ЗК для К„с весами д будет Рак = и. Так как Н является е-приближенным алгоритмом для ЗК, то Рд ( Р (1+ е) = п(1+ е). Если в С нет гамильтонова цикла, то любой гамильтонов цикл содержит хотя бы одно ребро с весом [3+ еп) и и — 1 ребер с весом не менее 1. Таким образом, суммарный вес любого гамильтонова пекла не меньше чем и — 1+ 2+ сп = п(1+ е) + 1. Лемма 5.1 показывает, что по результату работы алгоритма Н можно определить, есть лн в С гамильтонов цикл. Таким образом, мы получаем алгоритм Нь для задачи ГЦ. Оценим время его работы.

Дивна двоичного представления каждого веса д(е) не превосходит с)ойз и, где с — некотоРае константа, и количество весов меньше, чем пз. Поэтому длина входа для алгоритма Н не превосходит полинома от п. Поскольку время работы Н зависит полнломиально от длины входа, то общее время работы алгоритма Н, не превосходит полинома от п. В результате мы получаем, что если существует в-приближенный алгоритм Н с полиномиальной сложностью для ЗК, то существует алгоритм с полиномиальной сложностью для задачи ГЦ. Но задача ГЦ 1ь'Р-полна.

Тогда получаем, что Р = 14Р. Теорема 5.6 доказана. Во многих практических задачах веса удовлетворяют естественному ограничению, называемому неравенством треугольника: Ы(оьо-) < И(оьоь) + о(оь,о ) для всех различных ь, 1, й. Будем говорить, что дана задача коммивояжера с неравенством треугольника (ЗКНТ), если на вход поступают только веса, удовлетворяющие нервзеству треугольника. Теорема 5.7.

ЗКНТ являетсв ХР-тпрудной. Для доказательства этой теоремы полностью проходит доказательство теоремы 5.5. Достаточно только отметить, что набор весов, который строится в этом доказательстве, удовлетворяет неравенству треугольника. Теорема 5.8. Яля ЗКНТ существует 1-приближснный алгоритм с полиномиольной сложностью. доказательство. Мы должны построить алгоритм Н для ЗКНТ такой, что всегда Рл < 2.1"~. Применим к заданному графу К„с весами о' алгоритм с полиномиальной сложностью для построения кратчайшего остовного дерева (см.