# Maximum variance partitioning graph into disjoints cliques

I am working on the following problem: Let $$G = \left(V, E\right)$$ an undirected graph such that every vertex $$i\in V$$, has a label $$x_i \in \mathbb R$$. For every vertex subset $$S \subset V$$, we define $$\text{Var}(S) = \frac1{|S|} \sum_{i \in S} \left(x_i - \frac1{|S|} \sum_{j\in S} x_j\right)^2$$ the variance of $$S$$. The question asks for partitioning $$G$$ into disjoint cliques $$\left(C_k\right)_{k}$$ in order to maximize the total variance $$\sum_{k}\text{Var}\left(C_k\right).$$ I think that K-means can be used here but I do not know how? Can anyone helps me to find an idea for solving this problem?

• wait what is "the question"? Can you be more specific please? May 14, 2019 at 9:28
• The question is to find an algorithm or a heuristic to have the best partition. May 14, 2019 at 18:34
• that is computer science, not math. "algorithm" is very annoying to define rigorously May 14, 2019 at 19:43
• Do the labels have anything to do with the graph structure? Your definition of variance doesn't seem to use the fact that there are edges at all. May 14, 2019 at 20:10
• Oh, I see, you also require that every cluster is a clique, i.e. is a complete subgraph? In that case you're unlikely to have an efficient algorithm to do this - even checking whether graph has a k-clique of size k is NP complete. So if your plan is to do optimization on the space of all cliques, you might be able to do only slightly better than brute force. May 14, 2019 at 21:05