<p>This problem is NP-hard.  As proof, the maximal clique problem (or rather the decision variant find-a-K-clique) can be reduced to this problem as follows.</p>

<p>Start with a problem on a graph with N vertices where we wish to find a clique of size K.  The set containing these original vertices we'll call S. Add a clique (we'll call it C) of size (N - K)*K which is joined to every vertex in S.  Additionally, adjoin one more vertex V which is joined only to the vertices in S (not the ones in C).</p>

<p>Now we have an instance of your problem (never mind the edge weights) where we want to divide the resulting graph up into N - K + 1 cliques of size K+1.  I claim that there is a solution to this problem if and only if there is a clique of size K in the original graph.</p>

<p>only-if follows from the fact that V must belong to some clique of size K+1 which is only the case if there are K vertices which form a clique in S.</p>

<p>Furthermore, there will be enough leftover nodes in C that every S-vertex not in the solution clique can be assigned to a separate set of K vertices from C.  So once we've managed to find a clique for V, finding the other N-K (K+1)-cliques is always possible (and indeed trivial).</p>

<hr>

<p>So taking "efficient" to mean "polynomial time", then the answer to your question is "no", or more precisely, "only if P = NP"</p>

CC BY-SA 3.0
2014-01-17T01:01:53.667Z
2014-01-17T07:55:32.423Z
2014-01-17T07:55:32.423Z
dspyz
<p>There is of course a formulation of this as an integer linear program (ILP).  There's no reason to expect it to run in polynomial time, but off-the-shelf ILP servers are pretty good so it might yield decent solutions in practice if your graph isn't too large.</p>

<p>In particular, let $x_{i,v}$ be a 0-or-1 integer variable, with the intended meaning that $x_{i,v}=1$ means that the $i$th clique contains vertex $v$.  We obtain the linear equations</p>

<p>$$\sum_{v \in V} x_{i,v} = M$$
$$\sum_i x_{i,v} = 1$$</p>

<p>and the inequalities $0 \le x_{i,v} \le 1$.</p>

<p>Next, let $y_{i,u,v}$ be a 0-or-1 integer variable, with the intended meaning that $y_{i,u,v}=1$ if and only if $x_{i,u}=x_{i,v}=1$.  We obtain the linear inequalities</p>

<p>$$y_{i,u,v} \ge x_{i,u} + x_{i,v}-1, y_{i,u,v} \le x_{i,u}, y_{i,u,v} \le x_{i,v}, 0 \le y_{i,u,v} \le 1.$$</p>

<p>Finally, we wish to maximize/minimize</p>

<p>$$\sum_{i,u,v} y_{i,u,v} wt(u,v).$$</p>

<p>If you wish, you could add some symmetry-breaking by requiring that $\sum_{u,v} y_{i,u,v} wt(u,v) \le \sum_{u,v} y_{i+1,u,v} wt(u,v)$ for all $i$: it is possible that this might help the ILP solver a little bit.</p>

CC BY-SA 3.0
2014-01-17T00:32:38.947Z
2014-01-17T00:32:38.947Z
D.W.
<p>It is also interesting when M is a small constant >2. Unfortunately it is still NP-complete for M=3. Let G be an instance of the Partition-Into-Triangle (PIT) problem. Note that the number of nodes n is a multiple of 3. We construct a complete weighted graph H as an instance of your problem. The edge weight is one if it is in G, or otherwise two. Then, it is clear G can be partition into triangles iff your problem has a solution of cost n. The maximization version can be shown similarly. Consequently for any constant M>2, the problem is NP-hard, even when all edge weights are either one or two.   </p>

CC BY-SA 3.0
2014-01-18T10:11:50.713Z
2014-01-18T10:11:50.713Z
Bangye
<p>Let us consider a complete weighted graph, with $NM$ nodes.
Our objective is to find, among all possible combinations of $N$ disjoint $M$-cliques (each clique consisting of $M$ nodes), the configuration that maximizes/minimizes the sum of the $N$ $M$-cliques weights.
Here the weight of a $M$-clique is the sum of the edge weights between all the $M$ nodes composing the clique.</p>

<p>It sounds like a classical mathematical problem, but I have been spending hours without finding anything.
The special case where $M=2$ consists of a maximal weighted matching problem in a complete graph and can be solved using Edmonds Matching Algorithm, but I can't find anything for $M&gt;2$.</p>

<p>Is there an efficient algorithm for this problem?</p>

