On Approximability of Steiner Tree in ℓp-metrics

In the Continuous Steiner Tree problem (CST), we are given as input a set of points (called terminals) in a metric space and asked for the minimum-cost tree connecting them. Additional points (called Steiner points) from the metric space can be introduced as nodes in the solution. In the Discrete Steiner Tree problem (DST), we are given in addition to the terminals, a set of facilities, and any solution tree connecting the terminals can only contain the Steiner points from this set of facilities.

Trevisan [SICOMP'00] showed that CST and DST are APX-hard when the input lies in the ℓ 1 -metric (and Hamming metric). Chlebík and Chlebíkov á [TCS'08] showed that DST is NP-hard to approximate to factor of 96/95 ≈ 1.01 in the graph metric (and consequently ℓ ∞ -metric).

Prior to this work, it was unclear if CST and DST are APX-hard in essentially every other popular metric.

In this work, we prove that DST is APX-hard in every ℓ 𝑝 -metric. We also prove that CST is APX-hard in the ℓ ∞ -metric. Finally, we relate CST and DST, by observing a gap preserving reduction from CST to DST in ℓ 𝑝 -metrics.

It is known that the APX-hardness of DST in ℓ 0 , ℓ 1 , and ℓ ∞ -metrics can be obtained from the APX-hardness of covering problems (with additional structure). Our main conceptual insight is that for certain ranges of 𝑝 (such as 𝑝 = 2), the soundness guarantees of covering problems might be insufficient to show that DST in the ℓ 𝑝 -metric is APX-hard, but the soundness guarantees of a packing problem (with requisite additional structure) is enough. Equipped with this insight,