用于查找大小为 Ω(logn) 的团伙的多项式时间算法
我有一个家庭作业问题，要求使用多项式算法来找到大小为 Ω(logn) 的团。
我当前的实现如下：
- 将图划分为大小为 logn 的 n^logn 个微集（子图）并将它们存储为邻接矩阵
- 对于每个子图，强力检查 S 是否是大小为 logn 的团
- 如果 S 是团，则返回它。
- 如果我们完成迭代而没有找到团，则返回 None （图中没有 logn 团，这是最坏的情况）
构建子图将花费 n^k 时间。要检查子图是否是大小为 logn 的团，将需要 O((logn)^2)，因为子图中的每个顶点将有 k^2 条边（其中 k 是团大小，在本例中为 logn）。必须对所有 n^logn 子间隙执行此操作，因此总运行时间将为 O(n^logn +(n^(logn))((logn)^2))。
我的问题是：
- 这是多项式，还是 k 作为指数使其呈指数形式
- 我的逻辑合理吗？
- 运行时间减少到什么程度？
谢谢大家！
编辑1：我意识到在多项式时间内做到这一点的唯一方法是不创建 n^k 个子图，而是将图划分为 n/k 个分量。然而，如果我这样做，就无法保证我的任何微集实际上都会有一个 k 大小的团，即使图中保证有一个团。有什么办法可以解决这个问题吗？
编辑 2：我之前没有提到或考虑的一件非常重要的事情是，我们知道 G 的团大小为 n/2。 因此，我们知道，当将 n/2 的最大团均匀地分成大小为 logn/2 的团到每个子图中时，将导致将 G 分成大小为 logn 的 n/logn 子集的最坏情况。这保证了我们至少找到一个大小为 logn/2 的团，这满足了找到大小为 Ω(logn) 的团。这也是多项式，因为它运行时间为 O(n/logn * n^(log2(3)/3) 时间。很抱歉没有早点提供这个！
I have a homework question asking for a polynomial algorithm to find a clique of size Ω(logn).
My current implementation is as follows:
- Divide the graph into n^logn microsets (subgraphs) of size logn and store them as adjacency matrices
- For each subgraph, brute force check if S is a clique of size logn
- If S is a clique, return it.
- If we finish iterating without finding a clique, return None (no logn cliques in graph, which is the worst case)
Building the subgraphs will take n^k time. To check if a subgraph is a clique of size logn will take O((logn)^2), as each vertex in the subgraph will have k^2 edges (where k is the clique size, which in this case is logn). This must be done for all n^logn subgaphs, so the total runtime would be O(n^logn +(n^(logn))((logn)^2)).
My questions are:
- Is this polynomial, or does the k as an exponent make it exponential
- Is my logic sound?
- What does the runtime reduce to?
Thanks y'all!
EDIT 1: I realize that the only way to do this in polynomial time is going to involve not creating n^k subgraphs, but rather dividing the graph into n/k components. If I do this, however, there is no way to guarantee that any of my microsets will actually have a k-sized clique even if one is guaranteed in the graph. Is there any way around this?
EDIT 2: One VERY important thing that I failed to mention or consider earlier was that we are given that G has a clique size of n/2.
Because of this, we know that the worst case for separating G into n/logn subsets of size logn will result when the maximum clique of n/2 is evenly separated into size logn/2 cliques into each subgraph. This guarantees that we find at least one clique of size logn/2, which satisfies finding a clique of size Ω(logn). This is also polynomial, as it runs in O(n/logn * n^(log2(3)/3) time. Apologies for not providing this earlier!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论