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

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