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.


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.


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.