Parameterized Complexity of the Spanning Tree Congestion Problem
Parameterized Complexity of the Spanning Tree Congestion Problem
复制标题
DOI：
10.1007/s00453-011-9565-7
复制
发表时间：
2011-09
期刊：
影响因子：
1.1
通讯作者：
H. Bodlaender;F. Fomin;P. Golovach;Y. Otachi;E. J. V. Leeuwen
中科院分区：
文献类型：
--
作者：
H. Bodlaender;F. Fomin;P. Golovach;Y. Otachi;E. J. V. Leeuwen
本文研究了图的平移树的确定问题。我们提出了一些鲜明的对比，在这个问题的参数化的复杂性。首先，我们证明了在无顶点子图（包含平面图、有界树宽图和有界亏格图的一般图类）上，确定给定图在mostk处是否有生成树拥塞的问题对于每个固定k都可以在线性时间内得到解决。我们还表明，对于每一个固定的kandd的问题是可解的线性时间图度在最多。相反，如果我们只允许一个顶点的无界度，问题立即成为NP-完全的任何fixedk≥8。此外，硬度的结果适用于图不包括完全图6顶点作为一个小的。我们还观察到，当fork≤3时，问题变得多项式时间可解。
We study the problem of determining thespanning tree congestionof a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at mostkcan be solved in linear time for every fixedk. We also show that for every fixedkanddthe problem is solvable in linear time for graphs of degree at mostd. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixedk≥8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that fork≤3 the problem becomes polynomially time solvable.