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

К примеру, построить оптимизированную версию графа с n вершинами за полиномиальное время можно только с точностью до множителя <math>\Theta (log \; n) \; </math>, если не выполняются некоторые стандартные теоретико-сложностные предположения [9]. В терминах параметризованной сложности эта задача, как было показано в [8], является W[2]-полной. Для планарных графов она по-прежнему является NP-полной, однако в данном случае ситуация оказывается намного проще. В своей основополагающей работе Бэйкер показала, что существует схема аппроксимации с полиномиальным временем исполнения (PTAS) [6], и что в случае планарных графов эта задача становится разрешимой при помощи алгоритмов с фиксированными параметрами [2, 4]. В частности, задача может иметь решение при использовании достаточно эффективных правил редукции; может быть доказан результат кернелизации (общее описание редукции данных и кернелизации см. в [16]).