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

Вопрос: существует ли подграф <math>S \subseteq V</math> с <math>|S| \le k \; </math>, такой, что каждая вершина <math>v \in V \; </math> входит в S, либо по крайней мере один из ее соседей входит в S?

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