@inproceedings{7ba772a6437c483e8d71ec09d1e6f944,
title = "Complexity results for the Spanning Tree Congestion Problem",
abstract = "We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved 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 ≥ 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k.",
keywords = "span tree, planar graph, linear time, tree decomposition, chordal graph",
author = "Y. Otachi and H.L. Bodlaender and \{van Leeuwen\}, E.J.",
note = "International Workshop on Graph Theoretic Concepts in Computer Science",
year = "2010",
doi = "10.1007/978-3-642-16926-7\_3",
language = "English",
isbn = "9783642169250",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "3--14",
editor = "D.M. Thilikos",
booktitle = "Graph-theoretic concepts in computer science",
}