Аппроксимационные схемы для задач с планарными графами

Ключевые слова и синонимы: алгоритмы аппроксимации в планарных графах; подход Бэйкер; подход Липтона-Тарьяна

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

Многие NP-полные графовые задачи проще решить при помощи аппроксимации на планарных графах и их обобщениях. (Граф является планарным, если он может быть изображен на плоскости или сфере без пересечения дуг. Более подробно о других родственных классах графов см. двумерность). К примеру, в задаче нахождения максимального независимого множества нужно найти максимальное подмножество вершин графа, не порождающих дуг. Эта задача является неаппроксимируемой в графах общего вида с коэффициентом [math]\displaystyle{ n^{l- \epsilon} }[/math] для любого ε > 0, если только не окажется верным NP = ZPP (и неаппроксимируемой с коэффициентом [math]\displaystyle{ n^{l/2 - \epsilon} }[/math], если только не окажется верным P = NP); в то же время для планарных графов можно выполнить 4-аппроксимацию (или простую 5-аппроксимацию), взяв наибольший цветовой класс для раскраски вершин в 4 цвета (или, соответственно, в 5 цветов). Другая задача – нахождение минимального доминирующего множества – заключается в поиске минимального подмножества вершин, такого, что каждая вершина либо входит в подмножество, либо смежна с ним; эта задача неаппроксимируема для графов общего вида с коэффициентом ε log n для некоторого ε > 0, если только не окажется верным P = NP, однако в случае планарных графов возможно применение полиномиальной схемы аппроксимации (PTAS) – набора алгоритмов аппроксимации с коэффициентами (1 + ε) для всех ε > 0.

Для построения PTAS-схем для планарных графов и их обобщений применяются два основных подхода: подход с использованием сепараторов и подход Бэйкер.

Липтон и Тарьян [15, 16] ввели первый подход, основанный на планарных сепараторах. Первый шаг этого алгоритма заключается в нахождении сепаратора, состоящего из [math]\displaystyle{ O(\sqrt{n}) }[/math] вершин или дуг (где n – размер графа), удаление которых разделяет граф на два или несколько фрагментов, каждый из которых представляет собой константную компоненту, меньшую по размеру, чем исходный граф. Затем рекурсивное применение алгоритма к каждому полученному фрагменту позволит построить рекурсивное дерево сепараторов; процесс следует остановить, когда фрагменты будут иметь некоторый константный размер – к примеру, 1/ε. После этого для отдельных фрагментов задача может быть решена при помощи прямого перебора, и останется только объединить решения, протянув их вверх по рекурсивному дереву. Внесенная погрешность часто может быть ограничена по отношению к полному размеру всех сепараторов, который, в свою очередь, может быть ограничен ε n. Если отношение размера оптимального решения к n составляет не меньше некоторого константного множителя, этот подход часто приводит к схеме PTAS.

Подход с планарными сепараторами имеет два ограничения. Во-первых, он требует, чтобы отношение размера оптимального решения к n составляло не меньше некоторого константного множителя; в противном случае стоимость, внесенная сепараторами, может оказаться намного больше желаемого оптимального решения. Подобная граница может иметь место в некоторых задачах после усечения графа (нахождения ядра) – таких, как задача о независимом множестве, задача о вершинном покрытии и разные варианты задачи коммивояжера. Однако Гроу [12] утверждает, что для нахождения доминирующего множества «техники, основанные на теореме о сепараторах, неприменимы». Во-вторых, алгоритмы аппроксимации на основе планарных сепараторов часто оказываются непрактичными из-за больших константных множителей. Например, чтобы получить коэффициент аппроксимации 2, требуется произвести исчерпывающее решение для графов, имеющих 2 в степени [math]\displaystyle{ 2^{400} }[/math] вершин.

Бэйкер [1] предложила подход, способный справиться со вторым ограничением; он до некоторой степени касается и первого ограничения. Этот подход основан на декомпозиции графа на перекрывающиеся подграфы с ограниченной внешнепланарностью.

Основные результаты

