4551
правка
Аппроксимационные схемы для задач с планарными графами: различия между версиями
Материал из WEGA
Аппроксимационные схемы для задач с планарными графами (посмотреть исходный код)
Версия от 17:41, 18 июля 2014
, 18 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
Алгоритм Бэйкер начинает работу с планарного вложения планарного графа. Затем он разделяет вершины на слои, итеративно удаляя вершины с внешнего контура графа; слой j состоит из вершин, удаленных на j-й итерации. Если после этого удалить уровни, конгруэнтные i по модулю k для любого выбранного i, граф разделяется на связные компоненты, содержащие не более k последовательных уровней, в силу чего граф становится k-внешнепланарным. Многие NP-полные задачи могут быть решены на k-внешнепланарных графах для фиксированного k при помощи методов динамического программирования (в частности, такие графы имеют ограниченную древесную ширину). Алгоритм аппроксимации Бэйкер вычисляет упомянутые оптимальные решения для каждого выбранного значения i, удаляя уровни этого класса конгруэнтности, и возвращает наилучшее решение среди полученных k решений. Ключевой этап задачи нахождения максимума рассматривает оптимальное решение в приложении ко всему графу и доказывает, что удаление одного из k классов конгруэнтности уровней удаляет не более 1/k части оптимального решения, так что возвращаемое решение будет близко к оптимальному с коэффициентом 1 + 1/k. Более тонкий подход также решает и задачу нахождения минимума. Для таких задач, как нахождение максимального независимого множества, минимального доминирующего множества и минимального вершинного покрытия, подход Бэйкер позволяет получить алгоритмы (1 + ε)-аппроксимации с временем исполнения <math>2^{O(1/ \epsilon)}n^{O(1)} \, </math> на планарных графах. | Алгоритм Бэйкер начинает работу с планарного вложения планарного графа. Затем он разделяет вершины на слои, итеративно удаляя вершины с внешнего контура графа; слой j состоит из вершин, удаленных на j-й итерации. Если после этого удалить уровни, конгруэнтные i по модулю k для любого выбранного i, граф разделяется на связные компоненты, содержащие не более k последовательных уровней, в силу чего граф становится k-внешнепланарным. Многие NP-полные задачи могут быть решены на k-внешнепланарных графах для фиксированного k при помощи методов динамического программирования (в частности, такие графы имеют ограниченную древесную ширину). Алгоритм аппроксимации Бэйкер вычисляет упомянутые оптимальные решения для каждого выбранного значения i, удаляя уровни этого класса конгруэнтности, и возвращает наилучшее решение среди полученных k решений. Ключевой этап задачи нахождения максимума рассматривает оптимальное решение в приложении ко всему графу и доказывает, что удаление одного из k классов конгруэнтности уровней удаляет не более 1/k части оптимального решения, так что возвращаемое решение будет близко к оптимальному с коэффициентом 1 + 1/k. Более тонкий подход также решает и задачу нахождения минимума. Для таких задач, как нахождение максимального независимого множества, минимального доминирующего множества и минимального вершинного покрытия, подход Бэйкер позволяет получить алгоритмы (1 + ε)-аппроксимации с временем исполнения <math>2^{O(1/ \epsilon)}n^{O(1)} \, </math> на планарных графах. | ||
Эпстайн [10] обобщает алгоритм Бэйкер на более широкий класс графов, называемых ''графами с ограниченной древесной шириной'' – иначе говоря, графов, у которых древесная ширина подграфа, порожденного множеством вершин с расстоянием до любой веришны не более r, ограничена некоторой функцией f(r), независимой от n. Основное отличие подхода Эпстайна заключается в замене понятия ограниченной внешнепланарности понятием ограниченной древесной ширины (благодаря чему можно применить алгоритмы динамического программирования, способные решить большой класс задач) и оснащению слоев метками в порядке простого обхода в ширину. Этот подход привел к созданию схем PTAS для традиционных задач нахождения максимума – таких, как максимальное независимое множество и максимальная клика, максимальное соответствие треугольников и максимальное H-паросочетание, максимальное перекрытие черепицы, минимальное вершинное покрытие, минимальное доминирующее множество, минимальное доминирующее множество дуг, минимальная цветовая сумма и изоморфизм подграфов относительно фиксированного шаблона [6, 8, 10]. Фрик и Гроу [11] разработали также обобщенную схему доказательства любого свойства, поддающегося выражению в виде логики первого порядка на графах с ограниченной древесной шириной. | |||
Обоснованием для этих результатов является характеризация | Обоснованием для этих результатов является характеризация Эпстайном замкнутых относительно операции взятия минора семейств графов с ограниченной древесной шириной [10]. В частности, Эпстайн показал, что замкнутое относительно операции взятия минора семейство имеет ограниченную локальную древесную ширину в том и только том случае, если оно не включает апексный граф – граф, имеющий особую вершину, при удалении которой он становится планарным. К сожалению, первоначальное доказательство этого результата сделало подход Эпстайна непрактичным, поскольку граница локальной древесной ширины в графе без апексного минора оказалась дважды экспоненциальной – 2 в степени <math>2^{O(r)} \, </math>. Однако эту границу удалось улучшить до <math>2^{O(r)} \, </math> [3] и даже до оптимального O(r) [4]. Последняя граница соответствует времени исполнения алгоритма Бэйкер, <math>2^{O(1/ \epsilon)}n^{O(1)} \, </math> для алгоритмов (1 + ε)-аппроксимации для всех графов без апексных миноров. | ||
Еще один способ рассмотрения обязательной декомпозиции подходов Бэйкер и | Еще один способ рассмотрения обязательной декомпозиции подходов Бэйкер и Эпстайна заключается в том, что вершины или дуги графа могут быть разделены на любое число (k) фрагментов, таких, что после удаления любого из этих фрагментов получается граф с ограниченной древесной шириной, причем граница зависит от k. Подобные декомпозиции фактически существуют для произвольных графов, за исключением фиксированных миноров H [9], и они могут быть найдены за полиномиальное время [6]. Этот подход обобщает PTAS-схемы Бэйкер-Эпстайна для обработки графов общего вида, не содержаших H-миноров. | ||
Данный алгоритм декомпозиции ограничен задачами, замкнутыми относительно удаления, качество оптимального решения которых повышается при удалении из графа вершин или дуг. Еще один алгоритм декомпозиции предназначен для задач, замкнутых относительно сжатия, качество оптимального решения которых повышается при сжатии дуг графа. В их число входят такие классические задачи, как нахождение множества доминаторов и его вариации, задача коммивояжера, задача коммивояжера для подмножеств, минимальное дерево Штейнера и нахождение c-реберно-связного подмультиграфа с минимальным весом. Для этих задач на планарных графах [2, 13, 14] и на графах ограниченного рода [7] были разработаны PTAS-схемы благодаря тому, что дуги графа могут быть разделены на любое число (k) фрагментов, таких, что после сжатия любого из этих фрагментов получается граф с ограниченной древесной шириной, причем граница зависит от k. | Данный алгоритм декомпозиции ограничен задачами, замкнутыми относительно удаления, качество оптимального решения которых повышается при удалении из графа вершин или дуг. Еще один алгоритм декомпозиции предназначен для задач, замкнутых относительно сжатия, качество оптимального решения которых повышается при сжатии дуг графа. В их число входят такие классические задачи, как нахождение множества доминаторов и его вариации, задача коммивояжера, задача коммивояжера для подмножеств, минимальное дерево Штейнера и нахождение c-реберно-связного подмультиграфа с минимальным весом. Для этих задач на планарных графах [2, 13, 14] и на графах ограниченного рода [7] были разработаны PTAS-схемы благодаря тому, что дуги графа могут быть разделены на любое число (k) фрагментов, таких, что после сжатия любого из этих фрагментов получается граф с ограниченной древесной шириной, причем граница зависит от k. | ||
