rsj's blog

By rsj, history, 4 months ago, In English

Problem Source.

I cannot find an clear editorial about it. Can you help me with

How this DP works?

How to combine the answers(meet)?

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you very much! I'll check it out now.