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

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

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

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