0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Looks like this should be NP-hard, via a reduction to MAX-CLIQUE or the CLIQUE decision problem. All weights equal to $1$, number of nodes in $G$ being $N$, target clique size being $k$: let $A=\{N-k,k\}$. $\endgroup$ – Clement C. Aug 12 '18 at 20:12
  • $\begingroup$ @ClementC. But deciding if a graph can be partitioned into two cliques isn't hard (I don't know about having a given target size for these two cliques though). $\endgroup$ – Manuel Lafond Aug 13 '18 at 13:56
  • $\begingroup$ The target size is the key... $\endgroup$ – Clement C. Aug 13 '18 at 14:12
  • $\begingroup$ If there are no "good" algorithms, are there any "bad" algorithms that are better than brute force? $\endgroup$ – Martin Aug 15 '18 at 7:14

Your Answer

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

Browse other questions tagged or ask your own question.