Improved upper bounds for vertex cover

This paper presents an O(1.2738k+kn)-time polynomial-space algorithm for Vertex Cover improving the previous O(1.286k+kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. Most of the previous algorithms rely on exhaustive case-by-case branching rules, and an underlying conservative worst-case-scenario assumption. The contribution of the paper lies in the simplicity, uniformity, and obliviousness of the algorithm presented. Several new techniques, as well as generalizations of previous techniques, are introduced including: general folding, struction, tuples, and local amortized analysis. The algorithm also improves the O(1.2745kk4+kn)-time exponential-space upper bound for the problem by Chandran and Grandoni.