Существование -аппроксимации доминирующего множества с ?

Рассмотрим проблему доминирующего множества в общих графах, и пусть будет количеством вершин в графе. Алгоритм жадного приближения дает гарантию приближения фактора , т. Е. В полиномиальное время можно найти решение такое, что , где - размер минимального доминирующего множества. Есть оценки , показывающие , что мы не можем улучшить зависимость много http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf .$n$$1 + \log n$$S$$|S| \leq (1 + \log n) opt$$opt$$\log n$

Мой вопрос: есть ли алгоритм приближения, который имеет гарантию с точки зрения вместо ? На графиках, где очень велико по отношению к оптимуму, приближение фактор- будет намного хуже, чем приближение фактор- . Известно ли что-то подобное или есть причины, по которым этого не может быть? Я доволен любым алгоритмом полиномиального времени, который выдает решение такое, что для некоторой константы .$opt$$n$$n$$\log n$$\log opt$$S$$|S| \in O(opt^c)$$c$

Я думаю, что все еще открыто, если доминирующий набор или ударный набор имеют приближение af (OPT) для некоторой (нетривиальной) функции f. Это должен быть очень сложный (и, возможно, глубокий) вопрос. Я считаю это наиболее интересным вопросом в параметризованном приближении (наряду с аналогичным вопросом для Клики). Возможно, вы захотите взглянуть на мой опрос [1], в котором обсуждается это. Обратите внимание, что в более поздней работе [2] показано, что «выполнимость монотонной схемы для цепей утка-2», задача более общая, чем доминирующий набор, не имеет аппроксимации f (OPT) для любых f.

[1] Д. Маркс. Параметризованные алгоритмы сложности и аппроксимации. Компьютерный журнал, 51 (1): 60-78, 2008.

[2] Д. Маркс. Абсолютно неприемлемые монотонные и антимонотонные параметризованные проблемы. В материалах 25-й ежегодной конференции IEEE по вычислительной сложности, Кембридж, Массачусетс, 181-187, 2010.

Это должен быть комментарий, так как он напрямую не отвечает на ваш вопрос, а связан с вопросом. Возможно, что аналогичная уловка из [1] даст вам ответ.

В [1] доказано следующее:

Даны граф и параметр . Не существует алгоритма FPT (параметризованного ), который либо: (a) возвращает независимый доминирующий набор в размером не менее , где - фиксированная функция, зависящая только от или (b), определяет что не имеет доминирующего множества размера . (... Если FPT = W [2].)$G=(V,E)$$k$$k$$G$$g(k)$$g(k)$$k$$G$$k$

Любой алгоритм за полиномиальное время, который возвращает независимый доминирующий набор размером не менее , подразумевает, как минимум, FPT = W [2].$g(k)$

[1] Родни Г. Дауни, Майкл Р. Товарищи, Кэтрин Маккартин и Фрэнсис Розамонд. «Параметризованная аппроксимация задач с доминирующим множеством». Письма обработки информации, том 109, выпуск 1, декабрь 2008 года.