Instância de reduções de FPT que não são uma redução no tempo polinomial

Na complexidade parametrizada, as pessoas usam a redução de FPT (Trace-Parametrable-Fixed) para provar a dureza W [t]. Teoricamente, uma redução de FPT não é uma redução de tempo polinomial, pois pode ser executada exponencialmente no parâmetro k. Mas, na prática, todas as reduções de FPT que eu vi são reduções no tempo p, o que significa que as provas de dureza W [t] quase sempre implicam provas de completude de NP.

Gostaria de saber se alguém pode me dar uma redução de FPT que realmente é executada exponencialmente no parâmetro . Obrigado.$k$

Um exemplo inicial é a prova de dureza W [2] para o Conjunto Dominante de Torneio (Teorema 4.1 em [1]). A redução é de Dominating Set e constrói um torneio com vértices, em que n é o número de vértices da instância do conjunto dominante e k é o parâmetro.$O(2^k n)$$n$$k$

[1]: Rodney G. Downey e Michael R. Fellows. Viabilidade computacional parametrizada. Em P. Clote e JB Remmel, editores, Proceedings of Feasible Mathematics II, páginas 219-244. Birkhauser, 1995.

O documento a seguir contém reduções para várias parametrizações de Substring mais próximo, nas quais o tempo de execução depende exponencialmente ou do dobro exponencialmente do parâmetro (e essa dependência parece inevitável).

D. Marx. Problemas de substring mais próximos com pequenas distâncias . Revista Brasileira de Computação, 38 (4): 1382-1410, 2008.

Como complemento às outras respostas, a seguinte proposição mostra que as noções correspondentes de redutibilidade são incomparáveis:

$(Q,k)$$(Q',k')$$(Q,k) <^{\mathrm{fpt}} (Q',k')$$Q' <^{\mathrm{ptime}}\ Q$

$<^{\mathrm{fpt}}$$<^{\mathrm{ptime}}$

[2]: J. Flum, M. Grohe. Teoria da complexidade parametrizada. Springer (2006)

Provavelmente, essa não é uma resposta pretendida, mas que tal (uma variante aleatória) de código de cores para o problema do caminho k? http://en.wikipedia.org/wiki/Color-coding

Ali, transforma-se uma instância do problema do caminho k em instâncias do problema colorido do caminho k por uma redução de fpt com dependência super-polinomial de k. (Cria-se várias instâncias, mas elas podem ser vistas como uma grande instância.) Como o problema do caminho k colorido pode ser resolvido em tempo de fpt pela programação dinâmica, podemos concluir que o problema do caminho k pertence ao FPT.

Outro exemplo dessa redução é a prova de dureza para a dimensão VC. Veja "Complexidade da aprendizagem parametrizada", de Downey, Evans e Fellows.