Complexity results for the spanning tree congestion problem

摘要

We study the computational complexity of determining the spanning tree congestion of a graph. First, we show that the problem of determining whether a given graph has spanning tree congestion at most fixed k can be solved in linear time for graphs of bounded degree. Next, we show that the problem becomes NP-complete for every fixed k ^ 10 if we allow only one vertex of unbounded degree in the input graphs. We also show that it is NP-hard to approximate the spanning tree congestion of such graphs within a factor better than 11/10.%本論文では，グラフの全域木混雑度について研究する．初めに，与えられた次数制限されたグラフが，k以下の全域木混雑度を持つか否か決定する問題が，パラメータkが固定されている場合は線形時間で解ける事を示す．次に，与えられたグラフが次数制限されない頂点を1個でも持つと，固定されたk≧10 に対して，グラフがk以下の全域木混雑度を持つか否か決定する問題が，NP 完全である事を示す．さらに，11/10 より良い近似比の解を求める事がNP困難である事も示す．