Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
