# 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:

1. 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?
2. 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.
3. 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.

• MDS is a special case of Maximum independent set (MIS) problem, special case because we assume no geometry regarding the shapes. Perhaps looking at ways in which 3-SAT has been reduced to MIS can be helpful. Commented Dec 13, 2017 at 0:59
• Perhaps you should explain the problem "maximum disjoint set". Commented Dec 13, 2017 at 12:51
• Thank you very much. I have managed to reduce it from MIS. I will now edit the question so that whoever needs this can learn. Commented Dec 13, 2017 at 12:51
• You should answer your own question instead of editing. Commented Dec 13, 2017 at 13:17

## 1 Answer

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

• Small point: when we write an edge as $xy$, that is treated as an abbreviation for the undirected edge $\{x,y\}$. As such, $xy=yx$ by definition. But that is something one would have to be careful about if implementing this reduction. Commented Jan 12, 2018 at 14:42