Dividing a complete graph into two cliques with maximal sum of edge weights

Question

Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\frac n2\in\mathbb Z$ vertices, and the sum of all weights is maximized.

Example:

$\begin{bmatrix} &A & B & C & D\\ A &0 &1 &0.66 &0.5\\ B &1 &0 &0.01 &0.5\\ C &0.66 &0.01 &0 &0.33\\ D &0.5 &0.5 &0.33 &0 \end{bmatrix}$

The above adjacency matrix of graph $G$ is an instance of the problem with $A$, $B$, $C$ and $D$ being the vertices of the graph. In this instance, the solution to the problem is pairing $A$ with $B$ $(1)$ and $C$ with $D$ $(0.33)$, with the resulting weight sum $1.33$ being the maximum achievable value.

What would be the exact algorithm for solving this problem, or maybe there is a problem which it can be reduced to?

Answer 1

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 weights, and thus minimize the edge weights of the edges that are cut.

This problem is NP-complete, and you can find a reduction in "Some simplified NP-complete graph problems" by M. R. Garey, D. S. Johnson, and L. Stockmeyer in Theorem 1.3 and the preceding paragraph.