CC BY-SA 3.0
2014-01-21T15:43:58.423Z
Thank you for your time. The three of you have helped a lot to clarify the problem.
It sounds quite complicated to solve though, but I will give it a try, using your pieces of advice. Have a nice day ! M
MdM
<ds.algorithms><graph-theory><graph-algorithms><clique>
M-clique covers in complete graphs
MdM
# M-clique covers in complete graphs

(Asked by: username_0 on 2014-01-16)

Let us consider a complete weighted graph, with $NM$ nodes.
Our objective is to find, among all possible combinations of $N$ disjoint $M$-cliques (each clique consisting of $M$ nodes), the configuration that maximizes/minimizes the sum of the $N$ $M$-cliques weights.
Here the weight of a $M$-clique is the sum of the edge weights between all the $M$ nodes composing the clique.

It sounds like a classical mathematical problem, but I have been spending hours without finding anything.
The special case where $M=2$ consists of a maximal weighted matching problem in a complete graph and can be solved using Edmonds Matching Algorithm, but I can't find anything for $M>2$.

Is there an efficient algorithm for this problem?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, clique
> **Comments:**
> **username_0**: Thank you for your time. The three of you have helped a lot to clarify the problem. It sounds quite complicated to solve though, but I will give it a try, using your pieces of advice. Have a nice day ! M  

---

## 3 answers

### Answer by username_1 on 2014-01-17. Score: 2 | Accepted answer

This problem is NP-hard. As proof, the maximal clique problem (or rather the decision variant find-a-K-clique) can be reduced to this problem as follows.

Start with a problem on a graph with N vertices where we wish to find a clique of size K. The set containing these original vertices we'll call S. Add a clique (we'll call it C) of size (N - K)\*K which is joined to every vertex in S. Additionally, adjoin one more vertex V which is joined only to the vertices in S (not the ones in C).

Now we have an instance of your problem (never mind the edge weights) where we want to divide the resulting graph up into N - K + 1 cliques of size K+1. I claim that there is a solution to this problem if and only if there is a clique of size K in the original graph.

only-if follows from the fact that V must belong to some clique of size K+1 which is only the case if there are K vertices which form a clique in S.

Furthermore, there will be enough leftover nodes in C that every S-vertex not in the solution clique can be assigned to a separate set of K vertices from C. So once we've managed to find a clique for V, finding the other N-K (K+1)-cliques is always possible (and indeed trivial).

---

So taking "efficient" to mean "polynomial time", then the answer to your question is "no", or more precisely, "only if P = NP"


---

### Answer by username_2 on 2014-01-17. Score: 1

There is of course a formulation of this as an integer linear program (ILP). There's no reason to expect it to run in polynomial time, but off-the-shelf ILP servers are pretty good so it might yield decent solutions in practice if your graph isn't too large.

In particular, let $x\_{i,v}$ be a 0-or-1 integer variable, with the intended meaning that $x\_{i,v}=1$ means that the $i$th clique contains vertex $v$. We obtain the linear equations

$$\sum\_{v \in V} x\_{i,v} = M$$
$$\sum\_i x\_{i,v} = 1$$

and the inequalities $0 \le x\_{i,v} \le 1$.

Next, let $y\_{i,u,v}$ be a 0-or-1 integer variable, with the intended meaning that $y\_{i,u,v}=1$ if and only if $x\_{i,u}=x\_{i,v}=1$. We obtain the linear inequalities

$$y\_{i,u,v} \ge x\_{i,u} + x\_{i,v}-1, y\_{i,u,v} \le x\_{i,u}, y\_{i,u,v} \le x\_{i,v}, 0 \le y\_{i,u,v} \le 1.$$

Finally, we wish to maximize/minimize

$$\sum\_{i,u,v} y\_{i,u,v} wt(u,v).$$

If you wish, you could add some symmetry-breaking by requiring that $\sum\_{u,v} y\_{i,u,v} wt(u,v) \le \sum\_{u,v} y\_{i+1,u,v} wt(u,v)$ for all $i$: it is possible that this might help the ILP solver a little bit.


---

### Answer by username_3 on 2014-01-18. Score: 0

It is also interesting when M is a small constant >2. Unfortunately it is still NP-complete for M=3. Let G be an instance of the Partition-Into-Triangle (PIT) problem. Note that the number of nodes n is a multiple of 3. We construct a complete weighted graph H as an instance of your problem. The edge weight is one if it is in G, or otherwise two. Then, it is clear G can be partition into triangles iff your problem has a solution of cost n. The maximization version can be shown similarly. Consequently for any constant M>2, the problem is NP-hard, even when all edge weights are either one or two.


---

