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.


$\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 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:

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.