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.

$\endgroup$
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.

$\endgroup$
  • $\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 '16 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 '16 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 '16 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 '16 at 23:28

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.