Dividing a complete graph into two cliques with maximal sum of edge weights 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}      
&amp;A  &amp;  B &amp;   C &amp;   D\\
A   &amp;0    &amp;1    &amp;0.66 &amp;0.5\\
    B   &amp;1    &amp;0    &amp;0.01 &amp;0.5\\
    C   &amp;0.66 &amp;0.01 &amp;0    &amp;0.33\\
    D   &amp;0.5  &amp;0.5  &amp;0.33 &amp;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?
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.