解説放送でも触れられていたように，同じ問題 (Rectilinear Steiner Arborescence Problem) が理論計算機科学分野で研究されています． 私は偶然この結果を知っていたので，この貪欲法の結果を評価関数にした貪欲法をすることで，団子から少しだけ抜け出しました．

\(2\) 近似アルゴリズム（ 23 位に並ぶ貪欲法と \(\mathrm{O}(n \log n)\) 時間の実装）
Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, Peter W. Shor: The rectilinear Steiner arborescence problem. Algorithmica, 1992.
https://doi.org/10.1007/BF01758762
https://x.com/ygussany/status/1835318265922687453

NP 困難性
Weiping Shi, Chen Su: The rectilinear Steiner arborescence problem is NP-complete. SIAM Journal on Computing, 2005. (Also in Proc. SODA, 2000.)
https://doi.org/10.1137/S0097539704371353
https://x.com/ygussany/status/1836365191405281791