<p>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.</p>

<p>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.) </p>

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

CC BY-SA 2.5
2010-09-04T19:18:23.260Z
Actually I thought the others gave more comprehensive answers. In fact after seeing Serge's answer, I thought about deleting mine...
Ryan Williams
CC BY-SA 2.5
2010-09-04T16:58:06.813Z
2010-09-04T16:58:06.813Z
Ryan Williams
<p>The problem is known as <strong>r-Set Packing</strong>:<br>
Instance: A collection $\mathcal{C}$ of subsets of size at most $r$ of a finite set $S$ and an integer $k$.<br>
Parameter: $k$<br>
Question: Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ which consists of at least $k$ mutually disjoint subsets?</p>

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

<p>[1]: Rodney G. Downey, Michael R. Fellows: Parameterized Complexity. Springer, 1999.<br>
[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)</p>

CC BY-SA 2.5
2010-09-04T16:57:38.110Z
2010-09-04T18:37:18.243Z
2010-09-04T18:37:18.243Z
Serge Gaspers
<p>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).</p>

<p>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$. </p>

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

<p>$\{(u,v) ~|~ (u,v) \in E(G)\}$,</p>

<p>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. </p>

<p>Now, here is a reduction <em>to</em> 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. </p>

<p>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. </p>

<p>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.  </p>

CC BY-SA 2.5
2010-09-04T17:24:06.903Z
Hi Neeldhara, you can make the curly braces {} appear by putting them outside of the latex code. E.g., {$(u,v)$} works. (It's just a property of the latex compiler we are using... sorry)
Ryan Williams
CC BY-SA 2.5
2010-09-04T17:28:37.250Z
Aha - that worked, thanks much! Saved me a trip to meta :)
Neeldhara
CC BY-SA 2.5
2010-09-04T18:01:13.103Z
Double-backslash-curly works in math, I think.
David Eppstein
CC BY-SA 2.5
2010-09-04T18:14:30.123Z
That's quite right; and the behavior is also explained at the MO FAQ: http://mathoverflow.net/faq Apparently it has something to do with Markdown interference, and apparently using backticks is another solution too.
Neeldhara
CC BY-SA 2.5
2010-09-04T17:13:25.200Z
2010-09-04T18:09:32.527Z
2010-09-04T18:09:32.527Z
Neeldhara
<p>Parametrized maximum independent clauses problem:<br>
Input : A r-CNFSAT formula F having <strong>n</strong> variables and <strong>m</strong> clauses, <strong>k</strong><br>
Ques  : Does there exists at least <strong>k</strong> clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.<br>
Parameter : <strong>k</strong><br>
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated. </p>

CC BY-SA 2.5
2010-09-04T16:32:34.997Z
Are the k in “k-CNF” and the k in the question the same variable?  And what is the parameter of this problem?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-04T16:44:11.913Z
Also, have you tried to state your problem in different ways, that is, without referring to CNF formulas?  “The hypergraph matching” and “the r-set packing” (where r refers to your first k, the number of variables in each clause) seem to be common names for this problem.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-04T16:45:28.697Z
The parameter is likely to be $k$. This appears to me as being equivalent to finding a maximum matching a hypergraph, not sure how I see the fact that it is a "formula" makes a difference (in other words, I don't see how negated literals influence the problem - not that they have to, just curious).
Neeldhara
CC BY-SA 2.5
2010-09-04T16:47:45.717Z
@Tsuyoshi: A quick search doesn't reveal anything about the parameterized complexity of the maximum hypergraph matching problem either, so the question remains interesting despite the recasting.
Neeldhara
CC BY-SA 2.5
2010-09-04T16:56:54.760Z
@Neeldhara: My guess is that the parameter is either the plain k or the bold **k**, not the italic $k$!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-04T17:16:28.563Z
@Tsuyoshi: Whoops, I had, in my mind, disregarded the very first k in the question - I now realize that my suggestion about the parameter is not helpful at all :) As you have guessed, the parameter is likely to be the number of "clauses" in question.
Neeldhara
CC BY-SA 2.5
2010-09-04T17:22:07.173Z
@Neeldhara: Yeah, I have guessed so.  An interesting thing is that the parametrized complexity of this problem is very different depending on which k is the parameter :).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-04T17:26:07.470Z
@Tsuyoshi: Absolutely - tried to clarify that in an attempted answer, and now hoping not too much is wrong with it!
Neeldhara
<cc.complexity-theory><parameterized-complexity><fixed-parameter-tractable>
Is parametrized maximum independent clauses problem in FPT?
Gaurav
# Is parametrized maximum independent clauses problem in FPT?

(Asked by: username_0 on 2010-09-04)

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.

**Tags:** cc.complexity-theory, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: Are the k in “k-CNF” and the k in the question the same variable?  And what is the parameter of this problem?  
> **username_1**: Also, have you tried to state your problem in different ways, that is, without referring to CNF formulas?  “The hypergraph matching” and “the r-set packing” (where r refers to your first k, the number of variables in each clause) seem to be common names for this problem.  
> **username_2**: The parameter is likely to be $k$. This appears to me as being equivalent to finding a maximum matching a hypergraph, not sure how I see the fact that it is a "formula" makes a difference (in other words, I don't see how negated literals influence the problem - not that they have to, just curious).  
> **username_2**: @Tsuyoshi: A quick search doesn't reveal anything about the parameterized complexity of the maximum hypergraph matching problem either, so the question remains interesting despite the recasting.  
> **username_1**: @Neeldhara: My guess is that the parameter is either the plain k or the bold **k**, not the italic $k$!  
> **username_2**: @Tsuyoshi: Whoops, I had, in my mind, disregarded the very first k in the question - I now realize that my suggestion about the parameter is not helpful at all :) As you have guessed, the parameter is likely to be the number of "clauses" in question.  
> **username_1**: @Neeldhara: Yeah, I have guessed so.  An interesting thing is that the parametrized complexity of this problem is very different depending on which k is the parameter :).  
> **username_2**: @Tsuyoshi: Absolutely - tried to clarify that in an attempted answer, and now hoping not too much is wrong with it!  

---

## 3 answers

### Answer by username_3 on 2010-09-04. Score: 5 | Accepted answer

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".

> **Comments:**
> **username_3**: Actually I thought the others gave more comprehensive answers. In fact after seeing Serge's answer, I thought about deleting mine...  

---

### Answer by username_4 on 2010-09-04. Score: 11

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 by username_2 on 2010-09-04. Score: 6

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.

> **Comments:**
> **username_3**: Hi Neeldhara, you can make the curly braces {} appear by putting them outside of the latex code. E.g., {$(u,v)$} works. (It's just a property of the latex compiler we are using... sorry)  
> **username_2**: Aha - that worked, thanks much! Saved me a trip to meta :)  
> **username_5**: Double-backslash-curly works in math, I think.  
> **username_2**: That's quite right; and the behavior is also explained at the MO FAQ: http://mathoverflow.net/faq Apparently it has something to do with Markdown interference, and apparently using backticks is another solution too.  

---

