The Exact Complexity of ε-Dense Steiner Tree

In the ε-Dense Steiner Tree problem of Karpinski and Zelikovsky, every terminal is adjacent to at least an ε-fraction of the non-terminals, and a Steiner tree with the fewest edges is sought. For every fixed ε > 0 the problem has a polynomial-time approximation scheme. At an Oberwolfach problem session in 2004, Hauptmann asked for hardness results and noted that it was not even known whether the exact problem is NP-hard; the question was still described as open in 2015 and in 2020. We show that for every fixed ε ∈ (0,1] the problem can be solved exactly in time n^{O(log n/ε)}. The main step is a structural lemma: if H is any set of non-terminals that are all adjacent to terminals, and G[S ∪ H] has r components, then every optimal tree has at most |H| + 2r − 2 Steiner vertices adjacent to terminals. Consequently the problem is not NP-hard, even under Turing reductions, unless NP ⊆ DTIME(2^{O(log² n)}). Conversely, for every fixed ε ∈ (0,1), a reduction from 3-SAT in the style of Megiddo and Vishkin, combined with a dense covering gadget over F_q^d, shows that the problem has no N^{o(log N)}-time algorithm unless the Exponential Time Hypothesis (ETH) fails, and that it is not in P unless FPT = W[2]. Hence, assuming ETH, exact ε-Dense Steiner Tree is neither in P nor NP-hard. Of the two halves of this statement, "not NP-hard" needs only NP ⊄ QP, while "not in P" needs ETH or FPT ≠ W[2]. This is an unrefereed note.