{"id":"arxiv/2610.39863","url":"https://arxiv.org/abs/2610.39863","tags":["cs.DS","math.CO"],"score":0,"title":"From Trees to Binary Trees: Approximation Algorithms and a PTAS","domain":"cs.DS","source":"arxiv","authors":["Fabian Weisbrodt","Florian Werner"],"reviews":0,"subject":"cs.DS","summary":"Kellerhals, Krebs, Nichterlein, and Schmid introduced the optimization problem Tree in Binary Tree (TBT), where, given a tree $T$, the task is to find a binary tree $S^*$ with $V(T)=V(S^*)$ that minimizes $\\sum_{uv\\in E(T)} \\operatorname{dist}_{S^*}(u,v)$. They also introduced the variant Tree in Binary Tree With Steiner Nodes (TBT-SN), where the condition $V(T)=V(S^*)$ is relaxed to $V(T)\\subseteq V(S^*)$. We give a simple linear-time $\\frac{8}{3}$-approximation algorithm for TBT and a polynomial-time approximation scheme (PTAS) for TBT-SN. Our main building idea in both algorithms is to…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}