Parameterized Complexity of the Spanning Tree Congestion Problem |
| |
Authors: | Hans L Bodlaender Fedor V Fomin Petr A Golovach Yota Otachi Erik Jan van Leeuwen |
| |
Affiliation: | 1. Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands 2. Department of Informatics, University of Bergen, P.O. Box 7803, 5020, Bergen, Norway 3. School of Engineering and Computing Sciences, Durham University, South Road, Durham, DH1 3LE, UK 4. Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan
|
| |
Abstract: | We study the problem of determining the spanning tree congestion of 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 most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|