Точные алгоритмы построения доминирующего множества: различия между версиями

Задача построения минимального доминирующего множества – одна из основных задач параметризованной сложности [ ]; она является W[2]-полной и, в связи с этим, едва ли окажется разрешимой при помощи алгоритмов с фиксированными параметрами. С другой стороны, на планарных графах она является разрешимой при помощи алгоритмов с фиксированными параметрами. С точки зрения аппроксимации эта задача эквивалентна задаче о минимальном покрытии множества при L-сведении. Существует аппроксимационный алгоритм для нахождения минимального доминирующего множества с коэффициентом <math>1 + ln |V| \; </math>; эта задача не может быть аппроксимирована с коэффициентом <math>(1 - \epsilon ) \; ln |V|</math> для любого <math>\epsilon > 0 \; </math>, за исключением случая <math>NP \subset DTIME(n^{log \; log \; n})</math> [1].