Party optimization: maximum weight independent set in a tree/graph
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).