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

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

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

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

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