3
$\begingroup$

Suppose you had a set $P$ of people. Every person $p_j \in P$ is familiar with atleast one other person $p_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no two people in $S$ know each other? Show that the problem is NP-Complete.

Clearly this resembles the Maximum Independent Set problem, however, I am having trouble seeing how to do the reduction. My idea is to generate a graph $G'$ such that vertices represents people and an edge between two vertices means those two people know each other.

The problem is, this graph can be disconnected so any ideas as to how this can be reduced?

EDIT:

Take for instance this graph $G'$

One possible Maximum Independent Set is clearly $\{2,3,7,5\}$ but does it matter if the graph is disconnected?

$\endgroup$
  • $\begingroup$ Is familiarity symmetric? $\endgroup$ – Swapniel Aug 5 '14 at 12:50
  • $\begingroup$ 1) $k$ is not quantified, I assume you mean for a given input $P,k$ "is there $S$ such that $|S|\geq k$ and no two...". I also assume the relation symmetric. 2) Then your reduction from Max. Ind. Set seems correct. You just need the observation that given any input graph $G'$ any disconnected point from the graph belongs to the maximal independent set, so remove it when generating the set of people and familiarity relation. You then deduce the independent set from the subset $S$ by adding those points. In short: you easily get rid of the assumption that everybody is familiar with someone. $\endgroup$ – Joseph Stack Aug 5 '14 at 13:31
  • $\begingroup$ Yes the relationship between two people is symmetric i.e they know each other. $\endgroup$ – 1337holiday Aug 5 '14 at 18:01
  • 1
    $\begingroup$ I don't see why this only resembles the independent set problem, in my eyes it simply is the independent set problem. Or am I missing something? And I don't think it matters whether the graph is connected or not. $\endgroup$ – john_leo Aug 6 '14 at 10:16
  • $\begingroup$ @john_leo yes, it was mainly for clarification, unfortunately I can't close the question. If you answer it, ill just accept it. $\endgroup$ – 1337holiday Aug 6 '14 at 16:50
4
$\begingroup$

Your problem, as stated, is already the independent set problem, as defined e.g. on Wikipedia.
A very similar NP-Complete problem is Clique, which is part of Karp's original 21 NP-complete problems, where, given a graph $G$ and an integer $k$, you try to find a complete subgraph of size $k$. It is easy to see that looking for an independent set in a graph is the same as looking for a clique in its complement graph.
In Karp's paper one can also find a straightforward reduction from SAT to Clique, and the reduction does not depend on whether the graph is connected or not. Hence it does not matter whether your graph is connected or disconnected.

$\endgroup$

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.