Sándor Kisfaludi-Bak

Sándor Kisfaludi-Bak, Dániel Marx

We give approximation schemes for Subset TSP and Steiner Tree on unit disk graphs, and more generally, on intersection graphs of similarly sized connected fat (not necessarily convex) polygons in the plane. As a first step towards this goal, we prove spanner-type results: finding an induced subgraph of bounded size that is $(1+\varepsilon)$-equivalent to the original instance in the sense that the optimum value increases only by a factor of at most $(1+\varepsilon)$ when the solution can use only the edges in this subgraph. - For Subset TSP, our algorithms find a $(1+\varepsilon)$-equivalent induced subgraph of size $\mathrm{poly}(1/\varepsilon)\cdot\mathrm{OPT}$ in polynomial time, and use it to find a $(1+\varepsilon)$-approximate solution in time $2^{\mathrm{poly}(1/\varepsilon)}\cdot n^{O(1)}$. - For Steiner Tree, our algorithms find a $(1+\varepsilon)$-equivalent induced subgraph of size $2^{\mathrm{poly}(1/\varepsilon)}\cdot\mathrm{OPT}$ in time $2^{\mathrm{poly}(1/\varepsilon)}\cdot n^{O(1)}$, and use it to find a $(1+\varepsilon)$-approximate solution in time $2^{2^{\mathrm{poly}(1/\varepsilon)}}\cdot n^{O(1)}$. - An improved algorithm finds a $(1+\varepsilon)$-approximate solution for Steiner Tree in time $2^{\mathrm{poly}(1/\varepsilon)}\cdot n^{O(1)}$. An easy reduction shows that approximation schemes for unit disks imply approximation schemes for planar graphs. Thus our results are far-reaching generalizations of analogous results of Klein [STOC'06] and Borradaile, Klein, and Mathieu [ACM TALG'09] for Subset TSP and Steiner Tree in planar graphs. We show that our results are best possible in the sense that dropping any of (i) similarly sized, (ii) connected, or (iii) fat makes both problems APX-hard.

Timothy M. Chan, Hsien-Chih Chang, Jie Gao et al.

Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [SoCG '22] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter $Δ$ is at least $Ω(\log n)$, hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include: - A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. - A truly subquadratic time lower bound for \Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be truly subquadratic hard when the diameter is $Ω(\log n)$. - A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D. - A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.