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

Preprint · Quanlong Niu, Riheng Jia

- Archive id: arxiv:2610.19537
- Published: 2026-10-14
- arXiv: https://arxiv.org/abs/2610.19537
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.19537
- PDF: https://arxiv.org/pdf/2610.19537
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.