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

CREATORSujoy Bhore, Barış Can Esmer, Dániel Marx, Karol Węgrzycki
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE209 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07346

Browse the full library · About the Tower of Babel