2026/07/30 by Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
Computer Science · #cs.CG #cs.CC #cs.DM #cs.DS
35 pages
arxiv created 2026/07/30 · arxiv updated 2026/07/31
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 xi and hits each consecutive trace T with probability min\1,x(T)\. We obtain three tight UGC thresholds. First, for every fixed d≥ 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≥ 2, closing under UGC the gap left by the d-approximation of Ben-David, Grant, Ma, and Sharpe [CCCG 2012].