固定k的顶点封面的时间复杂度与固定的clique

Question

我有两种方法解决了固定大小的独立设置问题 $ k $ 图表 $ g=（v，e）$ ：
- 在 $ o ^ *（1.47 ^ {v - k}）$ （优化递归算法）中运行的顶点覆盖算法 - 在 $ o（{v \ choical k}）中运行的Clique算法>（简单枚举 $ v $ 和检查算法）

如何确定哪一个具有较低的时间复杂性？我对NP完整问题的算法和 $ o ^ * $ 表示法不太熟悉。会绘制这些功能是否足够？我认为VC算法可以具有任何多项式 $ n ^ {o（1）} $ 作为乘法，因为 $o ^ * $ 表示法，这可能会影响运行时间，但我不确定。

Answer 1

对于任何固定的 $ k $ ， $ o（\ binom {v} {k}）= o（v^ k）$ 是多项式，而<跨度类=“math-container”> $ o ^ *（1.47 ^ {vk}）= o ^ *（1.47 ^ v）$ 是指数。指数比多项式增长得多。

绘制曲线并不是如此有帮助，因为这些是渐近语句。

表示，如果您对特定 $ v $ 和 $ k$ ，那么您的最佳选择是经验检查这些算法中哪一个更快。渐近表示法在这里没有帮助，因为它隐藏了恒定因素，并且这些可以对 $ v $ 和 $ k $ 。

Answer 2

顶点盖子是固定参数的易动。 有一个简单 $ 2 ^ k n $ 算法，找到一个大小的vc $ k $ 。 这应该击败天真的算法。 本领域的当前状态是 $ 1.24 ^ K n $ 。

在一些假设下，没有运行时间 $ f（k）n ^ c $

的算法。

如果您的图表有一些特殊结构，则可以提高结果。