頂点被覆
H. Freeman , p. 134, cites Gavril.
↑ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
↑ I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").
↑ Khot, S.; Regev, O. (2008), “Vertex cover might be hard to approximate to within 2-ε”, J. Comput. Syst. Sci. 74 (3): 335–349, doi:10.1016/j.jcss.2007.06.019 .
ヒッティングセット問題においては、パラメータ化は異なる意味を持つ。ヒッティングセット問題はパラメータ O P T {\displaystyle OPT} について W [ 2 ] {\displaystyle W[2]} -完全であり、 f ( O P T ) n O ( 1 ) {\displaystyle f(OPT)n^{O(1)}} という時間内で動作するアルゴリズムは存在しないと思われる。ここで O P T {\displaystyle OPT} は最小ヒッティングセットの濃度である。ヒッティングセット問題はパラメータ O P T + d {\displaystyle OPT+d} について固定パラメータ容易性を持つ。ここで d {\displaystyle d} はそのハイパーグラフの最大ハイパーエッジの大きさ | e | {\displaystyle |e|} である。より正確には、ヒッティングセット問題には d O P T n O ( 1 ) {\displaystyle d^{OPT}n^{O(1)}} という時間内で動作するアルゴリズムが存在する。
力まかせ探索アルゴリズムを使えば、2n の時間で問題を解くことができる。したがって頂点被覆は固定パラメータ容易性があり、小さい k のみに着目する場合は多項式時間で問題を解くことができる。このときのアルゴリズム的技法として bounded search tree algorithm があり、頂点の選択を繰り返し、現在の頂点を頂点被覆に含めるか、隣接する全頂点を頂点被覆に含めるかを再帰的に選択していくものである。計算複雑性理論における exponential time hypothesis という仮説によれば、この方式の実行時間は 2n より改善されることはない。
平面グラフでは、大きさ k の頂点被覆は 2 O ( k ) n O ( 1 ) {\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}} という時間で求めることができ、準指数固定パラメータ容易性がある。exponential time hypothesis によれば、平面グラフの頂点被覆問題について 2 o ( k ) n O ( 1 ) {\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}} という時間未満で解けるアルゴリズムは存在しない。