Экземпляр FPT-сокращений, который не является уменьшением за полиномиальное время

11

В параметризованной сложности люди используют сокращение с фиксированным параметром (FPT), чтобы доказать W [t] -твердость. Теоретически FPT-редукция не является редукцией за полиномиальное время, поскольку она может экспоненциально выполняться по параметру k. Но на практике все сокращения FPT, которые я видел, являются сокращением p-времени, что означает, что доказательства W [t] -твердости почти всегда подразумевают доказательства NP-полноты.

Интересно, может ли кто-нибудь дать мне сокращение FPT, которое действительно экспоненциально выполняется по параметру . Спасибо.k

yzll
источник

Ответы:

11

Ранним примером является доказательство W [2] -твердости для доминирующего в турнире множества (теорема 4.1 в [1]). Сокращение происходит от Доминирующего множества и создает турнир с вершинами, где - количество вершин экземпляра доминирующего множества, а - параметр.n kO(2kn)nk

[1]: Родни Г. Дауни и Майкл Р. Товарищи. Параметризованная вычислительная выполнимость. В P. Clote и JB Remmel, редакторы, Труды выполнимой математики II, стр. 219-244. Бирхаузер, 1995.

Серж Гасперс
источник
1
(Возможно, другое) доказательство того же утверждения также можно найти в книге «Теория параметризованной сложности» Дж. Флума и М. Гроэ, теорема 7.17.
Матье Шапель
8

Следующая статья содержит сокращения для различных параметризаций Ближайшей подстроки, где время выполнения экспоненциально или в два раза экспоненциально зависит от параметра (и эта зависимость кажется неизбежной).

Д. Маркс. Ближайшие проблемы с подстрокой на малых расстояниях . SIAM Journal of Computing, 38 (4): 1382-1410, 2008.

Даниэль Маркс
источник
6

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

(Q,k)(Q,k)(Q,k)<fpt(Q,k)Q<ptime Q

<fpt<ptime

[2]: J. Flum, M. Grohe. Теория параметризованной сложности. Springer (2006)

Матье Шапель
источник
5

Возможно, это не предполагаемый ответ, но как насчет (дерандомизированного варианта) цветового кодирования для проблемы k-пути? http://en.wikipedia.org/wiki/Color-coding

Там каждый преобразует экземпляр проблемы k-path в экземпляры красочной задачи k-path путем fpt-редукции с суперполиномиальной зависимостью от k. (Создается несколько экземпляров, но их можно рассматривать как один большой экземпляр.) Поскольку красочная проблема k-path может быть решена за fpt время с помощью динамического программирования, мы можем заключить, что проблема k-path относится к FPT.

Ёсио Окамото
источник
3

Другим примером такого снижения является доказательство твердости для VC-измерения. См. «Параметризованная сложность обучения» Дауни, Эванса и Стипендиатов.

Майкл Лэмпис
источник