0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – csTheoryBeginner Dec 13 '17 at 0:59
  • $\begingroup$ Perhaps you should explain the problem "maximum disjoint set". $\endgroup$ – Yuval Filmus Dec 13 '17 at 12:51
  • $\begingroup$ 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. $\endgroup$ – Oğuzhan Karakahya Dec 13 '17 at 12:51
  • $\begingroup$ You should answer your own question instead of editing. $\endgroup$ – fade2black Dec 13 '17 at 13:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jan 12 '18 at 14:42

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.