{"id":"arxiv:2610.19537","kind":"preprint","title":"Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage","authors":["Quanlong Niu","Riheng Jia"],"author_count":2,"year":2026,"published":"2026-10-14","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2610.19537","nct_id":null,"source_url":"https://arxiv.org/abs/2610.19537","archive_url":"https://space-kitty.com/papers/arxiv:2610.19537","updated":"2026-10-14","pmid":null,"pmcid":null,"openalex_id":"W7222098062","pdf_url":"https://arxiv.org/pdf/2610.19537","abstract":"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$ guarantee for a single station. A recurrence extends this bound to larger station limits, giving approximation factors that converge to $\\sqrt{5}-1$. Budget-threshold enumeration computes the restricted optimum in polynomial time for every fixed station limit. Under $k$-fold coverage, every edge must be covered by at least $k$ distinct stations, ensuring coverage after any $k-1$ station failures. We prove that selecting the $k$ vertices with the smallest full-coverage costs yields a $2$-approximation relative to the unrestricted optimum for $k$-fold coverage. When $k=2$, we combine upper bounds derived from the structure of the covering balls to improve the approximation guarantee to $5/3$.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}