| Abstract: |
This paper presents an O(1.2740k + kn)-time
polynomial-space algorithm for Vertex
Cover improving both the previous O(1.286k + kn)-time
polynomial-space algorithm by Chen, Kanj, and Jia, and the very recent O(1.2745k
+ k4n+ kn)-time exponential-space algorithm, by
Chandran and Grandoni. Most of the previous algorithms rely on exhaustive
case-by-case analysis, and an underlying conservative worst-case-scenario
assumption. The contribution of the paper lies in the extreme 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 induces improvement on the upper
bound for the Independent Set
problem on graphs of degree bounded by 6. |