Аппроксимационные схемы для задач с планарными графами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (Irina переименовал страницу Схемы аппроксимации для задач с планарными графами в Аппроксимационные схемы для задач с планарными графами) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 14: | Строка 14: | ||
== Основные результаты == | == Основные результаты == | ||
Изначально подход Бэйкер [1] охватывал PTAS для максимального независимого множества на планарных графах, а также другие задачи для планарных графов: максимальное перекрытие черепицы, разбиение на треугольники, максимальное H-паросочетание, минимальное вершинное покрытие, минимальное доминирующее множество, минимальное доминирующее множество дуг. | Изначально подход Бэйкер [1] охватывал PTAS для максимального независимого множества на планарных графах, а также другие задачи для планарных графов: максимальное перекрытие черепицы, разбиение на треугольники, максимальное H-паросочетание, минимальное вершинное покрытие, минимальное доминирующее множество, минимальное доминирующее множество дуг. | ||
Алгоритм Бэйкер начинает работу с планарного вложения планарного графа. Затем он разделяет вершины на слои, итеративно удаляя вершины с внешнего контура графа; слой j состоит из вершин, удаленных на j-й итерации. Если после этого удалить уровни, конгруэнтные i по модулю k для любого выбранного i, граф разделяется на связные компоненты, содержащие не более k последовательных уровней, в силу чего граф становится k-внешнепланарным. Многие NP-полные задачи могут быть решены на k-внешнепланарных графах для фиксированного k при помощи методов динамического программирования (в частности, такие графы имеют ограниченную древесную ширину). Аппроксимационный алгоритм Бэйкер вычисляет упомянутые оптимальные решения для каждого выбранного значения i, удаляя уровни этого класса конгруэнтности, и возвращает наилучшее решение среди полученных k решений. Ключевой этап задачи нахождения максимума рассматривает оптимальное решение в приложении ко всему графу и доказывает, что удаление одного из k классов конгруэнтности уровней удаляет не более 1/k части оптимального решения, так что возвращаемое решение будет близко к оптимальному с коэффициентом 1 + 1/k. Более тонкий подход также решает и задачу нахождения минимума. Для таких задач, как нахождение максимального независимого множества, минимального доминирующего множества и минимального вершинного покрытия, подход Бэйкер позволяет получить алгоритмы (1 + ε)-аппроксимации с временем | Алгоритм Бэйкер начинает работу с планарного вложения планарного графа. Затем он разделяет вершины на слои, итеративно удаляя вершины с внешнего контура графа; слой 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] обобщает алгоритм Бэйкер на более широкий класс графов, называемых ''графами с ограниченной древесной шириной'' – иначе говоря, графов, у которых древесная ширина подграфа, порожденного множеством вершин с расстоянием до любой веришны не более 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]. Последняя граница соответствует времени | Обоснованием для этих результатов является характеризация Эпстайном замкнутых относительно операции взятия минора семейств графов с ограниченной древесной шириной [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-миноров. | Еще один способ рассмотрения обязательной декомпозиции подходов Бэйкер и Эпстайна заключается в том, что вершины или дуги графа могут быть разделены на любое число (k) фрагментов, таких, что после удаления любого из этих фрагментов получается граф с ограниченной древесной шириной, причем граница зависит от k. Подобные декомпозиции фактически существуют для произвольных графов, за исключением фиксированных миноров H [9], и они могут быть найдены за полиномиальное время [6]. Этот подход обобщает PTAS-схемы Бэйкер-Эпстайна для обработки графов общего вида, не содержаших H-миноров. | ||