Learning-Augmented Algorithms for Online Vertex Cover
2026-06-22 • Computational Complexity
Computational ComplexityMachine Learning
AI summaryⓘ
The authors studied a problem where a computer needs to choose a set of important points (vertices) in a graph to cover all connections, but it has to decide step-by-step without changing previous choices. They focus on two types of graphs: bipartite and general. Their algorithms balance two goals: being reliable even with bad advice (robustness) and doing well when given good advice (consistency). They found the best possible tradeoffs between these goals and confirmed their results with tests on fake and real data.
online algorithmsvertex coverbipartite graphsdeterministic algorithmrandomized algorithmrobustnessconsistencylearning-augmented algorithmsski rental problem
Authors
Tianhang Lu, Runtian Ren, Shengcai Liu
Abstract
This paper studies learning-augmented online weighted vertex cover with advice and a parameter $λ\in (0,1)$. We consider two graph cases: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same robustness--consistency tradeoffs as learning-augmented ski rental. For the bipartite graph model, we give a randomized algorithm that is $\frac{1}{1-e^{-λ}}$-robust and $\fracλ{1-e^{-λ}}$-consistent. For the general graph model, we give a deterministic algorithm that is $(1+\frac{1}λ)$-robust and $(1+λ)$-consistent. We prove that the tradeoffs above are optimal in both settings. We also validate the proposed algorithms through experiments on synthetic and real-world datasets.