Вершинное покрытие и деревья поиска: различия между версиями

Формальное определение задачи выглядит следующим образом. Пусть G – неориентированный граф. Подмножество C вершин графа G является вершинным покрытием G, если хотя бы одна конечная точка каждого ребра G принадлежит к C. Пример (параметризованной) задачи о вершинном покрытии представляет собой пару (G, k), где G – граф, а k – целочисленный параметр; в задаче требуется определить, имеет ли граф G вершинное покрытие из k вершин. Наша цель заключается в разработке параметризованных алгоритмов с временем выполнения O(f(k)p(n)) для нахождения вершинного покрытия, где p(n) – полином более низкой степени от размера входного графа n, а f(k) – неполиномиальная часть, являющаяся функцией от параметра k и независимая от n. Ожидается, что неполиномиальная функция f(k) будет насколько возможно малой. Такой алгоритм будет эффективным на практике, если параметр k будет малым. Следует отметить, что за исключением редко встречающихся в теории сложности случаев функция f(k) является по меньшей мере экспоненциальной относительно параметра k [8].

Предположим, что (G, k) – экземпляр задачи о вершинном покрытии, где G – граф, а k – параметр. Операция кернелизации применяет к экземпляру (G, k) подпрограмму обработки с полиномиальным временем выполнения, которая строит еще один экземпляр (G’, k’), где G’ – граф меньшего размера (ядро), а <math>k’ \le k \;</math>, такой, что G’ имеет вершинное покрытие из k’ вершин в том и только том случае, если G имеет вершинное покрытие из k вершин. В классической работе Немхаузера и Троттера [9] был получен следующий результат, относящийся к кернелизации.

Теорема 1. Существует алгоритм решения задачи о вершинном покрытии с временем выполнения <math>O(kn + k^3) \;</math>, который для экземпляра (G, k) строит еще один экземпляр задачи (G’, k’), где граф G’ содержит не более 2k’ вершин, а <math>k’ \le k \;</math>, такой, что граф G имеет вершинное покрытие из k вершин в том и только том случае, если граф G’ имеет вершинное покрытие из k’ вершин.

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

Предположим, что v – вершина степени 2 в графе G, имеющая двух соседей u и w, не являющихся смежными друг с другом. Построим новый граф G’ следующим образом: удалим все вершины v, u и w и введем новую вершину v’, смежную со всеми оставшимися соседями вершин u и w в графе G. В таком случае говорится, что граф G’ был получен из графа G в результате свертки вершины v. Для технологии свертки был получен следующий результат.

