Tight UGC Thresholds for Geometric Stabbing Problems

Abstract

Many geometric stabbing problems admit natural covering LPs in which each constraint is a union of consecutive traces on ordered candidate sets. We prove a transfer theorem showing that every fixed finite, bounded-arity integrality-gap instance of this form yields a matching hardness ratio under the Unique Games Conjecture. Using the strict-CSP framework of Kumar, Manokaran, Tulsiani, and Vishnoi [SODA 2011], we construct the required connected local distributions by randomized rounding and a full-support perturbation. Given a fractional vector $x$ on a block, the rounding selects candidate $i$ with marginal probability $x_i$ and hits each consecutive trace $T$ with probability $\min \{1,x(T)\}$. We obtain three tight UGC thresholds. First, for every fixed $d\ge 2$, stabbing arbitrary-size axis-parallel $d$-cubes with coordinate hyperplanes has threshold $d$. For $d=2$, the hardness holds for arbitrary-size squares and establishes threshold $2$ for rectangle and square stabbing, matching the $2$-approximation of Gaur, Ibaraki, and Krishnamurti [ESA 2000]. Second, stabbing horizontal segments with horizontal and vertical lines has threshold $e/(e-1)$, matching the $e/(e-1)$-approximation of Kovaleva and Spieksma [ESA 2004]. Third, separated $d$-interval transversal has threshold $d$ for every fixed $d\ge 2$, closing under UGC the gap left by the $d$-approximation of Ben-David, Grant, Ma, and Sharpe [CCCG 2012].

35 pages

Topics & keywords