# NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

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?

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.
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$$