<p>You can notice that <span class="math-container">$SN_i$</span> is maximum if <span class="math-container">$P_i$</span> is a clique of size <span class="math-container">$|P_i|$</span>.</p>

<p>So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts <span class="math-container">$P_i$</span> have the same size.</p>

<p>But the problem of partitioning a graph into 3 cliques of the same size is still NP-complete.</p>

<p>Indeed 3-COLORING remains NP-complete even if we require that all color classes have the same size (I'll call it EQUAL SIZE 3-COLORING). A quick proof idea is: given <span class="math-container">$G$</span> make 3 copies of it <span class="math-container">$G_1, G_2, G_3$</span>, pick the same node <span class="math-container">$v$</span> in each copy of <span class="math-container">$G$</span>: (<span class="math-container">$v_1, v_2, v_3 $</span>) and "link" them to form a clique <span class="math-container">$K_3$</span>. <span class="math-container">$G$</span> is 3 colorable if and only if <span class="math-container">$G' = G_1 \cup G_2 \cup G_3 \cup K_3$</span> is 3 colorable with equal size color classes.</p>

<p>But EQUAL SIZE 3-COLORING a graph <span class="math-container">$G$</span> with <span class="math-container">$3n$</span> nodes is equivalent to find 3 cliques of size <span class="math-container">$n$</span> in its dual <span class="math-container">$\bar G$</span>. Which is also equivalent to partition <span class="math-container">$\bar G$</span> into 3 parts with a total sum <span class="math-container">$\sum SN_i = 3n$</span> </p>

CC BY-SA 4.0
2020-04-20T10:38:32.667Z
2020-04-20T21:57:37.270Z
2020-04-20T21:57:37.270Z
Marzio De Biasi
<p>Given a graph <span class="math-container">$G=\{V,E\}$</span> where <span class="math-container">$V$</span> denotes the nodes and <span class="math-container">$E$</span> denotes edges. The size of the node <span class="math-container">$|V| = nk$</span>. The target is to separte the graph into <span class="math-container">$n$</span> disjoint parts <span class="math-container">$P=\{V_i\}_{i=1}^n$</span> and the size of every part is the same, i.e., <span class="math-container">$k$</span>. The goal is to maxmize the sum of the shared neighbors of every part, which can be difined as:
<span class="math-container">\begin{gather}
    \sum_{i=1}^m SN_{i}\\
    s.t. \quad\qquad SN_{i} = \cap_{v_i \in P_i} Nei(v_i)\\
    |P_i| = k\\
    \qquad \sum_{i=1}^m |P_i| = nk
\end{gather}</span></p>

<p>where <span class="math-container">$SN_{i}$</span> is the shared neighbours of the nodes in part <span class="math-container">$P_i$</span>. For convenience, we regard that the node is the neighbour of itself.</p>

<p>I think the problem is np-hard. In my view, we can construct a specific graph which contains n k-clique. We then think about it as a clique-cover problem. However, I think the solution is a little strange... How should we prove it? </p>

<p>Thanks in advance!!! </p>

<co.combinatorics><np-hardness><partition-problem>
NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part
Refrain
# NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

(Asked by: username_0 on 2020-04-20)

Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V\_i\}\_{i=1}^n$ and the size of every part is the same, i.e., $k$. The goal is to maxmize the sum of the shared neighbors of every part, which can be difined as:
\begin{gather}
\sum\_{i=1}^m SN\_{i}\\
s.t. \quad\qquad SN\_{i} = \cap\_{v\_i \in P\_i} Nei(v\_i)\\
|P\_i| = k\\
\qquad \sum\_{i=1}^m |P\_i| = nk
\end{gather}

where $SN\_{i}$ is the shared neighbours of the nodes in part $P\_i$. For convenience, we regard that the node is the neighbour of itself.

I think the problem is np-hard. In my view, we can construct a specific graph which contains n k-clique. We then think about it as a clique-cover problem. However, I think the solution is a little strange... How should we prove it?

Thanks in advance!!!

**Tags:** co.combinatorics, np-hardness, partition-problem

---

## 1 answers

### Answer by username_1 on 2020-04-20. Score: 3 | Accepted answer

You can notice that $SN\_i$ is maximum if $P\_i$ is a clique of size $|P\_i|$.

So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts $P\_i$ have the same size.

But the problem of partitioning a graph into 3 cliques of the same size is still NP-complete.

Indeed 3-COLORING remains NP-complete even if we require that all color classes have the same size (I'll call it EQUAL SIZE 3-COLORING). A quick proof idea is: given $G$ make 3 copies of it $G\_1, G\_2, G\_3$, pick the same node $v$ in each copy of $G$: ($v\_1, v\_2, v\_3 $) and "link" them to form a clique $K\_3$. $G$ is 3 colorable if and only if $G' = G\_1 \cup G\_2 \cup G\_3 \cup K\_3$ is 3 colorable with equal size color classes.

But EQUAL SIZE 3-COLORING a graph $G$ with $3n$ nodes is equivalent to find 3 cliques of size $n$ in its dual $\bar G$. Which is also equivalent to partition $\bar G$ into 3 parts with a total sum $\sum SN\_i = 3n$


---

