Algorithm for cliques in weighted graph

Question

Is there a known algorithm (besides brute force) for the following problem:

We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (to begin with we can just assume that $A$ has only one element). We want to decompose $G$ in cliques whose size is an element of $A$ and such that the sum of all edges of these cliques is maximal. (If this is not possible, e.g., in the case when $A = \lbrace n \rbrace$ and $n$ is not a divisor of the number of vertices of $G$, we are allowed to add vertices and edges (with weight $0$) to $G$.)

This is a modeling for the following problem: Given a group of people, a "friendship index" between each two people and a hotel with rooms of size $n_1,\ldots,n_k$, determine the optimal room division.

I have posted this question (some time ago) also at MathStackExchange, but without answer.

Answer 1

The problem is at least as hard as 3-edge coloring of 3-regular graphs:

Suppose $\Gamma$ is the graph to be 3-edge-colored. Let $L(\Gamma)$ be the line graph of $\Gamma$. Let $G$ be the complete graph with order $|L(\Gamma)|$.

Assign the weights in $G$ as follows: $-1$ if the edge is in $L(\Gamma)$, and 0 otherwise. Let $A= \lbrace {|\Gamma|/2} \rbrace$.

Then $L(\Gamma)$ must be partitioned into 3 groups, and the largest sum, $0$, is attained iff the groups are all independent sets in $L(\Gamma)$, which gives a 3-edge coloring of $\Gamma$.

Thus, there is a reduction from 3-edge coloring of 3-regular graphs, which is NP-complete, to your problem.