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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Is familiarity symmetric? $\endgroup$
    – Swapniel
    Commented Aug 5, 2014 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
    Commented Aug 5, 2014 at 13:31
  • $\begingroup$ Yes the relationship between two people is symmetric i.e they know each other. $\endgroup$
    – 1337holiday
    Commented Aug 5, 2014 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
    Commented Aug 6, 2014 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
    Commented Aug 6, 2014 at 16:50

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

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

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