Вершинное покрытие и деревья поиска

Ключевые слова и синонимы

Ветвление и поиск; ветвление и границы

Постановка задачи

Задача о вершинном покрытии является одной из шести базовых NP-полных задач по классификации Кэри и Джонсона [7]. Это означает, что она не может быть решена за полиномиальное время, если только не верно соотношение P = NP. Однако NP-полнота задачи не устраняет необходимости в ее решении, поскольку она имеет фундаментальную значимость и широкий круг приложений.

Один из подходов к решению заключается в разработке параметризованных алгоритмов, вычислительная сложность которых выражается через размер входных данных и значение параметра. Этот подход был основан на наблюдении, заключающемся в том, что во многих приложениях экземпляры задачи ассоциированы с параметрами малой величины. Учитывая это благоприятное обстоятельство, можно найти эффективное и практичное решение NP-полной задачи.

Формальное определение задачи выглядит следующим образом. Пусть 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]\displaystyle{ k’ \le k \; }[/math], такой, что G' имеет вершинное покрытие из k' вершин в том и только том случае, если G имеет вершинное покрытие из k вершин. В классической работе Немхаузера и Троттера [9] был получен следующий результат, относящийся к кернелизации.

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

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

Свертка

Предположим, что v – вершина степени 2 в графе G, имеющая двух соседей u и w, не являющихся смежными друг с другом. Построим новый граф G' следующим образом: удалим все вершины v, u и w и введем новую вершину [math]\displaystyle{ v_0 \; }[/math], смежную со всеми оставшимися соседями вершин u и w в графе G. В таком случае говорится, что граф G' был получен из графа G в результате свертки вершины v. Для технологии свертки был получен следующий результат.

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

Операция свертки позволяет уменьшить значение параметра k без применения ветвления. Такие операции оказались весьма эффективными для разработки экспоненциальных по времени алгоритмов решения задачи о вершинном покрытии. Недавно было предложено расширение операции свертки, допускающее применение к множеству из нескольких вершин графа [6].

Ветвление и поиск

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

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

[math]\displaystyle{ T(k) = T(k - c_1) + T(k - c_2) + ... + T(k - c_b) \; }[/math]

Для решения этого рекуррентного соотношения положим [math]\displaystyle{ T(k) = x^k \; }[/math], после чего оно будет выглядеть следующим образом:

[math]\displaystyle{ x^k = x^{k - c_1} + x^{k - c_2} + ... + x^{k - c_b} \; }[/math]

Можно доказать [3], что вышеприведенное полиномиальное уравнение имеет единственный корень [math]\displaystyle{ x_0 \; }[/math] больше 1. Исходя из этого, получаем [math]\displaystyle{ T(k) = x^k_0 \; }[/math], что с точностью до полиномиального коэффициента задает верхнюю границу времени выполнения процесса ветвления и поиска на экземпляре (G, k).

Простейший случай соответствует выбору вершины v степени d > 0 в графе G. Пусть [math]\displaystyle{ w_1, ..., w_d \; }[/math] – соседи вершины v. Тогда либо v входит в вершинное покрытие C из k вершин, либо, если v не входит в C, то все ее соседи [math]\displaystyle{ w_1, ..., w_d \; }[/math] должны входить в C. Таким образом, получаем набор из двух подмножеств [math]\displaystyle{ C_1 = \{ v \} \; }[/math] и [math]\displaystyle{ C_2 = \{ w_1, ..., w_d \} \; }[/math], к которому может быть применен процесс ветвления и поиска.

Эффективность операции ветвления и поиска определяется эффективностью определения семейства подмножеств вершин. Интуитивно кажется, что чем больше размеры подмножеств вершин, тем эффективнее операция. Для повышения размеров этих подмножеств было приложено немало усилий, в основном связанных с очень сложным и утомительным анализом и перечислением комбинаторных структур графов. В недавней статье [3] было получено семейство из двух подмножеств [math]\displaystyle{ C_1 \; }[/math] и [math]\displaystyle{ C_2 \; }[/math] размером [math]\displaystyle{ c_1 = 1 \; }[/math] и [math]\displaystyle{ c_2 = 6 \; }[/math], соответственно, и другие семейства подмножеств вершин, которые оказались по меньшей мере не хуже указанных (техники кернелизации и свертки вершин играли большую роль в вычислении данных семейств). В результате был получен следующий алгоритм решения задачи о вершинном покрытии.

Теорема 3. Задача о вершинном покрытии может быть решена за время [math]\displaystyle{ O(kn + 1,2852^k) \; }[/math].

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

Применение

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

На основе параметризованного алгоритма, упомянутого в теореме 3, был разработан более быстрый алгоритм для решения другой важной NP-полной задачи – задачи о нахождении максимального независимого множества на разреженных графах [3].

Открытые вопросы

Главный нерешенный вопрос в этом направлении исследований заключается в том, насколько далеко по нему можно зайти. Точнее говоря, насколько маленькой может быть константа c > 1, чтобы алгоритм решения задачи о вершинном покрытии имел время выполнения [math]\displaystyle{ O(c^k n^{O(1)}) \; }[/math]? Более тщательный анализ комбинаторных структур графов позволяет надеяться на некоторое улучшение текущей наилучшей верхней границы [4]. Некоторые недавно разработанные техники [6] также обещают улучшить значение верхней границы. С другой стороны, известно, что константа c не может быть произвольно близкой к 1, за исключением определенных, редко встречающихся в теории сложности случаев [8].

Экспериментальные результаты

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

См. также

• Редукция данных для доминирования в графах
• Локальные аппроксимации задач упаковки и покрытия
• Алгоритмы локального поиска для kSAT
• Кернелизация вершинного покрытия

Литература

1. Abu-Khzam, F., Collins, R., Fellows, M., Langston, M., Suters, W., Symons, C.: Kernelization algorithms for the vertex cover problem: theory and experiments. Proc. Workshop on Algorithm Engineering and Experiments (NLENEX), pp. 62-69. (2004)

2. Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.: Solving large FPT problems on coarse grained parallel machines. J. Comput. Syst. Sci. 67,691-706 (2003)

3. Chen, J., Kanj, I A, Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41, 280-301 (2001)

4. Chen, J., Kanj, I A, Xia, G.: Improved parameterized upper bounds for vertex cover. In: Lecture Notes in Computer Science (MFCS 2006), vol. 4162, pp. 238-249. Springer, Berlin (2006)

5. Fellows, M.: Parameterized complexity: the main ideas and some research frontiers. In: Lecture Notes in Computer Science (ISAAC 2001), vol. 2223, pp. 291-307. Springer, Berlin (2001)

6. Fomin, F., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O(2°.288n) independent set algorithm. In: Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA 2006), pp. 18-25(2006)

7. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)

8. Impagliazzo, R., Paturi, R.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512-530 (2001)

9. Nemhauser, G.L., Trotter, L.E.: Vertex packing: structural properties and algorithms. Math. Program. 8, 232-248 (1975)

10. Roth-Korostensky, C.: Algorithms for building multiple sequence alignments and evolutionary trees. Ph. D. Thesis, ETH Zurich, Institute of Scientific Computing (2000)

11. Stege, U.: Resolving conflicts from problems in computational biology. Ph.D. Thesis, ETH Zurich, Institute of Scientific Computing (2000)