# Graph partition that maximize the number of triangles within its parts

Given a graph $$G = (V,E)$$, how to partition $$V$$ into $$k$$ parts $$P_1, P_2, \ldots P_k$$ of at most $$M$$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?

This seems NP-complete. Was this problem studied before? (I couldn't find anything after searching clique graph partition). Furthermore, I would appreciate a heuristic approach to solve it.

I don't know whether there are any good heuristics, but I can suggest one approach: you could try to use an ILP solver on this task. Introduce zero-or-one variables $$x_{i,v}$$, $$y_{i,u,v,w}$$, where $$x_{i,v}=1$$ means that vertex $$v$$ is contained in partition $$P_i$$, and $$y_{i,u,v,w}=1$$ means that $$u,v,w$$ are a 3-clique in $$P_i$$. (Only introduce variables $$y_{i,u,v,w}$$ for triples of vertices $$u,v,w$$ that are a 3-clique in the original graph $$G$$; all others are effectively hardcoded at 0.) You can add constraints $$y_{i,u,v,w} \ge x_{i,u} + x_{i,v} + x_{i,w} - 2,$$ $$y_{i,u,v,w} \le x_{i,u}, y_{i,u,v,w} \le x_{i,v}, y_{i,u,v,w} \le x_{i,w},$$ $$\sum_v x_{i,v} \le M, \sum_i x_{i,v}=1.$$ Then, maximize the objective function $$\sum_{i,u,v,w} y_{i,u,v,w}$$ subject to these constraints, using an off-the-shelf ILP solver.