On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
Sujoy Bhore, Barış Can Esmer, Dániel Marx, Karol Węgrzycki · 2025
Read On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects by Sujoy Bhore, Barış Can Esmer, Dániel Marx, Karol Węgrzycki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07346.txt.
Introduction
Sujoy Bhore and co-authors study the Steiner Tree problem on graphs formed where geometric shapes overlap. Given disks, squares, or polygons in the plane, a few marked terminals must be linked through as few extra objects as possible. Planar problems often allow fast methods that grow slowly with solution size.
Here that hope fails. Assuming the Exponential-Time Hypothesis, no algorithm can run in subexponential time in the combined size measures, even for unit disks or unit squares. The hardness result closes a natural line of attack. Algorithm designers learn to seek approximations or different parameters instead of exact subexponential methods.
Catalog record
| CREATOR | Sujoy Bhore, Barış Can Esmer, Dániel Marx, Karol Węgrzycki |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 209 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07346