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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT, ECCC TR03-049 (2003)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1–45 (1998)
Brandstädt, A., Dragan, F.F., Le, H.-O., Le, V.B.: Tree spanners on chordal graphs: complexity and algorithms. Theoret. Comput. Sci. 310, 329–354 (2004)
Brandstädt, A., Dragan, F.F., Le, H.-O., Le, V.B., Uehara, R.: Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47, 27–51 (2007)
Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discrete Math. 8, 359–387 (1995)
Castejón, A., Ostrovskii, M.I.: Minimum congestion spanning trees of grids and discrete toruses. Discuss. Math. Graph Theory 29, 511–519 (2009)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Courcelle, B.: The monadic second-order logic of graphs III: Tree-decompositions, minor and complexity issues. Theor. Inform. Appl. 26, 257–286 (1992)
Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)
Dragan, F.F., Fomin, F.V., Golovach, P.A.: Spanners in sparse graphs. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 597–608. Springer, Heidelberg (2008)
Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Appl. Math. 108, 85–103 (2001)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Hliněný, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. J. Comput. 51, 326–362 (2008)
Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21, 549–568 (1974)
Hruska, S.W.: On tree congestion of graphs. Discrete Math. 308, 1801–1809 (2008)
Kozawa, K., Otachi, Y., Yamazaki, K.: On spanning tree congestion of graphs. Discrete Math. 309, 4215–4224 (2009)
Law, H.-F.: Spanning tree congestion of the hypercube. Discrete Math. 309, 6644–6648 (2009)
Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston (1976)
Löwenstein, C., Rautenbach, D., Regen, F.: On spanning tree congestion. Discrete Math. 309, 4653–4655 (2009)
Ostrovskii, M.I.: Minimal congestion trees. Discrete Math. 285, 219–226 (2004)
Ostrovskii, M.I.: Minimum congestion spanning trees in planar graphs. Discrete Math. 310, 1204–1209 (2010)
Raspaud, A., Sýkora, O., Vrťo, I.: Congestion and dilation, similarities and differences: A survey. In: SIROCCO 2000, pp. 269–280. Carleton Scientific (2000)
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B 52, 153–190 (1991)
Simonson, S.: A variation on the min cut linear arrangement problem. Math. Syst. Theory 20, 235–252 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J. (2010). Complexity Results for the Spanning Tree Congestion Problem. In: Thilikos, D.M. (eds) Graph Theoretic Concepts in Computer Science. WG 2010. Lecture Notes in Computer Science, vol 6410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16926-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-16926-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16925-0
Online ISBN: 978-3-642-16926-7
eBook Packages: Computer ScienceComputer Science (R0)