Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage

Q Niu, R Jia - arXiv preprint arXiv:2610.19537, 2026 - arxiv.org
Q Niu, R Jia
arXiv preprint arXiv:2610.19537, 2026•arxiv.org
The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph
vertices to cover every edge while minimizing the total budget. The cost of covering an edge
from a station is the shortest-path distance from the station to the nearer endpoint plus the
edge length. We study how restricting the number of stations affects the cost of ordinary and
fault-tolerant coverage. In ordinary Em-VC, we prove that the optimal solution using at most
two stations costs at most $5/4$ times the unrestricted optimum, improving the known $4/3 …
The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph vertices to cover every edge while minimizing the total budget. The cost of covering an edge from a station is the shortest-path distance from the station to the nearer endpoint plus the edge length. We study how restricting the number of stations affects the cost of ordinary and fault-tolerant coverage. In ordinary Em-VC, we prove that the optimal solution using at most two stations costs at most times the unrestricted optimum, improving the known guarantee for a single station. A recurrence extends this bound to larger station limits, giving approximation factors that converge to . Budget-threshold enumeration computes the restricted optimum in polynomial time for every fixed station limit. Under -fold coverage, every edge must be covered by at least distinct stations, ensuring coverage after any station failures. We prove that selecting the vertices with the smallest full-coverage costs yields a -approximation relative to the unrestricted optimum for -fold coverage. When , we combine upper bounds derived from the structure of the covering balls to improve the approximation guarantee to .
arxiv.org