English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In the spanning tree congestion problem, given a connected graph $G$, theobjective is to compute a spanning tree $T$ in $G$ that minimizes its maximumedge congestion, where the congestion of an edge $e$ of $T$ is the number ofedges in $G$ for which the unique path in $T$ between their endpoints traverses$e$. The problem is known to be $\mathbb{NP}$-hard, but its approximability isstill poorly understood. In the decision version of this problem, denoted$K-\textsf{STC}$, we need to determine if $G$ has a spanning tree withcongestion at most $K$. It is known that $K-\textsf{STC}$ is$\mathbb{NP}$-complete for $K\ge 8$. On the other hand, $3-\textsf{STC}$ can besolved in polynomial time, with the complexity status of this problem for $K\in\{4,5,6,7\}$ remaining an open problem. We substantially improve the earlierhardness results by proving that $K-\textsf{STC}$ is $\mathbb{NP}$-complete for$K\ge 5$. This leaves only the case $K=4$ open, and improves the lower bound onthe approximation ratio to $1.2$.  Motivated by evidence that minimizing congestion is hard even for graphs ofsmall constant radius, we consider $K-\textsf{STC}$ restricted to graphs ofradius $2$, and we prove that this variant is $\mathbb{NP}$-complete for all$K\ge 6$. Exploring further in this direction, we also examine the variant,denoted $K-\textsf{STC}D$, where the objective is to determine if the graph hasa depth-$D$ spanning three of congestion at most $K$. We prove that$6-\textsf{STC}2$ is $\mathbb{NP}$-complete even for bipartite graphs. Forbipartite graphs we establish a tight bound, by also proving that$5-\textsf{STC}2$ is polynomial-time solvable. Additionally, we complement thisresult with polynomial-time algorithms for two special cases that involvebipartite graphs and restrictions on vertex degrees.

Better Hardness Results for the Minimum Spanning Tree Congestion Problem