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.

Improve this question
$\endgroup$
4
  • $\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, 2017 at 0:59
  • $\begingroup$ Perhaps you should explain the problem "maximum disjoint set". $\endgroup$
    – Yuval Filmus
    Dec 13, 2017 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, 2017 at 12:51
  • $\begingroup$ You should answer your own question instead of editing. $\endgroup$
    – fade2black
    Dec 13, 2017 at 13:17

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\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, 2018 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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