3
I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for $n = 6$ you can end up with extra edges that don't form any other maximal cliques otherwise:
If that assumption is correct, your operation is called a bisection of the graph. You want to maximize the remaining ...
3
With an idea by Louis Jachiet, we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the $b$'s by decreasing "ending time" (i.e., by increasing $q_i$ above), consider the $b$'s by intervals of "starting time" (the $p_i$ above), and restrict the search to greedy schedulings that follow the ...
1
To me it was somewhat surprising that minimal vertex cover is a subproblem of the Hungarian Algorithm, namely when determining a minimal set of horizontal or vertical lines that cover all the zeros that were generated by subtracting row and column minima.
That amounts to finding a minimal vertex cover in a bipartite graph which, also surprisingly, can be ...
Only top voted, non community-wiki answers of a minimum length are eligible
