max-weight k-clique in a complete k-partite graph

Question

My Problem

Whether there's an efficient algorithm to find a max-weight (or min-weight) k-clique in a complete k-partite graph (a graph in which vertices are adjacent if and only if they belong to different partite sets according to wikipedia)?

More Details about the Terms

Max-weight Clique: Every edge in the graph has a weight. The weight of a clique is the sum of the weights of all edges in the clique. The goal is to find a clique with the maximum weight.

Note that the size of the clique is k which is the largest possible clique size in a complete k-partite graph.

What I have tried

I met this problem during a project. Since I am not a CS person, I am not sure about the complexity etc.

I have googled several related papers but none of them deals with the same problem. I have also programmed a greedy algorithm + simulated annealing to deal with it (the result seems not good). I have also tried something like Dynamic Programming (but it does not seem efficient). So I wonder whether the exact optimal can be computed efficiently. Thanks in advance.

EDIT Since my input can be really large (e.g. the number of vertices in each clique is 2^k), I hope to find a really fast algorithm (e.g. polynomial of k in time) that works out the optimal result. If it's not possible, can we prove some lower bound of the complexity?

Shiprigged

What do you mean by weight? – Chimere

@ColonelPanic Each edge in the graph has a weight. The weight of a clique is the sum of the weights of all edges in the clique. – Shiprigged

yeah forget my comment on spanning tree... i misread your text and already deleted my wrong comments :) – Madox

@fordprefect thank you for your attention anyway:) – Shiprigged

This may be useful for you - engineering.uiowa.edu/~krokhmal/pdf/bitCLQ.pdf – Autoerotism

Answer 1

The maximum clique problem in a weighted graph in general is intractable. In your case, if the graph contains N nodes, you can enumerate through all possible k-cliques in N ** k time. If k is fixed (don't know if it is), your problem is trivially polynomially solvable, as this is a polynomial in N. I don't believe the problem to be tractable if k is a free parameter because I can't see how the assumption of a k-partite graph would make the problem significantly simpler from the general one.

How hard your problem is in practice depends also on how the weights are distributed. If all the weights are very near to each others, i.e. the difference between "best" and "good" is relatively small, the problem is very hard. If you have wildly different weights on the edges, the problem can be easier, because a greedy algorithm can give you a good "initial" solution, and you can use that and subsequent good solutions to limit your combinatorial search using the well-known branch-and-bound method.

Went

Thank you. If the k is fixed, do you think there's an even better algorithm (e.g. NlogN algorithm) for this problem, since my N can be really large (e.g. 2^k)? – Shiprigged

No, I don't really think so. This is a hard problem. – Went

Answer 2

Generalized Maximum Clique Problem (GMCP)

• I understand that you are looking for the Generalized Maximum/ minimum Clique Problem (GMCP), where finding the clique with maximum score or minimum cost is the optimization problem.
• This problem is a NP-Hard problem as shown in Generalized network design problems, so there is currently no polynomial time exact solution to your problem.
• Since, there is no known polynomial solution to your problem, you have 2 choices. Reducing the problem size to find the exact solution or to find an estimated solution by relaxing your problem and it leads you to a an estimation to the optimal solution.

Example and solution for the small problem size

• In small k-partite graphs (in our case k is 30 and each partite has 92 nodes), we were able to get the optimal solution in a reasonable time by a heavy branch and bounding algorithm. We have converted the problem into another NP-hard problem (Mixed Integer Programming), reduced number of integer variables, and used IBM Cplex optimizer to find the optimal solution to GMCP.
• You can find our project page and paper useful. I can also share the code with you.

How to estimate the solution

• One straight forward estimation to this NP-Hard problem is relaxing the Mixed Integer Programming problem and solve it as a linear programming problem. Of course it will give you an estimation of the solution, but still you might get a reasonable answer in practice.

More general problem (Generalized Maximum Multi Clique Problem)

• In another work, we solve the Generalized Maximum Multi Clique Problem (GMMCP), where maximizing the score or minimizing the cost of selecting multiple k-cliques in a complete k-partite graph is in interest. You can find the project page by searching for GMMCP Tracking.

Mercier

The project pages have gone 403. However, I think I managed to track down the paper referenced: doi.org/10.1109/CVPR.2015.7299036 – Eurhythmics