2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I haven't thought of reframing it as an integer programming question. Thank you. It would be even better if there is some faster greedy method. From past experience, integer programming is often quite slow. $\endgroup$ Jan 3 at 4:51
  • $\begingroup$ @JaeyoonKim makes sense. Hopefully someone else will have a better answer. In the meantime... some ILP solvers have a timeout option, where they will return the best solution they were able to find within a set time period. $\endgroup$
    – D.W.
    Jan 3 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.