A faster algorithm for Vertex Cover parameterized by solution size

David G. Harris, N. S. Narayanaswamy

We describe a new algorithm for vertex cover with runtime $O^{\ast }(1.25284^k)$, where $k$ is the size of the desired solution and $O^{\ast }$ hides polynomial factors in the input size. This…