From Trees to Binary Trees: Approximation Algorithms and a PTAS
Abstract
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 ∑uv∈ E(T) distS*(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)⊆ V(S*). We give a simple linear-time 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 iteratively consider subtrees of the tree T which contain all vertices below some vertex v and construct a solution where v has degree 1. For the PTAS, we cut T into smaller trees, solve these instances, modify the obtained solutions, and combine them to achieve a solution for the original instance.
Related
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- Maximal Center of Distances of Finite Ultrametric Spaces and Perfect Binary Trees
- Finite-Support Approximation in Variable-Coefficient Sobolev Spaces on Nonhomogeneous Flow-Measure Trees
- hp-adaptive trees for graph signal approximation
- The Distribution of the Deepest Leaves in Binary Trees
BibTeX
@misc{weisbrodt2026from,
title = {{From Trees to Binary Trees: Approximation Algorithms and a PTAS}},
author = {Fabian Weisbrodt and Florian Werner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39863},
eprint = {2610.39863},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39863},
}
RIS
TY - UNPB
TI - From Trees to Binary Trees: Approximation Algorithms and a PTAS
AU - Fabian Weisbrodt
AU - Florian Werner
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39863
UR - https://arxiv.org/abs/2610.39863
AB - 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 ∑_uv∈ E(T) 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)⊆ V(S^*). We give a simple linear-time 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 iteratively consider subtrees of the tree T which contain all vertices below some vertex v and construct a solution where v has degree 1. For the PTAS, we cut T into smaller trees, solve these instances, modify the obtained solutions, and combine them to achieve a solution for the original instance.
ER -