I have been thinking on this problem but couldn't come up with a good reduction yet. First part of the proof, i.e L is being in NP, is okay. However, I cannot find a proper reduction from 3-CNF-SAT to MAXIMUM-DISJOINT-SET problem.
Edit 1: MDS definition MAXIMUM-DISJOINT-SET problem: We are given a collection S of sets. We would like to find the maximum number of disjoint sets in S. K sets are said to be disjoint sets if they have no element in common(Wikipedia description).
I have tried the following ideas so far:
- Let each clause in 3-CNF form be a set with each literal being its element. Our decision problem is "is it possible to find at least k-many disjoint sets?
- If we put each literal of a clause to a set and distinguish between a literal and its negation, it does not work since phi = $(x_1 \lor x_1 \lor x_1)$ and $(\neg x_1 \lor \neg x_1 \lor \neg x_1)$ is not satisfiable but it is considered as disjoint set.
- If we negate back all negated literals, then the set phi = ($x_1$ $\lor$ $x_2$ $\lor$ $x_3$) and $(\neg x_1 \lor \neg x_2 \lor \neg x_3)$ is considered as non-disjoint although this function is satisfiable.
Any help is appreciated.