Vertex cover approximations improve with one-time offline advice
Vertex Cover Problem with Advice
Data Structures and Algorithms
Summary
The vertex cover problem asks how to pick the fewest nodes in a network so every connection touches one chosen node. This paper studies how having some one-time predictions about the best solution – either exact or noisy info on some nodes – can help find better solutions. The authors developed algorithms that use these predictions to get closer to an ideal answer, improving beyond known limits when no predictions are used. Their results show that even imperfect advice can lead to more accurate solutions efficiently.
What this means in practice
- •For network engineers: Improve automated network monitoring systems by using partial predicted info to identify crucial nodes more accurately.
- •For security analysts: Enhance threat detection by applying improved approximation algorithms with noisy predictions on access control graphs.
A theory result. No direct application yet.
Authors
Lucas de Oliveira Silva, Lehilton Lelis Chaves Pedrosa
Abstract
We study the minimum Vertex Cover problem under two non-adaptive offline advice models, where predictions about a fixed optimum solution are provided once as part of the input. These forms of prediction were introduced independently by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (2024) and by Ghoshal, Makarychev, and Makarychev (2025). In Partial Predictions, independently revealed vertices come with correct membership labels. For every sufficiently small fixed $\varepsilon>0$, we give a randomized polynomial-time algorithm that has expected approximation ratio at most $2-(2-o(1))\frac{\log\log(1/\varepsilon)}{\log(1/\varepsilon)}$. In Noisy Predictions, every vertex instead receives a mutually independent noisy membership label of bias $\varepsilon$. For every sufficiently small fixed $\varepsilon>0$, we give a randomized polynomial-time algorithm that has expected approximation ratio at most $2-(1-o(1))\frac{\log\log(1/\varepsilon)}{\log(1/\varepsilon)}$. Our Noisy Predictions bound matches the leading asymptotic improvement below $2$ obtained by Aamand, Chen, Gollapudi, Silwal, and Wu (2025), despite using only one noisy label per vertex rather than a separate independent label for each endpoint of each incident edge. Both our bounds hold as $\varepsilon$ goes to $0$ and are strictly below $2$, the optimal approximation threshold for minimum Vertex Cover without advice under the Unique Games Conjecture, as shown by Khot and Regev (2008).