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

Многие 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.