8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are the k in “k-CNF” and the k in the question the same variable? And what is the parameter of this problem? $\endgroup$ – Tsuyoshi Ito Sep 4 '10 at 16:32
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 4 '10 at 16:44
  • $\begingroup$ 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). $\endgroup$ – Neeldhara Sep 4 '10 at 16:45
  • $\begingroup$ @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. $\endgroup$ – Neeldhara Sep 4 '10 at 16:47
  • $\begingroup$ @Neeldhara: My guess is that the parameter is either the plain k or the bold k, not the italic $k$! $\endgroup$ – Tsuyoshi Ito Sep 4 '10 at 16:56
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Actually I thought the others gave more comprehensive answers. In fact after seeing Serge's answer, I thought about deleting mine... $\endgroup$ – Ryan Williams Sep 4 '10 at 19:18
11
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Ryan Williams Sep 4 '10 at 17:24
  • $\begingroup$ Aha - that worked, thanks much! Saved me a trip to meta :) $\endgroup$ – Neeldhara Sep 4 '10 at 17:28
  • 1
    $\begingroup$ Double-backslash-curly works in math, I think. $\endgroup$ – David Eppstein Sep 4 '10 at 18:01
  • $\begingroup$ That's quite right; and the behavior is also explained at the MO FAQ: mathoverflow.net/faq Apparently it has something to do with Markdown interference, and apparently using backticks is another solution too. $\endgroup$ – Neeldhara Sep 4 '10 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.