Planar Length-Constrained Minimum Spanning Trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914322704236544 |
|---|---|
| author | Hershkowitz, D Ellis Huang, Richard Z |
| author_facet | Hershkowitz, D Ellis Huang, Richard Z |
| contents | In length-constrained minimum spanning tree (MST) we are given an $n$-node graph $G = (V,E)$ with edge weights $w : E \to \mathbb{Z}_{\geq 0}$ and edge lengths $l: E \to \mathbb{Z}_{\geq 0}$ along with a root node $r \in V$ and a length-constraint $h \in \mathbb{Z}_{\geq 0}$. Our goal is to output a spanning tree of minimum weight according to $w$ in which every node is at distance at most $h$ from $r$ according to $l$.
We give a polynomial-time algorithm for planar graphs which, for any constant $ε> 0$, outputs an $O\left(\log^{1+ε} n\right)$-approximate solution with every node at distance at most $(1+ε)h$ from $r$ for any constant $ε> 0$. Our algorithm is based on new length-constrained versions of classic planar separators which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree. Complementing this, we show that any algorithm on general graphs for length-constrained MST in which nodes are at most $2h$ from $r$ cannot achieve an approximation of $O\left(\log ^{2-ε} n\right)$ for any constant $ε> 0$ under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09002 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Planar Length-Constrained Minimum Spanning Trees Hershkowitz, D Ellis Huang, Richard Z Data Structures and Algorithms In length-constrained minimum spanning tree (MST) we are given an $n$-node graph $G = (V,E)$ with edge weights $w : E \to \mathbb{Z}_{\geq 0}$ and edge lengths $l: E \to \mathbb{Z}_{\geq 0}$ along with a root node $r \in V$ and a length-constraint $h \in \mathbb{Z}_{\geq 0}$. Our goal is to output a spanning tree of minimum weight according to $w$ in which every node is at distance at most $h$ from $r$ according to $l$. We give a polynomial-time algorithm for planar graphs which, for any constant $ε> 0$, outputs an $O\left(\log^{1+ε} n\right)$-approximate solution with every node at distance at most $(1+ε)h$ from $r$ for any constant $ε> 0$. Our algorithm is based on new length-constrained versions of classic planar separators which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree. Complementing this, we show that any algorithm on general graphs for length-constrained MST in which nodes are at most $2h$ from $r$ cannot achieve an approximation of $O\left(\log ^{2-ε} n\right)$ for any constant $ε> 0$ under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs. |
| title | Planar Length-Constrained Minimum Spanning Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.09002 |