Изначально подход Бэйкер [1] охватывал PTAS для максимального независимого множества на планарных графах, а также другие задачи для планарных графов: максимальное перекрытие черепицы, разбиение на треугольники, максимальное H-паросочетание, минимальное вершинное покрытие, минимальное доминирующее множество, минимальное доминирующее множество дуг. Алгоритм Бэйкер начинает работу с планарного вложения планарного графа. Затем он разделяет вершины на слои, итеративно удаляя вершины с внешнего контура графа; слой j состоит из вершин, удаленных на j-й итерации. Если после этого удалить уровни, конгруэнтные i по модулю k для любого выбранного i, граф разделяется на связные компоненты, содержащие не более k последовательных уровней, в силу чего граф становится k-внешнепланарным. Многие NP-полные задачи могут быть решены на k-внешнепланарных графах для фиксированного k при помощи методов динамического программирования (в частности, такие графы имеют ограниченную древесную ширину). Алгоритм аппроксимации Бэйкер вычисляет упомянутые оптимальные решения для каждого выбранного значения i, удаляя уровни этого класса конгруэнтности, и возвращает наилучшее решение среди полученных k решений. Ключевой этап задачи нахождения максимума рассматривает оптимальное решение в приложении ко всему графу и доказывает, что удаление одного из k классов конгруэнтности уровней удаляет не более 1/k части оптимального решения, так что возвращаемое решение будет близко к оптимальному с коэффициентом 1 + 1/k. Более тонкий подход также решает и задачу нахождения минимума. Для таких задач, как нахождение максимального независимого множества, минимального доминирующего множества и минимального вершинного покрытия, подход Бэйкер позволяет получить алгоритмы (1 + ε)-аппроксимации с временем исполнения [math]\displaystyle{ 2^{O(1/ \epsilon)}n^{O(1)} \, }[/math] на планарных графах.

Эпстайн [10] обобщает алгоритм Бэйкер на более широкий класс графов, называемых графами с ограниченной древесной шириной – иначе говоря, графов, у которых древесная ширина подграфа, порожденного множеством вершин с расстоянием до любой веришны не более r, ограничена некоторой функцией f(r), независимой от n. Основное отличие подхода Эпстайна заключается в замене понятия ограниченной внешнепланарности понятием ограниченной древесной ширины (благодаря чему можно применить алгоритмы динамического программирования, способные решить большой класс задач) и оснащению слоев метками в порядке простого обхода в ширину. Этот подход привел к созданию схем PTAS для традиционных задач нахождения максимума – таких, как максимальное независимое множество и максимальная клика, максимальное соответствие треугольников и максимальное H-паросочетание, максимальное перекрытие черепицы, минимальное вершинное покрытие, минимальное доминирующее множество, минимальное доминирующее множество дуг, минимальная цветовая сумма и изоморфизм подграфов относительно фиксированного шаблона [6, 8, 10]. Фрик и Гроу [11] разработали также обобщенную схему доказательства любого свойства, поддающегося выражению в виде логики первого порядка на графах с ограниченной древесной шириной.

Обоснованием для этих результатов является характеризация Эпстайном замкнутых относительно операции взятия минора семейств графов с ограниченной древесной шириной [10]. В частности, Эпстайн показал, что замкнутое относительно операции взятия минора семейство имеет ограниченную локальную древесную ширину в том и только том случае, если оно не включает апексный граф – граф, имеющий особую вершину, при удалении которой он становится планарным. К сожалению, первоначальное доказательство этого результата сделало подход Эпстайна непрактичным, поскольку граница локальной древесной ширины в графе без апексного минора оказалась дважды экспоненциальной – 2 в степени [math]\displaystyle{ 2^{O(r)} \, }[/math]. Однако эту границу удалось улучшить до [math]\displaystyle{ 2^{O(r)} \, }[/math] [3] и даже до оптимального O(r) [4]. Последняя граница соответствует времени исполнения алгоритма Бэйкер, [math]\displaystyle{ 2^{O(1/ \epsilon)}n^{O(1)} \, }[/math] для алгоритмов (1 + ε)-аппроксимации для всех графов без апексных миноров.

Еще один способ рассмотрения обязательной декомпозиции подходов Бэйкер и Эпстайна заключается в том, что вершины или дуги графа могут быть разделены на любое число (k) фрагментов, таких, что после удаления любого из этих фрагментов получается граф с ограниченной древесной шириной, причем граница зависит от k. Подобные декомпозиции фактически существуют для произвольных графов, за исключением фиксированных миноров H [9], и они могут быть найдены за полиномиальное время [6]. Этот подход обобщает PTAS-схемы Бэйкер-Эпстайна для обработки графов общего вида, не содержаших H-миноров.

Данный алгоритм декомпозиции ограничен задачами, замкнутыми относительно удаления, качество оптимального решения которых повышается при удалении из графа вершин или дуг. Еще один алгоритм декомпозиции предназначен для задач, замкнутых относительно сжатия, качество оптимального решения которых повышается при сжатии дуг графа. В их число входят такие классические задачи, как нахождение множества доминаторов и его вариации, задача коммивояжера, задача коммивояжера для подмножеств, минимальное дерево Штейнера и нахождение c-реберно-связного подмультиграфа с минимальным весом. Для этих задач на планарных графах [2, 13, 14] и на графах ограниченного рода [7] были разработаны PTAS-схемы благодаря тому, что дуги графа могут быть разделены на любое число (k) фрагментов, таких, что после сжатия любого из этих фрагментов получается граф с ограниченной древесной шириной, причем граница зависит от k.

