1
$\begingroup$

I'd like to show that the language DISCONNECTED-SET, defined by $$ \{\langle G, k\rangle | \text{$G$ is an undirected graph that contains a disconnected set of size $k$}\},$$ is NP-complete. (A disconnected set $S$ is defined as a set of vertices such that for every pair of vertices $u,v \in G$, if there is no edge between $u$ and $v$, then at least one of the vertices is in $S$.)

I'm under the assumption that it could be done by reduction from CLIQUE. I've made the following observations (which I'm unable to utilize, though):

  • If we have a graph $G$, then the maximum disconnected set of its complement $G'$ has a size equal to the number of nodes in $G$ that belong to connected components of size at least 2 in $G$.
  • If we have isolated nodes in $G$, the sizes of the disconnected sets in $G'$ are unchanged.

May I just ask for a tiny tip that would get me going in the right direction, not a complete proof. Thank you.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

This is just VERTEX-COVER in disguise. The reduction from CLIQUE is also simple – a set is disconnected iff its complement is a clique.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm sorry, I don't see how the last statement is true. Might it be that you are confusing the language INDEPENDENT-SET to the one under discussion, the language DISCONNECTED-SET (see the definition in my original post). $\endgroup$
    – stensootla
    Dec 17, 2016 at 22:38
  • $\begingroup$ Nevertheless, it is true, just as the complement of a vertex cover is an independent set and vice versa. $\endgroup$
    – Yuval Filmus
    Dec 17, 2016 at 22:41
  • $\begingroup$ Your problem is the same as VERTEX-COVER (exercise). Look up any proof of the NP-completeness of VERTEX-COVER. $\endgroup$
    – Yuval Filmus
    Dec 17, 2016 at 23:00
  • $\begingroup$ Oh, my bad, at my first reading, I assumed you were talking about the graphs G and G' that contain the disconnected sets and cliques. In any case, I was able to show a reduction from VERTEX-COVER to my problem, as you suggested. Thanks. $\endgroup$
    – stensootla
    Dec 17, 2016 at 23:28

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.