PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Quanlong Niu, Riheng Jia

arXiv:2610.19537v1cs.DS

TL;DR

Em-VC asks how station budgets can cover graph edges, and how limiting the number of stations affects ordinary and fault-tolerant coverage. The paper analyzes station-limited solutions and k-fold coverage using threshold enumeration and bounds on expanded-graph balls. It proves a 5/4 bound for ordinary coverage with at most two stations, and 2 and 5/3 bounds for k-fold coverage generally and for k = 2, respectively.

  • Problem

    The paper asks how restricting the number of stations affects the cost of ordinary and fault-tolerant Em-VC compared with unrestricted coverage.

    Source: §1 · pp. 2–3

  • Method

    It derives finite-station bounds using candidate solutions and a recurrence, and analyzes k-fold coverage through expanded-graph balls and budget bounds.

    Source: §1 · pp. 2–3, §6.2 · p. 15, §7.4 · p. 18

  • Results

    At most two stations give an ordinary Em-VC cost at most 5/4 times unrestricted optimum; k-fold coverage has a 2-approximation, improved to 5/3 for k = 2.

    Source: §1 · p. 3, §8 · p. 20

  • Takeaways & Limitations

    Budget-threshold enumeration computes the optimal ordinary solution for every fixed station limit in polynomial time.

    Source: §1 · p. 3

    For twofold coverage, the worst-case approximation ratio for the optimal two-station algorithm is bounded within [4/3, 5/3].

    Source: §7.6 · p. 20

Abstract

from arXiv · show

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$.

1. Introduction

Emergency Vertex Cover models station budgets for reaching and fully traversing graph edges, with response cost determined by distance to the nearer endpoint plus edge length. This paper studies how limiting stations changes ordinary and fault-tolerant coverage guarantees.

1. Introduction

  • Emergency facility placement must account jointly for where stations are placed and the resources that determine their service ranges.In Em-VC, a station can cover an edge it is not incident to if its budget meets the response cost.Source: §1 · p. 2
  • Em-VC assigns budgets to stations at graph vertices so every edge is covered, charging the distance to its nearer endpoint plus the edge length.The total station budget is minimized.Source: §1 · p. 2
  • At most two stations give an ordinary Em-VC solution costing at most 5/4 times the unrestricted optimum, improving the single-station 4/3 guarantee.A recurrence extends the bounds to larger fixed station limits.Source: §1 · pp. 2–3
  • For every fixed station limit, budget-threshold enumeration computes an optimal restricted solution in polynomial time.The resulting algorithm has the approximation guarantee for that limit.Source: §1 · p. 3
  • For k-fold coverage, choosing the k vertices with the smallest full-coverage costs gives a 2-approximation, improved to 5/3 when k = 2.Every edge must be covered by k distinct stations, so coverage survives any k−1 station failures.Source: §1 · p. 3

2. Related work

Related work studies facility placement under coverage, resource-allocation, and backup requirements. This paper distinguishes Em-VC through edge traversal costs and compares finite-station solutions with an unrestricted optimum.

2. Related work

  • Set-covering and maximal-covering models address facility selection, while backup coverage studies first, second, and higher coverage multiplicities.Their service threshold is generally fixed, whereas Em-VC chooses response budgets as part of the solution.Source: §2 · p. 3
  • Power vertex cover allocates power but lets an edge be covered only by an endpoint; Em-VC allows a remote station to reach and traverse the edge.Power vertex cover also has parameterized-complexity and treewidth results, including an approximation scheme.Source: §2 · pp. 3–4
  • Broadcast domination uses shortest-path ranges to cover vertices, while Em-VC requires each edge to be reached and traversed in full from one station.Prior work gives exact algorithms for broadcast domination on connected unweighted graphs.Source: §2 · p. 4
  • Unlike minimum-sum-of-radii approximation results, the finite-station bounds compare a station-limited solution with an optimum having no station limit.The minimum sum of radii problem instead constrains both the solution and optimum to the same center limit.Source: §2 · p. 4
  • Metric multicover requires demand points to lie in balls around distinct facilities, paralleling the ball formulation of k-fold edge coverage in Em-VC.The comparison here is between exactly k stations, the minimum feasible number, and the unrestricted optimum for the same coverage requirement.Source: §2 · p. 4

3. Problem formulation

