# 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?

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 > 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 > 0$ (see Chalermsook, Laekhanukit and Nanongkai).