Optimal Non-Adaptive Vantage Point Selection

1 Introduction

• Vantage point selection models revealing bottleneck edges by querying graph vertices, with performance measured against an optimum that knows edge capacities.The paper focuses on non-adaptive algorithms, whose future queries cannot depend on earlier query results.Source: §1 · p. 2
• Network tomography uses probing to infer bottleneck capacities, but issuing probes requires access to the system at each vantage point.The paper relates a path's maximum data rate to its minimum-capacity edge.Source: §1 · p. 2

Prior Work

• Prior general-graph bounds left a gap between the trivial O(n) upper bound and a randomized lower bound of Ω~(√n).The lower-bound construction uses disjoint paths with one randomly selected path whose capacities decrease along it.Source: Prior Work · p. 3

Question: Can we get any non-trivial (sublinear competitive ratio) single-query algorithm

• For multi-query selection, prior general-graph upper bounds were unavailable beyond the trivial regime, while tree and planar graph guarantees were known.The trivial regime gives the algorithm n queries when α = n/k.Source: Question: Can we get any non-trivial… · p. 4

1.1 Our Results

• The paper provides the first non-trivial algorithms for general graphs, with a randomized non-adaptive algorithm matching lower bounds up to polylogarithmic factors.Its stated running time is O~(n(n + m)), with no additional overhead beyond all-pairs shortest paths up to polylogarithmic factors.Source: §1.1 · pp. 4–5
• The single-query optimum is Θ~(n^2/3); for general non-adaptive queries, the paper establishes a parameter-dependent bound tight up to polylogarithmic factors.The general result applies when αk ≤ n.Source: §1.1 · p. 5
• Figure 1 shows the single-query case alongside prior bounds and plots the tight multi-query ratio over α and k.The single-query plot marks n^2/3 at the y-intercept and the ratio 1 when the algorithm gets n queries.Source: Figure 1 · p. 6
• Whether the lower bounds extend to adaptive algorithms, or an adaptive algorithm can surpass them, remains open.The paper's guarantees concern the non-adaptive setting.Source: §1.1 · p. 6

2.1 Algorithm

• In the single-query (α = k = 1) setting, the overview reports competitive ratio ˜O(n2/3) for general graphs, versus ˜O(n6/7) for graphs with hop-diameter ˜O(1).Source: §2.1 · p. 6
• For low-hop-diameter graphs, the simpler algorithm samples among high-betweenness vertices, high-residual-degree vertices, and all vertices, each with probability 1/3.Its analysis uses the fact that if the optimum vertex has residual degree at most n^6/7, querying a vertex from S can reveal edges on paths hit by S; if many residual pairs remain, uniform sampling can yield ˜Ω(n^1/7) revealed edges in expectation.Source: §2.1 · pp. 7–8
• The framework builds a vertex set S toward either lowering the optimum vertex's residual degree or making all edges have low betweenness on the residual pairs.Because these quantities change together as S grows, the algorithm replaces fixed thresholds with interdependent, iteratively adjusted parameters and nested procedures.Source: §2.1 · p. 8

2.2 Lower Bound

• The lower-bound overview presents two simpler constructions whose ideas combine in the full construction: one for large α and k, and one for α = k = 1.The full construction's details are deferred to Section 5.Source: §2.2 · pp. 9–10

2.2.1 Case 1: Large-parameter regime

• In the large-parameter regime, symmetric butterfly graphs hide optimal vantage points among candidates while their expanding shortest-path trees let those points reveal many edges.Filler edges and shortcuts make the optimal queries' revealed edges nearly disjoint while causing non-optimal queries' revealed edges to overlap heavily; tuning the construction reaches the optimal competitive ratio when α^3k^2 ≥ n.Source: §2.2.1 · pp. 10–11

2.2.2 Case 2: α = k = 1

• The construction hides the optimal vantage point among ˜Ω(n^(2/3)) candidates, while an optimal-vantage query reveals nearly linearly many edges and a capacity-unaware query reveals only ˜O(n^(1/3)) edges.The butterfly is replaced with a two-phase expansion.Source: §2.2.2 · pp. 11–12
• A filler layer beyond the y-layer lets the hidden optimal candidate reveal nearly linearly many distinct edges despite the shortcut and two-phase-expansion structure.The construction also sets x-x′ capacities below other layer-to-layer edges on candidate-to-y paths to bound their contribution.Source: §2.2.2 · p. 12

3 Preliminaries

• Each reachable pair has a unique shortest path, and distinct edge capacities ensure that path has a unique minimum-capacity, or bottleneck, edge.The graph is undirected, and disconnected pairs are excluded from the reachable-pair set.Source: §3 · pp. 12–13
• A query selects a vertex and reveals the bottleneck edge on its shortest path to every other vertex in the same connected component.The algorithm seeks to reveal many edges by choosing a small number of vantage points.Source: §3 · p. 13
• The benchmark OPT_k is the maximum number of edges revealed by k vantage points chosen with full knowledge of the hidden capacities.For an algorithm using αk queries, the revealed-edge count is treated as a random variable when the algorithm is randomized, with guarantees understood in expectation unless stated otherwise.Source: §3 · pp. 13–14
• A non-adaptive algorithm chooses all vantage points before seeing capacity information or revealed bottleneck edges.Its output distribution may depend on the graph and shortest-path structure, but not on the hidden capacity assignment.Source: §3 · p. 14

4 Upper Bound

• For αk ≤ n, a randomized non-adaptive algorithm runs in ˜O(n(n + m)) time and achieves the competitive ratio stated in Theorem 3.The supplied theorem passage does not include the ratio expression.Source: §4 · p. 14

4.1.1 Finding Vertices of High Residual Betweenness Centrality

