论文标题
最小跨越树拥塞问题的更好硬度结果
Better Hardness Results for the Minimum Spanning Tree Congestion Problem
论文作者
论文摘要
在跨越的树拥塞问题中，鉴于连接的图形$ g $，目标是计算$ g $中的跨度树$ t $，从而最大程度地减少其最大边缘交通拥堵，在$ g $中，边缘$ e $ t $ of Edge $ e $ t $的拥塞是$ g $中的$ g $的数量，在其endpoints travers travers travers $ e $ e $之间是$ g $中的独特路径。该问题已知是$ \ mathbb {np} $ - 很难，但其近似性仍然很少理解。在此问题的决策版本中，表示为$ k- \ textsf {stc} $，我们需要确定$ g $是否具有最多$ k $的跨度树。众所周知，$ k- \ textsf {stc} $ is $ \ mathbb {np} $ - 完整$ k \ ge 8 $。另一方面，$ 3- \ textsf {stc} $可以在多项式时间内解决，并且对于$ k \ in \ {4,5,6,7 \} $的复杂性状态仍然是一个开放的问题。我们通过证明$ k- \ textsf {stc} $是$ \ mathbb {np} $ - 完成$ k \ ge 5 $，从而实质上改善了早期的硬度结果。这仅留下$ k = 4 $打开的情况，并将近似值的下限提高到$ 1.2 $。 以证据表明最小化交通拥堵的证据，即使对于小恒定半径的图形也很难，我们认为$ k- \ textsf {stc} $仅限于半径$ 2 $的图表，我们证明该变体为$ \ mathbb {np {np {np} $ - 用于所有$ k \ ge 6 $。为了进一步探索这个方向，我们还研究了$ k- \ textsf {stc} d $的变体，其中的目的是确定该图是否具有深度-D $，最多只能$ k $。我们证明$ 6- \ textsf {stc} 2 $ is $ \ mathbb {np} $ - 即使在两部分图中也可以完成。对于二分图，我们通过证明$ 5- \ textsf {stc} 2 $是多项式时间可求解，从而建立了一个紧密的界限。此外，我们将此结果与多项式时间算法相互补充，用于两种涉及两部分图和对顶点度的限制的特殊情况。
In the spanning tree congestion problem, given a connected graph $G$, the objective is to compute a spanning tree $T$ in $G$ that minimizes its maximum edge congestion, where the congestion of an edge $e$ of $T$ is the number of edges 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 is still poorly understood. In the decision version of this problem, denoted $K-\textsf{STC}$, we need to determine if $G$ has a spanning tree with congestion 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 be solved 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 earlier hardness 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 on the approximation ratio to $1.2$. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we consider $K-\textsf{STC}$ restricted to graphs of radius $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 has a depth-$D$ spanning three of congestion at most $K$. We prove that $6-\textsf{STC}2$ is $\mathbb{NP}$-complete even for bipartite graphs. For bipartite graphs we establish a tight bound, by also proving that $5-\textsf{STC}2$ is polynomial-time solvable. Additionally, we complement this result with polynomial-time algorithms for two special cases that involve bipartite graphs and restrictions on vertex degrees.
