Show that maximum disjoint set problem is NP Complete 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.
Given MIS is NP-Complete, we can reduce MIS to MDS. Let $G = (V,E)$ the graph we have for MIS problem. For every vertex $v_i \in V$, create a set $S_i$ with edges of $v_i$, however, be careful that write each edge element as $v_iv_j$ even if it is $v_jv_i$. Reduction is completed after creating the sets $S_i$. There is an independent set in $G$ of size $m$ if, and only if, there are $m$ disjoint sets where sets are taken from independent set's vertices.

This reduction can be performed in polynomial time since we traverse each vertex $v$ and its edges. It can be performed in $O(V+E)$. Additionally, given a collection of sets, we can verify if they are disjoint and there are at least $k$ of them in polynomial time.

Consequently, MDS is NP-Complete