最大重量K-集团在一个完整的K-部图 [英] max-weight k-clique in a complete k-partite graph

问题描述

我的问题

是否有一个有效的算法来找到一个最大权重（或最小重量）的 K - 的在一个完整的 K -partite图集团（图中的顶点相邻当且仅当它们属于不同的部集根据的维基）？

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)?

有关条款的更多详细信息

最大重量派：图中的每条边有一个权重。一集团的重量是在集团所有边的权重的总和。的目标是找到具有最大重量小集团。

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.

请注意，该集团的大小为k它是在一个完整的K-部图的最大可能团大小。

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

我已经试过

我一个项目中遇到了这个问题。由于我不是一个CS的人，我不知道有关的复杂性等。

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

我用Google搜索一些相关的文章，但没有人涉及的是同样的问题。我也编一个贪心算法+模拟退火处理它（的结果似乎并不好）。我也试着像动态规划（但它似乎并没有有效）。所以，我不知道是否准确的最佳可以有效地计算出来。先谢谢了。

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.

修改因为我的投入可真大（如顶点的每个集团的数量是2 ^ K），我希望能找到一个真正的快速算法（如K的时间多项式），其工作出最佳效果。如果这是不可能的，能证明某些下界的复杂性？

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?

推荐答案

在加权图的最大团问题一般是棘手。你的情况，如果图形中包含N个节点，则可以通过所有可能的K-拉帮结派的N **亩的时间一一列举。如果k是固定的（不知道是不是），你的问题是平凡多项式可解的，因为这是N的多项式，我不相信这个问题是容易处理，如果k是一个自由参数，因为我不能怎么看的k部图的假设，将使从一般的问题显著简单。

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.

这篇关于最大重量K-集团在一个完整的K-部图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！