The formulation assigns budgets to vertices using response costs for edges, then defines ordinary and k-fold coverage and the station-limited objectives.

3.1. Response costs and ordinary coverage

  • A finite, connected, undirected simple graph with positive-length edges is assumed; stations occupy original vertices, at most one per vertex, and zero-budget vertices are inactive.Source: §3.1 · p. 5
  • For an edge e = {r, s}, station v's response cost is the distance to the nearer endpoint plus w(e).A station covers e exactly when its budget meets this cost.Source: §3.1 · p. 5
  • Ordinary Em-VC requires every edge to be covered by at least one station while minimizing the total budget.Source: §3.1 · p. 5
  • A_ℓ denotes the optimum with at most ℓ positive-budget stations, against unrestricted optimum OPT.Each vertex's budget can be reduced to a response threshold without changing its covered edges; the threshold set has at most m + 1 values, yielding an optimal threshold-budget solution.Source: §3.1 · p. 5

3.2. Multiple coverage and solutions with the minimum number of stations

  • k-Robust Em-VC requires every edge to have k distinct covering stations, equivalently remaining covered after any at most k−1 station failures.OPT_k denotes its unrestricted optimum, with OPT_1 = OPT.Source: §3.2 · p. 6
  • With exactly k stations providing k-fold coverage, each must cover every edge, so the optimal set is the k vertices with the smallest full-coverage costs.Source: §3.2 · p. 6
  • A_2 is the ordinary optimum using at most two stations, whereas U_2 is the twofold-coverage optimum using exactly two stations.For one station, U_1 = A_1.Source: §3.2 · p. 6

4. The expanded metric graph and basic properties

The paper converts edge coverage into ball coverage on an expanded metric graph, then uses path-length, ball-merging, and center-rounding bounds to analyze solutions.

4. The expanded metric graph and basic properties

  • The expanded-graph analysis establishes path-length, ball-merging, and center-rounding bounds using a geometric approach.Source: §4 · p. 6

4.1. From edge coverage to ball coverage

  • The expanded graph replaces each original edge with a subdivided core path and a pendant edge; a station's distance to the edge's leaf equals its response cost.A ball centered at an original vertex covers the edge gadget when it reaches the leaf, making k-fold edge coverage equivalent to k-fold coverage of the expanded graph.Source: §4.1 · pp. 6–7

4.2. Coverage length along shortest paths

  • A ball of radius p covers at most 2p length along any shortest path, or at most p when that path starts at its center.Source: §4.2 · p. 7
  • If station balls cover the expanded graph with total budget S, its diameter is at most 2S.Source: §4.2 · p. 8

4.3. Merging intersecting balls and continuous centers

  • Intersecting balls of radii r and s, whose centers are distance d apart, fit inside a ball of radius at most (r + s + d)/2.Because the expanded graph is connected, repeatedly merging intersecting balls can produce one ball covering the space.Source: §4.3 · pp. 8–9
  • The minimum continuous-center radius is attained, and no continuous center lies in a pendant-edge interior or at its leaf.Source: §4.3 · pp. 8–9
  • Rounding a continuous center on an edge of length w yields A_1 ≤ C + w/2 and U_2 ≤ 2C + w.Choosing the endpoint with smaller full-coverage cost gives the first bound; giving each endpoint enough budget to cover the graph gives the second.Source: §4.3 · p. 9

5. Approximation for ordinary coverage with few stations

For ordinary Em-VC, restricting coverage to at most two stations costs at most 5/4 of the unrestricted optimum, and a recurrence extends the guarantee to larger fixed station limits. The section also gives exact polynomial-time algorithms for the restricted problems when the station limit is fixed.

5.1. Two upper bounds on the single-station cost

  • The single-station cost satisfies A_1 ≤ 4/3 OPT, recovered by combining two upper bounds on that cost.Weighting the bounds by 2 and 1 yields 3A_1 ≤ 4S.Source: §5.1 · p. 10

5.2. Exclusive edges and residual components

  • Removing the largest-budget station’s exclusive edges leaves components locally covered by the other stations; raising its budget to P+2R_j lets it absorb any component.The residual components are formed after deleting the edges covered exclusively by that station.Source: §5.2 · pp. 10–11

