A New Lower Bound for Online Vertex Cover under Vertex Arrivals
2026-08-10 • Data Structures and Algorithms
Data Structures and AlgorithmsComputer Science and Game Theory
AI summaryⓘ
The authors show that no random online algorithm for the vertex cover problem can do better than about 1.82 times the optimal solution in the worst case, even for simple bipartite graphs. They improve the known lower bound from about 1.75 to 1.82 by extending previous constructions to more complex scenarios. Their proof involves analyzing a mathematical recurrence relation describing the adversary's moves and shows that any algorithm attempting to beat this ratio would fail. They also provide an example demonstrating that this bound is exact within their framework.
online algorithmsvertex covercompetitive ratiorandomized algorithmsbipartite graphsoblivious adversaryrecurrence relationfixed pointintegral and fractional algorithms
Authors
Tianhang Lu
Abstract
We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an integrable fixed point; classifying all such fixed points forces the excess ratio to be at least $\sqrt{e}/2$. A truncated discrete recurrence and a Riemann-sum argument convert every strict continuous violation into a finite, algorithm-dependent but realization-oblivious input. We also exhibit a critical fixed point showing that $1+\sqrt{e}/2$ is the exact limit of this homogeneous complete-bipartite recurrence, rather than a numerical artifact.