Hello!

It may be fruitful to take a look at problem 1105E - Helping Hiasat . Also check out this comment.

Anyways, I will try to summarize the solution. First, observe you can reduce Max Independent Set to Max Clique by considering the complement graph. You then solve it using meet-in-the-middle. The main idea is to break the graph nodes into two halves and first find the max clique size for every subset of each half using DP.

Now, to "meet", you have to consider cliques which intersect both halves. The trick is to loop over all subsets of nodes in the second half (say we are currently considering $$$S_2$$$). If $$$S_2$$$ is not a clique, ignore it. Otherwise, construct the set $$$S_1$$$ of all nodes of the first half which have edges to all the nodes in $$$S_2$$$ (so that together they still form a clique shared by both halves). Since you have already precomputed the size of the max clique existing in $$$S_1$$$ using DP, you know that the "meeting" answer is $$$dp[S_1] + |S_2|$$$. Then you simply take the maximum over all the subsets you considered. The problem you linked to also asks for the actual nodes in a maximum independent set, but this is just a matter of reconstructing the solution (say, save the actual subsets instead of their sizes).

Overall it will take $$$O(2^{n/2} \cdot n^2)$$$ or $$$O(2^{n/2} \cdot n)$$$, depending on the way you represent the graph (I advise you to implement neighbour lists as bitmasks).

Hope it helped!

This is pretty old but may someone need this reference some day