Теорема 2. Пусть G’ – граф, полученный из графа G в результате свертки вершины v второй степени, два соседа которой не были смежными друг другу. Тогда граф G имеет вершинное покрытие из k вершин в том и только том случае, если G’ имеет вершинное покрытие из k-1 вершины.

Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство <math>\{ C_1, ..., C_b \} \;</math> подмножеств графа G (где для каждого i подмножество <math>C_i \;</math> имеет <math>c_i \;</math> вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств <math>C_i \;</math> существует вершинное покрытие из k вершин для G, содержащее все вершины из <math>C_i \;</math>. После этого можно построить семейство экземпляров меньшего размера <math>(G_i, k_i) \;</math>, где 1 < i < b; ki = k — ci, а <math>G_i \;</math> получается из G путем удаления всех вершин, входящих в <math>C_i \;</math>. Отметим, что исходный граф G имеет вершинное покрытие из k вершин в том и только том случае, если один из меньших экземпляров <math>(G_i, k_i) \;</math> графа <math>G_i \;</math> имеет вершинное покрытие из <math>k_i \;</math> вершин. Таким образом, процесс может быть разветвлен на b подпроцессов, каждый из которых на меньшем экземпляре задачи <math>(G_i, k_i) \;</math> рекурсивно выполняет поиск вершинного покрытия из <math>k_i \;</math> вершин для графа <math>G_i \;</math>.

Пусть T(k) – количество листьев в дереве поиска для вышеописанного процесса ветвления и поиска на экземпляре задачи (G, k). Тогда операция ветвления дает следующее рекуррентное соотношение:

T(k - cb)

T(k) = T(k - c1) + T(k - c2)

Для решения этого рекуррентного соотношения положим T(k) = x, после чего оно будет выглядеть следующим образом:

Можно доказать [ ], что вышеприведенное полиномиальное уравнение имеет единственный корень X0 больше 1. Исходя из этого, получаем T(k) = xk, что с точностью до полиномиального коэффициента задает верхнюю границу времени выполнения процесса ветвления и поиска на экземпляре (G, k).

Простейший случай соответствует выбору вершины v степени d > 0 в графе G. Пусть w1,...,wd – соседи вершины v. Тогда либо v входит в вершинное покрытие C из k вершин, либо, если v не входит в C, то все ее соседи w1,...,wd должны входить в C. Таким образом, получаем набор из двух подмножеств C1 = fvg и C2 = fw 1..: ; wdg, к которому может быть применен процесс ветвления и поиска.

Эффективность операции ветвления и поиска определяется эффективностью определения семейства подмножеств вершин. Интуитивно кажется, что чем больше размеры подмножеств вершин, тем эффективнее операция. Для повышения размеров этих подмножеств было приложено немало усилий, в основном связанных с очень сложным и утомительным анализом и перечислением комбинаторных структур графов. В недавней статье [ ] было получено семейство из двух подмножеств C1 и C2 размеров c1 = 1 и c2 = 6, соответственно, и другие семейства подмножеств вершин, которые оказались по меньшей мере не хуже указанных (техники кернелизации и свертки вершин играли большую роль в вычислении данных семейств). В результате был получен следующий алгоритм решения задачи о вершинном покрытии.

Теорема 3. Задача о вершинном покрытии может быть решена за время O(kn+ 1:2852k).

Недавно коэффициент из теоремы 3 удалось улучшить, разработав алгоритм с временем выполнения O(kn + 1:2738k) [4].

Исследование параметризованных алгоритмов для решения задачи о вершинном покрытии стимулировал проект ETH Zurich «DARWIN» в области вычислительной биологии и вычислительной биохимии (см., например, [10, 11]). Многие вычислительные задачи этого проекта – такие как множественное выравнивание последовательностей [10] и разрешение биологических конфликтов [11] – могут быть сформулированы в виде задач о вершинном покрытии, в которых значение параметра в общем случае не превышает 100. Таким образом, алгоритм с временем выполнения O(kn + 1:2852k) оказывается весьма эффективным и практичным для решения подобных задач.

Главный нерешенный вопрос в этом направлении исследований заключается в том, насколько далеко по нему можно зайти. Точнее говоря, насколько маленькой может быть константа c > 1, чтобы алгоритм решения задачи о вершинном покрытии имел время выполнения O(ck nO(1))? Более тщательный анализ комбинаторных структур графов позволяет надеяться на некоторое улучшение текущей наилучшей верхней границы [ ]. Несколько недавно разработанных техник [ ] также обещают улучшить значение верхней границы. С другой стороны, известно, что константа c не может быть произвольно близкой к 1, за исключением определенных, редко встречающихся в теории сложности случаев [8].

Несколько групп исследователей реализовали на практике идеи, лежащие в основе алгоритма теоремы 3 или ее вариаций; в их числе можно упомянуть проекты «Параллельные методы в биоинформатике» Карлтонского университета [2], «Высокопроизводительные вычислительные системы» университета Теннесси [ ] и проект «DARWIN» Швейцарской высшей технической школы Цюриха (ETH Zurich) [10, 11]. Как было отмечено в [ ], эти разработки показали, что данный алгоритм и связанные с ним техники оказались весьма практичными для решения задачи о вершинном покрытии при значении параметра k, меньшем 400.

* ''[[Алгоритмы локального поиска для kSAT]]