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

Question

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!!!

Answer 1

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$