5.3. A recurrence for the approximation guarantee

  • The recurrence compares a single-station solution, absorption of all residual components, and recursive coverage of one component while assigning the others to the largest-budget station.The induction combines these candidate bounds to establish the guarantee for each station limit.Source: §5.3 · pp. 11–12
  • 5/4 OPT bounds the at-most-two-station optimum; the recurrence α_l=1+α_(l−1)/(4+α_(l−1)) starts at α_1=4/3 and decreases to ρ.The recurrence relates guarantees for successive station limits.Source: §5.3 · pp. 11–12

5.4. An exact two-station algorithm and its complexity

  • Threshold enumeration computes A_l exactly in polynomial time for fixed l, while the at-most-two algorithm runs in O(nm log m+n^2m) after shortest-path preprocessing.For connected graphs, the stated total time including Floyd–Warshall is O(n^3+nm log m+n^2m).Source: §5.4 · pp. 13–14

6. Approximation for multiple coverage with the minimum number of stations

The section considers fault-tolerant coverage requiring every edge to be covered by k distinct stations. It selects stations by full-coverage cost and proves a 2-approximation relative to the unrestricted k-fold optimum.

6.1. Selecting full-coverage stations

  • Sorting full-coverage costs gives an optimal fault-tolerant solution using exactly k stations.Each selected station covers every edge independently.Source: §6.1 · p. 14

6.2. The approximation guarantee for general multiplicity

  • The k cheapest full-coverage stations give a 2-approximation for k-fold coverage relative to the unrestricted optimum.The proof bounds their total full-coverage cost using any feasible k-fold solution.Source: §6.2 · p. 15

7. An improved approximation guarantee for twofold coverage

For twofold coverage, the paper improves Algorithm 2’s approximation guarantee to 5/3 by combining structural upper bounds. A triangle instance gives a 4/3 lower bound for the best two-station solution, leaving its worst-case ratio between 4/3 and 5/3.

7.1. The ball intersection graph and an independent-set bound

  • The ball intersection graph is connected, and an independent set of weight I has pairwise disjoint balls whose deletion leaves budget S − I.This independent-set bound contributes to the upper bounds combined for the 5/3 guarantee.Source: §7.1 · pp. 15–16

7.2. Budget estimates along induced paths

  • Along shortest paths in the weighted intersection graph, induced-path structure bounds each station’s full-coverage cost by 4I − p_u.Choosing the two largest-budget stations gives U2 ≤ 8I − h1 − h2.Source: §7.2 · p. 16

7.3. Savings from merging along the central edge

  • Two stations covering the central edge have center distance at most A + B − w, so their balls merge into one of radius at most A + B − w/2.The merged-radius saving is used in deriving a further upper bound.Source: §7.3 · p. 17

7.4. The third upper bound

  • When the third-largest budget exceeds the central-edge length, the two largest-budget stations must cover that edge.This case distinction supplies the third upper bound used in the final combination.Source: §7.4 · pp. 18–19

7.5. Combining the three bounds

  • For k = 2, Algorithm 2 achieves a 5/3 approximation guarantee by combining three upper bounds.The bounds are weighted 4:1:1 to cancel I, w, and t, yielding 6U2 ≤ 10S.Source: §7.5 · pp. 19–20

7.6. A lower-bound instance for two-station solutions

  • A unit-edge triangle has twofold-cover optimum 3, while every two-station solution costs at least 4.Thus, the best two-station algorithm’s worst-case ratio lies in [4/3, 5/3].Source: §7.6 · p. 20

8. Conclusion and future directions

The conclusion summarizes the guarantees for ordinary and k-fold Em-VC and identifies open questions about their tightness.

8. Conclusion and future directions

  • Allowing two stations improves the ordinary Em-VC guarantee from 4/3 to 5/4, with further recurrence bounds for each fixed station limit.Whether the finite-station recurrence bounds are tight remains open.Source: §8 · p. 20
  • For k-fold coverage, using exactly k stations gives a 2-approximation, improved to 5/3 when k = 2.The gap between the 4/3 lower bound and 5/3 upper bound for the best two-station twofold solution remains open.Source: §8 · p. 20
  • The paper leaves open whether the finite-station recurrence bounds are tight.It also leaves open closing the twofold two-station ratio gap between 4/3 and 5/3.Source: §8 · p. 20

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

The authors report using an AI assistant during manuscript preparation and state that they reviewed and edited the content and assume responsibility for it.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

Loading 2610.19537v1…