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

Алгоритм Бэйкер начинает работу с планарного вложения планарного графа. Затем он разделяет вершины на слои, итеративно удаляя вершины с внешнего контура графа; слой 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]. В частности, Эпстайн показал, что замкнутое относительно операции взятия минора семейство имеет ограниченную локальную древесную ширину в том и только том случае, если оно не включает апексный граф – граф, имеющий особую вершину, при удалении которой он становится планарным. К сожалению, первоначальное доказательство этого результата сделало подход Эпстайна непрактичным, поскольку граница локальной древесной ширины в графе без апексного минора оказалась дважды экспоненциальной – 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 + ε)-аппроксимации для всех графов без апексных миноров.