<p>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 <span class="math-container">$n = 6$</span> you can end up with extra edges that don't form any other maximal cliques otherwise:</p>

<p><a href="https://i.sstatic.net/5zczz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5zczz.png" alt="enter image description here"></a></p>

<p>If that assumption is correct, your operation is called a <em>bisection</em> of the graph. You want to maximize the remaining weights, and thus minimize the edge weights of the edges that are cut.</p>

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

CC BY-SA 4.0
2019-09-23T22:05:40.077Z
2019-09-23T22:05:40.077Z
orlp
<p><strong>Problem</strong>: Considering a complete weighted graph <span class="math-container">$G$</span> with <span class="math-container">$n$</span> vertices, where <span class="math-container">$n\in2\mathbb Z$</span> is an even number, remove edges in such a way that you end up with two cliques of graph <span class="math-container">$G$</span>, each having <span class="math-container">$\frac n2\in\mathbb Z$</span> vertices, and the sum of all weights is maximized.</p>

<p><strong>Example</strong>:</p>

<p><span class="math-container">$\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}$</span></p>

<p>The above adjacency matrix of graph <span class="math-container">$G$</span> is an instance of the problem with <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, <span class="math-container">$C$</span> and <span class="math-container">$D$</span> being the vertices of the graph. In this instance, the solution to the problem is pairing <span class="math-container">$A$</span> with <span class="math-container">$B$</span> <span class="math-container">$(1)$</span> and <span class="math-container">$C$</span> with <span class="math-container">$D$</span> <span class="math-container">$(0.33)$</span>, with the resulting weight sum <span class="math-container">$1.33$</span> being the maximum achievable value.</p>

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

<ds.algorithms><graph-theory><graph-algorithms><optimization><clique>
Dividing a complete graph into two cliques with maximal sum of edge weights
kskcp
# Dividing a complete graph into two cliques with maximal sum of edge weights

(Asked by: username_0 on 2019-09-23)

**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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, optimization, clique


---

## 1 answers

### Answer by username_1 on 2019-09-23. Score: 3 | Accepted 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:

[![enter image description here](https://i.sstatic.net/5zczz.png)](https://i.sstatic.net/5zczz.png)

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.


---

