Given a graph with at most 2*10^5 nodes and 2*10^5 edges, bicolor the graph such that the difference between the number of nodes with each color is minimized, and print out that difference.
I am able to bicolor each of the connected components, and find the number of each color in each component. I tried to make the final step of finding the minimum difference into the subset sum problem before realizing that there are restrictions on what numbers can go together.
E.g. I have components (Red, Blue) as (1, 5) and (2, 4); the optimal subset sum solution would normally be to put the 1 and 5 together, and the 2 and 4 together. However, the (1, 5) pair and (2, 4) pair are component pairs, which is not allowed.
Please help, and thanks in advance!
You can use a knapsack algorithm in SsqrtS with S being the sum of values. You can find out more about it in the editorial and discussions of this problem. Let N be the total number of nodes. Let's say we have a pair (A, B) with A<=B. We add A to the value Left and B — A to an array v. Now, all you need to do is to choose some items from the array v so that their sum plus Left will be as close as possible to N / 2, which you can do with that modified version of knapsack. I denoted that sum by Left because it'll account for the number of nodes on the left side.