Two Complexity Results on Spanning-Tree Congestion Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917265963745280 |
|---|---|
| author | Atalig, Sunny Chrobak, Marek Dürr, Christoph Kolman, Petr Luu, Huong Sgall, Jiří Zhu, Gregory |
| author_facet | Atalig, Sunny Chrobak, Marek Dürr, Christoph Kolman, Petr Luu, Huong Sgall, Jiří Zhu, Gregory |
| contents | In the spanning-tree congestion problem ($\mathsf{STC}$), we are given a graph $G$, and the objective is to compute a spanning tree of $G$ that minimizes the maximum edge congestion. While $\mathsf{STC}$ is known to be $\mathbb{NP}$-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most $Δ$, it is known that $\mathsf{STC}$ is $\mathbb{NP}$-hard when $Δ\ge 8$. We provide a complete resolution of this variant, by showing that $\mathsf{STC}$ remains $\mathbb{NP}$-hard for each degree bound $Δ\ge 3$. (ii) In the decision version of $\mathsf{STC}$, given an integer $K$, the goal is to determine whether the congestion of $G$ is at most $K$. We prove that this variant is polynomial-time solvable for $K$-edge-connected graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_10881 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Two Complexity Results on Spanning-Tree Congestion Problems Atalig, Sunny Chrobak, Marek Dürr, Christoph Kolman, Petr Luu, Huong Sgall, Jiří Zhu, Gregory Data Structures and Algorithms In the spanning-tree congestion problem ($\mathsf{STC}$), we are given a graph $G$, and the objective is to compute a spanning tree of $G$ that minimizes the maximum edge congestion. While $\mathsf{STC}$ is known to be $\mathbb{NP}$-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most $Δ$, it is known that $\mathsf{STC}$ is $\mathbb{NP}$-hard when $Δ\ge 8$. We provide a complete resolution of this variant, by showing that $\mathsf{STC}$ remains $\mathbb{NP}$-hard for each degree bound $Δ\ge 3$. (ii) In the decision version of $\mathsf{STC}$, given an integer $K$, the goal is to determine whether the congestion of $G$ is at most $K$. We prove that this variant is polynomial-time solvable for $K$-edge-connected graphs. |
| title | Two Complexity Results on Spanning-Tree Congestion Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.10881 |