Maximum-weight set of cliques of size 3 with no common vertices in undirected graph
This problem is NP-complete even when all edge weights are 1, since that restriction is equivalent to the problem Partition Into Triangles, which &quot;Computers and Intractability&quot; (Garey and Johnson, 1979) lists as NP-complete on p. 192, attributing the result to a personal communication from T. J. Schaefer in 1974, apparently based on a reduction from 3-Dimensional Matching.
So, no efficient algorithm can be expected. For an exponential-time exact algorithm, I would probably try branch and bound intertwined with maximum bipartite (2-)matching, as follows: At each stage, we have a vertex $v_i$, which we will take to be the lowest-numbered vertex of a triangle, and the decision is which of its neighbour vertices $v_j$ should become the highest-numbered vertex in the triangle. For each possible $v_j$, to test feasibility of the choice, create a new, bipartite graph with a vertex for each low+high vertex pair decided so far, as well as a vertex for each as-yet unprocessed vertex, and an edge between two vertices whenever the low+high pair represented by one would form a triangle in the original graph with the other and the latter vertex is numbered between the low and high vertices represented by the former. Run maximum bipartite matching on this new graph, and check that every low+high pair decided so far is saturated (adjacent to a matched edge) -- if this fails, then the current assignment of low+high vertices cannot be extended to a full triangle partition and the branch can be pruned. I think this algorithm, which chooses just 2 vertices within each triangle, will result in B&amp;B tree depths of around 2/3rds the fully naive approach in which all 3 vertices of each triangle are chosen.