Emergency vertex cover helps plan city disaster response coverage
Emergency Vertex Cover
Data Structures and Algorithms
Summary
Covering all roads for emergency access is important but challenging. The authors expand on a known math problem by allowing coverage not just from nearby points but also from farther away if enough 'power' is assigned to the covering point. They show this new problem is hard to solve but provide both exact and approximate ways to tackle it. Their work helps in scenarios like disaster response where it’s crucial to ensure all roads are accessible.
What this means in practice
- •For disaster response teams: Design emergency resource placements to ensure all road segments remain accessible in urban disaster scenarios.
- •For urban planners: Plan infrastructure coverage with flexibility to assign resources efficiently beyond immediate intersections.
A theory result. No direct application yet.
Authors
Eric Angel, Evangelos Bampas, Evripidis Bampis, Vincent Chau, Johanne Cohen, Alexander Kononov, Yizheng Zhang
Abstract
The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is incident to at least one vertex in this subset. Among its variants, the Min-Power-Cover problem stands out due to its practical applications, such as camera placement at intersections: in an edge-weighted graph, an edge is covered if one of its endpoints is assigned a power value at least as large as the edge's weight. In this paper, we introduce the Emergency Vertex Cover (Em-VC) problem where an edge may be covered not only by its endpoints, but also by a distant vertex, provided the vertex is given sufficient power to "cover" the cumulative weight of the edges along a shortest path to one of the edge's endpoints plus the weight of the edge. Em-VC is motivated by different practical scenarios, e.g. the need for urban disaster response, where ensuring accessibility to all road segments (edges of the graph) is crucial for effective aid delivery. We prove that Em-VC is NP-hard, derive lower bounds, and design a polynomial-time algorithm for its continuous version. Moreover, we present a 4/3-approximation algorithm for the discrete case and identify several special graph classes for which the problem can be solved in polynomial time.