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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555–581 (1992)
Brandstädt, A., Dragan, F.F., Le, H.-O., Le, V.B.: Tree spanners on chordal graphs: complexity and algorithms. Theor. 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., 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)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864–894 (1994)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52, 866–893 (2005)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discrete Math. 18(3), 501–511 (2004)
Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth,with combinatorial and algorithmic applications through bidimensionality. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 682–689. SIAM, Philadelphia (2005)
Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28, 19–36 (2008)
Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 637–646. IEEE Computer Society, Los Alamitos (2005)
Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Approximation algorithms via structural results for apex-minor-free graphs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). Lecture Notes in Computer Science, vol. 5555, pp. 316–327. Springer, Berlin (2009)
Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005)
Dragan, F.F., Fomin, F.V., Golovach, P.A.: Spanners in sparse graphs, Journal of Computer and System Sciences, doi:10.1016/j.jcss.2010.10.002
Dragan, F.F., Fomin, F.V., Golovach, P.A.: Approximation of minimum weight spanners for sparse graphs. Theor. Comput. Sci. 412, 846–852 (2011)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275–291 (2000)
Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Appl. Math. 108, 85–103 (2001)
Fomin, F.V., Golovach, P.A., van Leeuwen, E.J.: Spanners of bounded degree graphs. Inf. Process. Lett. 111, 142–144 (2011)
Geelen, J.F., Richter, R.B., Salazar, G.: Embedding grids in surfaces. Eur. J. Comb. 25, 785–792 (2004)
Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23, 613–632 (2003)
Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99, 218–228 (2009)
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)
Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52, 233–252 (1994)
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, New York (1976)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 329–343 (1982)
Löwenstein, C., Rautenbach, D., Regen, F.: On spanning tree congestion. Discrete Math. 309, 4653–4655 (2009)
MacLane, S.: A combinatorial condition for planar graphs. Fundam. Math. 28, 22–32 (1937)
Mohar, B.: Combinatorial local planarity and the width of graph embeddings. Can. J. Math. 44, 1272–1288 (1992)
Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)
Okamoto, Y., Otachi, Y., Uehara, R., Uno, T.: Hardness results and an exact exponential algorithm for the spanning tree congestion problem. In: Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011). Lecture Notes in Comput. Sci., vol. 6648, pp. 452–462 (2011)
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)
Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.: Complexity results for the spanning tree congestion problem. In: Proceedings of the 6th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Comput. Sci., vol. 6410, pp. 3–14 (2010)
Peleg, D.: Low stretch spanning trees. In: Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002). Lecture Notes in Comput. Sci., vol. 2420, pp. 68–80 (2002)
Raspaud, A., Sýkora, O., Vrťo, I.: Congestion and dilation, similarities and differences: a survey. In: Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2000), pp. 269–280. Carleton Scientific, Oxford (2000)
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52, 153–190 (1991)
Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89, 43–76 (2003)
Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory, Ser. B 62, 323–348 (1994)
Simonson, S.: A variation on the min cut linear arrangement problem. Math. Syst. Theory 20, 235–252 (1987)
Thomassen, C.: A simpler proof of the excluded minor theorem for higher surfaces. J. Comb. Theory, Ser. B 70, 306–311 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Extended abstract of some results in this paper appeared in the proceedings of WG 2010 [40].
Y. Otachi belongs to JSPS Research Fellow.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Bodlaender, H.L., Fomin, F.V., Golovach, P.A. et al. Parameterized Complexity of the Spanning Tree Congestion Problem. Algorithmica 64, 85–111 (2012). https://doi.org/10.1007/s00453-011-9565-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9565-7