2

我有一个作业问题，要求使用多项式算法来找到一个大小为 Ω(logn) 的集团。

我目前的实现如下：

  1. 将图划分为 n^logn 个大小为 logn 的微集（子图）并将它们存储为邻接矩阵
  2. 对于每个子图，蛮力检查 S 是否为大小为 logn 的集团
  3. 如果 S 是一个集团，则返回它。
  4. 如果我们在没有找到 clique 的情况下完成迭代，则返回 None（图中没有 logn cliques，这是最坏的情况）

构建子图将花费 n^k 时间。要检查一个子图是否是一个大小为 logn 的 clique 将花费 O((logn)^2)，因为子图中的每个顶点将有 k^2 个边（其中 k 是 clique 的大小，在这种情况下是 logn）。这必须对所有 n^logn 子间隙进行，因此总运行时间为 O(n^logn +(n^(logn))((logn)^2))。

我的问题是：

  1. 这是多项式，还是 k 作为指数使其成为指数
  2. 我的逻辑合理吗？
  3. 运行时间减少到什么程度？

谢谢大家！

编辑 1：我意识到在多项式时间内做到这一点的唯一方法是不创建 n^k 子图，而是将图划分为 n/k 个分量。但是，如果我这样做，则无法保证我的任何微集实际上都会有一个 k 大小的团，即使图中保证了一个。有没有办法解决？

编辑 2：我之前没有提到或考虑过的一件非常重要的事情是，我们得到 G 的集团规模为 n/2。因此，我们知道将 G 分成大小为 logn 的 n/logn 个子集的最坏情况将是当 n/2 的最大团被均匀地分成大小为 logn/2 个的团到每个子图中时。这保证了我们至少找到一个大小为 logn/2 的团，这满足找到一个大小为 Ω(logn) 的团。这也是多项式，因为它在 O(n/logn * n^(log2(3)/3) 时间内运行。抱歉没有早点提供这个！

4

0 回答 0