Exact Algorithms for Minimum Steiner Point Trees

Abstract

Given distinct terminals $P\subset R^2$ and $R>0$, the Steiner tree problem with minimum number of Steiner points and bounded edge length asks for a straight line tree spanning $P$, with every edge of length at most $R$, that minimizes the number of Steiner points. Length is measured in a fixed $L_p$ metric with $p\in Q_{\ge 1}\cup \{\infty \}$. The optimum $k$ is not bounded by $n$, even in two-terminal case. We give a deterministic exact algorithm that computes an optimal implicit representation in $n^{O(n)}$ time, independent of $k$, in the computation model of Section~\ref{subseccomputation}. The representation consists of a full Steiner topology, exact branch coordinates, and a segment count for each topology edge. Subdivision requires additional time $\hat{I}˜(n+k)$. For each full Steiner topology, the feasible segment count vectors are the integer points of a convex projection in $O(n)$ dimensions. A continuous relaxation restricts the integer optimum to $2n-3$ consecutive values. Exact semialgebraic routines and a flatness recursion in integral lattice coordinates decide these values. Together with the parameterized bottleneck algorithm of Bandyapadhyay et al., this gives the value bound $\min \{n^{O(n)},k^{O(k)}{n}^{O(1)}\}$ for every fixed metric considered here.