O problema de cláusulas independentes máximas parametrizadas é no FPT?

Parametrizada máximo problema cláusulas independente:
Entrada: fórmula A r-CNFSAT F tendo n variáveis e m cláusulas, k
Ques: Does existe pelo menos k cláusulas de tal modo que eles são independentes entre si ou seja, não variável ocorre mais do que uma vez em todos estes cláusulas combinadas.
Parâmetro: k
Gostaria de saber se esse problema está no FPT ou não. Em ambas as situações, uma idéia para avançar será apreciada.

Suponho que o k no k-CNF seja diferente do número de cláusulas k e também que o último seja o parâmetro. Substituirei o k-CNF pelo k'-CNF a seguir.

Esse problema está no FPT para cada k '. Observe que nenhuma "lógica" está sendo usada na definição do problema; portanto, você pode simplesmente assumir que possui uma coleção de m conjuntos de n elementos, em que cada conjunto tem cardinalidade no máximo k '. (Remover os sinais dos literais não altera o problema.)

Agora você está solicitando um conjunto de tamanho k de uma coleção de tamanho m, onde cada conjunto tem cardinalidade no máximo k ' . Este é o FPT quando cada conjunto tem tamanho constante. Existem muitas referências a esse problema, a frase-chave é "definir embalagem".

$\mathcal{C}$$r$$S$$k$
$k$
$\mathcal{C'} \subseteq \mathcal{C}$$k$

$r$
$r$

[1]: Rodney G. Downey, Michael R. Fellows: complexidade parametrizada. Springer, 1999.
[2]: Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Dimitrios M. Thilikos, Sue Whitesides: Algoritmos tratáveis ​​de parâmetros fixos mais rápidos para problemas de correspondência e empacotamento. Algoritmica 52 (2): 167-176 (2008)

Deixe-me tentar fornecer uma redução bidirecional explícita que deve tornar clara a dureza FPT / W em diferentes situações (é altamente recomendável que você procure as excelentes referências nas outras respostas, pois isso é apenas algo que resolvi depois de ler sua pergunta, e eu poderia facilmente ter perdido alguma coisa).

$k$

$(i,j)$$i < j$

$\{(u,v) ~|~ (u,v) \in E(G)\}$

$u$$v$

Agora, aqui está uma redução ao conjunto independente: introduza um vértice para cada conjunto e adicione uma aresta entre dois conjuntos se eles compartilharem um elemento em comum. Novamente, um conjunto de conjuntos mutuamente disjuntos na família corresponde exatamente a um conjunto independente neste gráfico.

$W[1]$$\Delta = O(1)$$N[v]$$|N[v]|$

É por isso que seu problema é difícil em geral e FPT no caso especial quando os tamanhos dos conjuntos na família em questão são limitados.