• High-Residual-BC greedily adds vertices with greatest betweenness among paths avoiding the current S, stopping after at most I additions.It returns the maximum residual edge betweenness centrality after those additions, with the goal of bounding it by |P|/I.Source: §4.1.1 · p. 16

4.1.2 Querying Subroutine for Low Betweenness Centrality Regime

• RevealWithRestrictedBC queries a uniformly sampled vertex from T with probability 1/2 and a uniformly sampled vertex from V otherwise.For residual pairs with first endpoint in T and bounded edge betweenness, its analysis gives an expected revealed-edge lower bound.Source: §4.1.2 · pp. 16–17

4.1.3 Reducing the Maximum Residual Degree or Revealing Many Edges

• ReduceOrReveal tracks high-residual-degree vertices and their residual pairs, repeatedly applying the greedy betweenness routine to their paths.It either lowers all residual degrees below d or reaches a stage with many residual pairs and sufficiently low maximum edge betweenness for the querying subroutine; the returned S has size O(I log n).Source: §4.1.3 · pp. 17–18

4.1.4 Iterative Residual Degree Reduction

• IterativeReduce runs ReduceOrReveal over geometrically decreasing residual-degree thresholds, choosing each next threshold to balance reduction against the revealing guarantee.If a threshold is met, it updates the degree upper bound and continues; otherwise, it terminates after the procedure reveals many edges.Source: §4.1.4 · p. 19

4.1.5 The Final Algorithm"

• The final algorithm combines three cases: edges already revealed through S, the residual guarantee from Lemma 4.4, or sufficiency of uniform sampling from V.It chooses a case at random and samples αk vantage points using the corresponding strategy.Source: §4.1.5 · pp. 20–21

4.2.1 Proof of Lemma 4.1

• High-Residual-BC grows S iteratively while tracking residual pairs, which disappear when a selected vertex lies on their shortest paths.The pair sets Pi are nested, and adding vi removes pairs in Pi−1 whose shortest paths contain vi.Source: §4.2.1 · p. 22

4.2.2 Proof of Lemma 4.2

• A query can reveal an edge by sampling from either endpoint set Ae or Be; the analysis reapplies this one-query argument to residual pairs across αk queries.The proof tracks edges revealed so far and removes pairs whose bottleneck edges have already been revealed.Source: §4.2.2 · p. 24

4.2.3 Proof of Lemma 4.3

• ReduceOrReveal adds O(I log n) vertices and iterates only O(log n) times because each non-returning iteration halves |T| or |Q|.Its two possible conclusions are stated in Lemma 4.3, though their details are not present in the supplied passage.Source: §4.2.3 · pp. 25–26

4.2.4 Proof of Lemma 4.4

• IterativeReduce adds O(I log^2 n) vertices while decreasing its residual-degree bound geometrically until it falls below 1.Because residual degrees are integers, a bound below 1 means all residual degrees are zero.Source: §4.2.4 · pp. 26, 28

4.2.5 Final Analysis

• The final analysis combines estimates from three algorithm branches and uses Fhit ∪ Fres = F⋆ with |F⋆| = OPTk to express the competitive ratio.The branches cover edges already revealed by selected vertices, residual edges revealed by returned vantage points, and edges addressed by sampling from V.Source: §4.2.5 · pp. 30–31

• The implementation runs in tilde-O(n(n + m)) time, with shortest-path-tree computation as the bottleneck.The post-preprocessing work is tilde-O(n^2).Source: §4.3 · pp. 31, 33
• Euler-tour intervals identify and delete targets whose paths pass through a selected vertex in O((|D| + n) log n) time.The n interval queries are made even when an interval contains no target.Source: §4.3 · p. 32
• After shortest-path preprocessing, the remaining work takes tilde-O(n^2) time, including O(log^2 n) calls to Algorithm 1.The total accounts for the calls to Algorithms 1, 3, and 4.Source: §4.3 · pp. 32–33

5 Lower Bound

• For positive integers α and k with αk ≤ n, Theorem 4 asserts a worst-case n-vertex instance for every randomized non-adaptive algorithm.The theorem’s competitive-ratio expression is not present in the supplied passage.Source: §5 · p. 33

5.1 Construction

• The construction uses k parts with butterfly copies, filler vertices, and part-specific upper and shared lower shortcuts to hide optimal query vertices.Capacity choices are randomized independently across parts, and weight perturbations ensure unique shortest paths.Source: §5.1 · pp. 33, 37
• The construction can be padded to exactly n vertices with isolated vertices without affecting the competitive-ratio lower bound.The graph before padding has at most n vertices.Source: §5.1 · p. 38

5.2 Analysis

• For a fixed query vertex, the expected captured edges are O(τ) in Elarge and ˜O(τ + P) in Emid.Elarge comprises x-y and filler edges; Esmall is counted globally in the multi-query analysis.Source: §5.2 · pp. 38–39
• For every fixed query vertex u, the expected revealed edges satisfy Eσ[|R(u) ∩ Elarge|] = O(τ) and Eσ[|R(u) ∩ Emid|] = ˜O(τ + P).The case analysis bounds bottlenecks across endpoint types, with paths through lower shortcuts often placing bottlenecks in Esmall.Source: §5.2 · pp. 39, 41, 42, 43
• Because a randomized non-adaptive query set is independent of σ, decomposing it into fixed query sets lets the fixed-set upper bound apply by averaging.The averaging yields a fixed capacity assignment σ⋆ for the subsequent comparison.Source: §5.2 · p. 43
• k queries, one per part, reveal edge-disjoint sets of PQτ filler edges, and PQτ = ˜Θ(n), establishing the lower-bound construction in Theorem 2.The filler edges are disjoint across parts because their y-layer endpoints carry different part indices.Source: §5.2 · p. 44