¿El problema de las cláusulas independientes máximas parametrizadas en FPT?

Problema de cláusulas independientes máximas
parametrizadas : Entrada: Una fórmula F de r-CNFSAT que tiene n variables y cláusulas m , k
Ques: ¿Existe al menos k cláusulas tales que sean mutuamente independientes, es decir, no se produce ninguna variable más de una vez en todas estas cláusulas combinadas.
Parámetro: k
Me gustaría saber si este problema está en FPT o no. En ambas situaciones, se apreciará una idea para avanzar.

Asumiré que la k en k-CNF es diferente del número de cláusulas k, y también que esta última es el parámetro. Reemplazaré k-CNF con k'-CNF en lo siguiente.

Este problema está en FPT por cada k '. Observe que no se está utilizando "lógica" en la definición del problema, por lo que puede suponer que tiene una colección de m conjuntos de n elementos, donde cada conjunto tiene cardinalidad como máximo k '. (Eliminar los signos de los literales no cambia el problema).

Ahora está solicitando un conjunto de embalaje de tamaño k de una colección de tamaño m, donde cada conjunto tiene cardinalidad como máximo k ' . Esto es FPT cuando cada conjunto tiene un tamaño constante. Hay muchas referencias a este problema, la frase clave es "establecer embalaje".

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

$r$
$r$

[1]: Rodney G. Downey, Michael R. Fellows: Complejidad parametrizada. Springer, 1999.
[2]: Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides: Algoritmos manejables de parámetros fijos más rápidos para problemas de emparejamiento y empaque. Algorithmica 52 (2): 167-176 (2008)

Permítanme intentar ofrecer una reducción bidireccional explícita que debería aclarar la dureza FPT / W en diferentes situaciones (se recomienda encarecidamente que busque las excelentes referencias en las otras respuestas, ya que esto es algo que resolví después de leer tu pregunta, y podría haber pasado algo por alto fácilmente).

$k$

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

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

$u$$v$

Ahora, aquí hay una reducción al conjunto independiente: introduzca un vértice para cada conjunto y agregue un borde entre dos conjuntos si comparten un elemento en común. Una vez más, un conjunto de conjuntos mutuamente disjuntos en la familia corresponde exactamente a un conjunto independiente en este gráfico.

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

Es por eso que su problema es W-hard en general, y FPT en el caso especial cuando los tamaños de los conjuntos en la familia dada están limitados.