Применение

Большинство приложений алгоритма Бэйкер ограничивались задачами оптимизации, возникающими из «локальных» свойств (к примеру, определяемых логикой первого порядка). Интуитивно представляется, что подобные локальные свойства можно доказать при помощи локальной проверки ближайшего окружения константного размера. В работе [5] подход Бэйкер был обобщен, что дало в результате PTAS-схемы для нелокальных задач – в частности, для нахождения связного доминирующего множества. Для этого обобщения потребовалось применение двух различных техник. Первая из них заключается в использовании ε-доли аппроксимации с константным или даже логарифмическим коэффициентом исходной задачи в качестве основы для достижения нужного нелокального свойства. Вторая техника заключается в использовании подзадач, перекрывающихся на [math]\displaystyle{ \Theta }[/math](log n) уровней, вместо принятых в подходе Бэйкер [math]\displaystyle{ \Theta }[/math](1).

Несмотря на успехи в применении подхода Бэйкер к большему кругу задач, алгоритмы на базе планарных сепараторов способны решать задачи и других типов. Однако у этого подхода есть другое ограничение: он лучше всего подходит для задач, у которых отношение размера оптимального решения к n составляет не меньше некоторого константного множителя. Для широкого круга задач это ограничение было успешно преодолено [5]; в частности, это касается применения схемы PTAS к множеству возвратных вершин, к которому ранее ни подход Бэйкер, ни алгоритм на базе планарных сепараторов не были применимы. Для этого выполняется равномерное разделение оптимального решения, а не целого графа, с использованием отношения между древесной шириной и размером оптимального решения для ограничения древесной ширины графа; в результате получается сепаратор размера [math]\displaystyle{ O(\sqrt{OPT}) }[/math] вместо сепаратора размера [math]\displaystyle{ O(\sqrt{n}) }[/math]. Граница древесной ширины [math]\displaystyle{ O(\sqrt{OPT}) }[/math] следует из теории двумерности, описанной во введении к статье двумерность. Мы можем разделить оптимальное решение на приблизительно равные фрагменты, даже не обладая знанием оптимального решения, посредством аппроксимаций с константным или даже логарифмическим коэффициентом. При рекурсивном вычислении фрагменты не будут иметь ограниченные размеры, но их древовидная ширина будет ограниченной, в силу чего для построения оптимальных решений могут применяться быстрые алгоритмы с фиксированными параметрами.

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

Наиболее многообещающим направлением будущих исследований является построение общей теории PTAS-схем для задач на подмножествах. Несмотря на то, что для планарных графов были недавно получены PTAS-алгоритмы решения задачи коммивояжера для подмножеств и задачи Штейнера [2, 14], остается немало открытых задач того же рода – к примеру, для множества возвратных вершин подмножества. Еще одна перспективное направление исследований заключается в понимании того, до какой степени подход Бэйкер применим к нелокальным задачам. Пример модификации этого подхода для решения нелокальных задач связного множества доминаторов известен [5], однако единственная известная PTAS-схема для нахождения множества возвратных вершин в планарных графах использует алгоритм с сепараторами.

См. также

• Двумерность
• Сепараторы в графах
• Древесная ширина графов

Литература

1. Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach. 41 (1), 153-180 (1994)

2. Borradaile, G., Kenyon-Mathieu, C., Klein, P.N.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

3. Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40(3), 211-215(2004)

4. Demaine, E.D., Hajiaghayi, M.: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA'04), January 2004, pp. 833-842

5. Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, January 2005, pp. 590-601

6. Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.-I.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, October 2005, pp.637-646

7. Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7-9 January 2007, pp. 278-287

8. Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2),166-195(2004)

9. DeVos, M., Ding, G., Oporowski, B., Sanders, D.P., Reed, B., Seymour, P., Vertigan, D.: Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory Ser. B 91(1), 25-41 (2004)

10. Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27(3-4), 275-291 (2000)

11. Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM 48(6), 1184-1206 (2001)

12. Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613-632 (2003)

13. Klein, P.N.: A linear-time approximation scheme for TSP for planar weighted graphs. In: Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 146-155

14. Klein, P.N.: A subset spanner for planar graphs, with application to subset TSP. In: Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 749-756

15. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177-189 (1979)

16. Lipton, R.J., Tarjan, R.E.: Applications of a planar separator the orem. SIAM J. Comput. 9(3), 615-627 (1980)