Maximum weight independent set with divide and conquer

Question

I was reading about the Maximum Weight Independent Set problem which is:

Input: An undirected graph G = (V, E)and a non-negative weight Wv for each vertex v ∈ V

Output: An independent set S ∈ V of G with the maximum-possible sum ∑Vw of vertex weights

and that same source (not the SO post) mentions that the problem can be solved by 4 recursive calls with a divide & conquer approach.
I googled but couldn't find such an algorithm. Does anyone have an idea how would this be solved by divide & conquer? I do understand that the running time is much worse than the Dynamic Programming I am just curious on the approach

Answer 1

I understand the part in the manuscript in such a way that only line graphs are taken into consideration. In that case, I believe the footnote to mean the following.

If a larger line graph is taken as input and split (say at an edge which in incident with the nodes a and b), there are four cases to consider to have a proper combination step.

You would have to solve the "left" branch by solving for the cases

• a is included in the maximum independent set
• a is not included in the maximum independent set

and the same goes for the "right" branch. In total there are four possible ways to combine the results, out of which a maximal one is to be returned.