固定kのための頂点カバー対クラークの時間の複雑さ

Question

私は、固定サイズ $ k $ の独立したセット問題を解決するための2つの方法があります $ g=（v、e）$ ：
- $ o ^ *（1.47 ^ {v - k}）$ （最適化された再帰的アルゴリズム）で実行されている頂点カバーアルゴリズム - $ o（{v \ chood}）$ （の単純な列挙サブセット> $ v $ とチェックアルゴリズム）

どのようにして時間の複雑さが少ないかを判断できますか？NP完全な問題のアルゴリズムと $ O ^ * $ 表記にはあまり慣れていません。これらの機能をプロットするのは十分ですか？ $のために、vcアルゴリズムは多項式 $ n ^ {o（1）} $ を持つことができると思います。o ^ * $ 表記とこれは実行時間に影響を与える可能性がありますが、わかりません。

Answer 1

任意の $ k $ 、 $ O（\ binom {v} {k}）= O（v^ k）$ は多項式ですが、 $ O ^ *（1.47 ^ {vk}）= o ^ *（1.47 ^ v）$ は指数関数です。指数関数は多項式よりはるかに速く成長します。

カーブのプロットはそれほど役立ちません。これらは漸近文であるためです。

は、> $ v $ と $ kに興味がある場合$ 、それからあなたの最良の選択肢は、どのアルゴリズムのどれがより速いかを経験的にチェックすることです。漸近的な表記は、定数の要因を隠しているので、ここでは役に立ちません。 $ v $ 、 $ k $ 。

Answer 2

頂点カバーは固定パラメータ扱い可能です。 サイズ $ k $ のVCを見つけるための単純な $ 2 ^ k n $ アルゴリズムがあります。 これはナイーブアルゴリズムを破るはずです。 現在の最先端の状態は、 $ 1.24 ^ k n $ のようなものです。

いくつかの仮定の下では、実行時間 $ f（k）n ^ c $ 。

あなたのグラフのいくつかの特別な構造がある場合、結果は改善されます。