Full Neighbourhood Knowledge Helps Online Vertex Cover More Than Online Dominating Set

Abstract

We study the online vertex cover under the Connected Reveal with Neighbourhood (CRN) model, where each revealed vertex exposes all incident edges and must form a connected induced subgraph with previous revealed vertices. Focusing on trees, cactus graphs, outerplanar graphs, graphs with bounded degree, and threshold graphs, we adapted the k-Dominate and charging arguments from prior work on the online dominating set problem in [9] to fit the vertex cover context. We analyse three algorithms: 2-Cover, ⌈√∆⌉-Cover, and UNS, and show that 2-Cover achieves competitive ratios of 3/2 on trees, 5/3 on cactus graphs, and at most 5/2 on outerplanar graphs. In comparison, dominating set is known to be 2-competitive on trees, and 5/2 -competitive on cactus graphs in [9]. For cactus graphs, we introduce asymmetric charging rules, in contrast to the symmetric approach for dominating set, where the charging arguments for trees and cactus graphs are identical. For graphs with bounded degree ∆, we achieve an O(√∆)-competitive ratio, which matches the bound for dominating set in [9]. Finally, we show that threshold graphs admit a constant competitive ratio for vertex cover, whereas no such guarantee exists for dominating set, as shown in [9]. This sets vertex cover and dominating set fundamentally apart in the online setting.