Is parametrized maximum independent clauses problem in FPT?

Question

Parametrized maximum independent clauses problem:
Input : A r-CNFSAT formula F having n variables and m clauses, k
Ques : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
Parameter : k
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.

Answer 1

I'll assume that the k in k-CNF is different from the number of clauses k, and also that the latter is the parameter. I will replace k-CNF with k'-CNF in the following.

This problem is in FPT for every k'. Notice that no "logic" is being used in the problem definition, so you can just assume that you have a collection of m sets of n elements, where each set has cardinality at most k'. (Removing the signs of the literals does not change the problem.)

Now you are asking for a set packing of size k from a collection of size m, where every set has cardinality at most k'. This is FPT when each set has constant size. There are many references to this problem, the key phrase is "set packing".

Answer 2

The problem is known as r-Set Packing:
Instance: A collection $\mathcal{C}$ of subsets of size at most $r$ of a finite set $S$ and an integer $k$.
Parameter: $k$
Question: Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ which consists of at least $k$ mutually disjoint subsets?

For unbounded $r$, the problem is W[1]-hard by an easy reduction from Independent Set (see for example [1]).
However, for constant $r$, the problem becomes fixed parameter tractable (see for example [2]).

[1]: Rodney G. Downey, Michael R. Fellows: Parameterized Complexity. Springer, 1999.
[2]: Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides: Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. Algorithmica 52(2): 167-176 (2008)

Answer 3

Let me try to give an explicit two-way reduction that should make the FPT/W-hardness in different situations clear (it's strongly recommended that you look up the excellent references in the other answers, as this is just something I worked out after reading your question, and I could have quite easily missed something).

I'll work with the following problem: we are given a family of subsets of an universe, and the question is if there is a subfamily of mutually disjoint sets of size at least $k$.

So here is a reduction from independent set: let the universe be the set of all pairs $(i,j)$, $i < j$. For every vertex, introduce the subfamily:

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

with an appropriate ordering between $u$ and $v$. It's easy to see that a collection of independent vertices corresponds exactly to a mutually disjoint subcollection.

Now, here is a reduction to independent set: introduce a vertex for every set, and add an edge between two sets iff they share an element in common. Again, a set of mutually disjoint sets in the family corresponds exactly to an independent set in this graph.

This establishes, modulo details, that the problem in question is equivalent to the independent set problem, which is well-known to be $W[1]$-hard. On the other hand, if the graph has bounded maximum degree (let's say the $\Delta = O(1)$), then the problem is FPT by an easy branching strategy: note that any maximum independent set intersects non-trivially with $N[v]$, and one could branch if $|N[v]|$ is bounded.

That's why your problem is W-hard in general, and FPT in the special case when the sizes of the sets in the given family are bounded.