information:filtering, linguistic:voice_change, information:highlighting
Fixed-parameter tractability

An exhaustive search algorithm can solve the problem in time 2 n, where k is the size of the vertex cover. Vertex cover is therefore fixed-parameter tractable, and if we are only interested in small k, we can solve the problem in polynomial time. One algorithmic technique that works here is called bounded search tree algorithm, and its idea is to repeatedly choose some vertex and recursively branch, with two cases at each step: place either the current vertex or all its neighbours into the vertex cover.The algorithm for solving vertex cover that achieves the best asymptotic dependence on the parameter runs in time O (1.2738 k + (k ⋅ n)) {\displaystyle O(1.2738^{k}+(k\cdot n))}. The klam value of this time bound (an estimate for the largest parameter value that could be solved in a reasonable amount of time) is approximately 190. That is, unless additional algorithmic improvements can be found, this algorithm is suitable only for instances whose vertex cover number is 190 or less. Under reasonable complexity-theoretic assumptions, namely the exponential time hypothesis, the running time cannot be improved to 2, even when n {\displaystyle n} is O (k) {\displaystyle O(k)}.

However, for planar graphs, and more generally, for graphs excluding some fixed graph as a minor, a vertex cover of size k can be found in time 2 O (k) n O (1) {\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}, i.e., the problem is subexponential fixed-parameter tractable. This algorithm is again optimal, in the sense that, under the exponential time hypothesis, no algorithm can solve vertex cover on planar graphs in time 2 o (k) n O (1) {\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}.