# 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} &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?

## 1 Answer

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.