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


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


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.