Party optimization: maximum weight independent set in a tree/graph From Cornell 


  Suppose we want to throw a party for a company whose organization
  chart is a binary tree. Each employee has an associated fun value, and
  we want the set of invited employees to have the maximum total fun,
  which is the sum of the fun values of the invited employees. However,
  no one has fun if some employee and that employee's direct superior
  are both invited, so we never invite two employees who are directly
  connected in the organization chart. (The less whimsical name for this
  problem is the maximum weight independent set in a tree.)


I was trying to think of an analogous statement if the problem were a graph rather than a tree. Might we say that now we want to throw the largest possible party with ex-girlfriends/ex-boyfriends such that no one's ex-partner is invited? 

In this case an edge between two members denotes a ex-relationship. We want to find the largest set such that no two members share an edge.

Is this a correct interpretation of the graph problem and is there a known polynomial time algorithm?
You can interpret a graph problem in whatever way you wish. Note that your interpretation makes sense only for bipartite graphs.

Maximum independent set, even with all weights the same, is (almost) NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any fixed $\epsilon &gt; 0$ (here $n$ is the number of vertices); the actual hardness assumption is NP$\not\subseteq$BPP rather than P$\neq$NP (see for example Anupam Gupta's lecture notes). Under the exponential time hypothesis, any $r$-approximation algorithm must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ for any $\epsilon &gt; 0$ (see Chalermsook, Laekhanukit and Nanongkai).