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 > 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).

  • $\begingroup$ Can you please explain why my interpretation only makes sense for bipartite graphs? $\endgroup$ – rookie Sep 16 '15 at 19:58
  • 1
    $\begingroup$ @rookie An edge connects a man and a woman. Unless you had a more modern interpretation in mind. $\endgroup$ – Yuval Filmus Sep 16 '15 at 20:32

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.