4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – MdM Jan 21 '14 at 15:43
2
$\begingroup$

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"

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.