M-clique covers in complete graphs

Question

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?

Answer 1

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 2

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 3

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.