{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:24Z","timestamp":1772119404934,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T00:00:00Z","timestamp":1729900800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T00:00:00Z","timestamp":1729900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["CCF-2153723"],"award-info":[{"award-number":["CCF-2153723"]}]},{"name":"National Science Foundation","award":["CCF-2153723"],"award-info":[{"award-number":["CCF-2153723"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,1]]},"abstract":"Abstract<\/jats:title>\n \n In the spanning tree congestion problem, given a connected graph\n G<\/jats:italic>\n , the objective is to compute a spanning tree\n T<\/jats:italic>\n in\n G<\/jats:italic>\n that minimizes its maximum edge congestion, where the congestion of an edge\n e<\/jats:italic>\n of\n T<\/jats:italic>\n is the number of edges in\n G<\/jats:italic>\n for which the unique path in\n T<\/jats:italic>\n between their endpoints traverses\n e<\/jats:italic>\n . The problem is known to be\n \n \n $$\\mathbb{N}\\mathbb{P}$$<\/jats:tex-math>\n \n \n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratio\n o<\/jats:italic>\n (\n n<\/jats:italic>\n ). In the decision version of this problem, denoted\n \n \n $${\\varvec{K}-\\textsf {STC}}$$<\/jats:tex-math>\n \n \n \n K<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n STC<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we need to determine if\n G<\/jats:italic>\n has a spanning tree with congestion at most\n K<\/jats:italic>\n . It is known that\n \n \n $${\\varvec{K}-\\textsf {STC}}$$<\/jats:tex-math>\n \n \n \n K<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n STC<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is\n \n \n $$\\mathbb{N}\\mathbb{P}$$<\/jats:tex-math>\n \n \n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -complete for\n \n \n $$K\\ge 8$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \u2265<\/mml:mo>\n 8<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,\n \n \n $${\\varvec{3}-\\textsf {STC}}$$<\/jats:tex-math>\n \n \n \n 3<\/mml:mn>\n <\/mml:mrow>\n -<\/mml:mo>\n STC<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can be solved in polynomial time, with the complexity status of this problem for\n \n \n $$K\\in { \\left\\{ 4,5,6,7 \\right\\} }$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \u2208<\/mml:mo>\n \n 4<\/mml:mn>\n ,<\/mml:mo>\n 5<\/mml:mn>\n ,<\/mml:mo>\n 6<\/mml:mn>\n ,<\/mml:mo>\n 7<\/mml:mn>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n remaining an open problem. We substantially improve the earlier hardness results by proving that\n \n \n $${\\varvec{K}-\\textsf {STC}}$$<\/jats:tex-math>\n \n \n \n K<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n STC<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is\n \n \n $$\\mathbb{N}\\mathbb{P}$$<\/jats:tex-math>\n \n \n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -complete for\n \n \n $$K\\ge 5$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \u2265<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . This leaves only the case\n \n \n $$K=4$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n =<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider\n \n \n $${\\varvec{K}-\\textsf {STC}}$$<\/jats:tex-math>\n \n \n \n K<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n STC<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n restricted to graphs of radius 2, and we prove that this variant is\n \n \n $$\\mathbb{N}\\mathbb{P}$$<\/jats:tex-math>\n \n \n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -complete for all\n \n \n $$K\\ge 6$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \u2265<\/mml:mo>\n 6<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s00453-024-01278-5","type":"journal-article","created":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T03:01:45Z","timestamp":1729911705000},"page":"148-165","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Better Hardness Results for the Minimum Spanning Tree Congestion Problem"],"prefix":"10.1007","volume":"87","author":[{"given":"Huong","family":"Luu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,26]]},"reference":[{"key":"1278_CR1","doi-asserted-by":"crossref","unstructured":"Bhatt, S., Chung, F., Leighton, T., Rosenberg, A.: Optimal simulations of tree machines. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science. SFCS \u201986, pp. 274\u2013282. IEEE Computer Society, USA (1986)","DOI":"10.1109\/SFCS.1986.38"},{"key":"1278_CR2","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/BFb0040384","volume-title":"VLSI Algorithms and Architectures","author":"AL Rosenberg","year":"1988","unstructured":"Rosenberg, A.L.: Graph embeddings 1988: Recent breakthroughs, new directions. In: Reif, J.H. (ed.) VLSI Algorithms and Architectures, pp. 160\u2013169. Springer, New York, NY (1988)"},{"issue":"1","key":"1278_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0020-0190(94)90044-2","volume":"50","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Designing multi-commodity flow trees. Inf. Process. Lett. 50(1), 49\u201355 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1278_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.disc.2004.02.009","volume":"285","author":"MI Ostrovskii","year":"2004","unstructured":"Ostrovskii, M.I.: Minimal congestion trees. Discret. Math. 285(1), 219\u2013226 (2004)","journal-title":"Discret. Math."},{"key":"1278_CR5","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-030-42071-0_12","volume-title":"Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday","author":"Yota Otachi","year":"2020","unstructured":"Otachi, Yota: A survey on spanning tree congestion. In: Fomin, Fedor V., Kratsch, Stefan, van Leeuwen, Erik Jan (eds.) Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, pp. 165\u2013172. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_12"},{"key":"1278_CR6","unstructured":"L\u00f6wenstein, C.: In the complement of a dominating set. PhD thesis, Technische Universit\u00e4t at Ilmenau (2010)"},{"key":"1278_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-16926-7_3","volume-title":"Graph Theoretic Concepts in Computer Science","author":"Yota Otachi","year":"2010","unstructured":"Otachi, Yota, Bodlaender, Hans L., van Leeuwen, Erik Jan: Complexity results for the spanning tree congestion problem. In: Graph Theoretic Concepts in Computer Science, pp. 3\u201314. Springer Berlin Heidelberg, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16926-7_3"},{"key":"1278_CR8","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/978-3-642-20877-5_44","volume-title":"Theory and Applications of Models of Computation","author":"Yoshio Okamoto","year":"2011","unstructured":"Okamoto, Yoshio, Otachi, Yota, Uehara, Ryuhei, Uno, Takeaki: Hardness results and an exact exponential algorithm for the spanning tree congestion problem. In: Ogihara, Mitsunori, Tarui, Jun (eds.) Theory and Applications of Models of Computation, pp. 452\u2013462. Springer Berlin Heidelberg, Berlin, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20877-5_44"},{"issue":"13","key":"1278_CR9","doi-asserted-by":"publisher","first-page":"4215","DOI":"10.1016\/j.disc.2008.12.021","volume":"309","author":"K Kozawa","year":"2009","unstructured":"Kozawa, K., Otachi, Y., Yamazaki, K.: On spanning tree congestion of graphs. Discret. Math. 309(13), 4215\u20134224 (2009)","journal-title":"Discret. Math."},{"issue":"12","key":"1278_CR10","doi-asserted-by":"publisher","first-page":"1040","DOI":"10.1016\/j.disc.2011.03.002","volume":"311","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Kozawa, K., Matsushima, T., Otachi, Y.: Spanning tree congestion of k-outerplanar graphs. Discret. Math. 311(12), 1040\u20131045 (2011)","journal-title":"Discret. Math."},{"issue":"4","key":"1278_CR11","doi-asserted-by":"publisher","first-page":"753","DOI":"10.7151\/dmgt.1577","volume":"31","author":"K Kozawa","year":"2011","unstructured":"Kozawa, K., Otachi, Y.: Spanning tree congestion of rook\u2019s graphs. Discussiones Mathematicae Graph Theory 31(4), 753\u2013761 (2011)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"1278_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-011-9565-7","volume":"64","author":"H Bodlaender","year":"2012","unstructured":"Bodlaender, H., Fomin, F., Golovach, P., Otachi, Y., Leeuwen, E.: Parameterized complexity of the spanning tree congestion problem. Algorithmica 64, 1\u201327 (2012)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"1278_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0166-218X(00)00226-2","volume":"108","author":"S\u00e1ndor P Fekete","year":"2001","unstructured":"Fekete, S\u00e1ndor. P., Kremer, Jana: Tree spanners in planar graphs. Discr. Appl. Math. 108(1\u20132), 85\u2013103 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00226-2","journal-title":"Discr. Appl. Math."},{"issue":"3","key":"1278_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discret. Math. 8(3), 359\u2013387 (1995)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"1278_CR15","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1016\/j.jcss.2010.10.002","volume":"77","author":"FF Dragan","year":"2011","unstructured":"Dragan, F.F., Fomin, F.V., Golovach, P.A.: Spanners in sparse graphs. J. Comput. Syst. Sci. 77(6), 1108\u20131119 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1278_CR16","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/060666202","volume":"38","author":"Y Emek","year":"2009","unstructured":"Emek, Y., Peleg, D.: Approximating minimum max-stretch spanning trees on unweighted graphs. SIAM J. Comput. 38(5), 1761\u20131781 (2009)","journal-title":"SIAM J. Comput."},{"issue":"10","key":"1278_CR17","first-page":"1","volume":"141","author":"F Alvarruiz Bermejo","year":"2015","unstructured":"Alvarruiz Bermejo, F., Mart\u00ednez Alzamora, F., Vidal Maci\u00e1, A.M.: Improving the efficiency of the loop method for the simulation of water distribution networks. J. Water Resour. Plan. Manag. 141(10), 1\u201310 (2015)","journal-title":"J. Water Resour. Plan. Manag."},{"key":"1278_CR18","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating $$s-t$$ minimum cuts in $$\\tilde{O}(n^2)$$ time. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 47\u201355 (1996)","DOI":"10.1145\/237814.237827"},{"key":"1278_CR19","doi-asserted-by":"crossref","unstructured":"Fung, W.S., Hariharan, R., Harvey, N.J., Panigrahi, D.: A general framework for graph sparsification. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 71\u201380 (2011)","DOI":"10.1145\/1993636.1993647"},{"issue":"4","key":"1278_CR20","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.-H.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011)","journal-title":"SIAM J. Comput."},{"key":"1278_CR21","unstructured":"Chandran, L.S., Cheung, Y.K., Issac, D.: Spanning Tree Congestion and Computation of Generalized Gy\u00f6ri-Lov\u00e1sz Partition. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 107, 32\u201313214 (2018)"},{"key":"1278_CR22","doi-asserted-by":"publisher","unstructured":"Luu, H., Chrobak, M.: Better hardness results for the minimum spanning tree congestion problem. CoRR (2022) https:\/\/doi.org\/10.48550\/arXiv.2209.08219https:\/\/arxiv.org\/abs\/2209.08219","DOI":"10.48550\/arXiv.2209.08219"},{"issue":"4","key":"1278_CR23","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"1278_CR24","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-32033-3_18","volume-title":"Term Rewriting and Applications","author":"Ryo Yoshinaka","year":"2005","unstructured":"Yoshinaka, Ryo: Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete. In: Term Rewriting and Applications, pp. 235\u2013249. Springer Berlin Heidelberg, Berlin, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-32033-3_18"},{"key":"1278_CR25","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/S1571-0661(05)80043-X","volume":"40","author":"Klemens H\u00e4gele","year":"2001","unstructured":"H\u00e4gele, Klemens, \u00d3 D\u00fanlaing, Colm, Riis, S\u00f8ren.: The complexity of scheduling TV commercials. Electron. Notes Theor. Comput. Sci. 40, 162\u2013185 (2001). https:\/\/doi.org\/10.1016\/S1571-0661(05)80043-X","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"1278_CR26","doi-asserted-by":"crossref","unstructured":"Luu, H., Chrobak, M.: Better hardness results for the minimum spanning tree congestion problem. In: Proceedings of 17th International Conference and Workshop on Algorithms and Computation WALCOM\u201923, pp. 167\u2013178 (2023)","DOI":"10.1007\/978-3-031-27051-2_15"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01278-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01278-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01278-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:25:17Z","timestamp":1737102317000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01278-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,26]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1278"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01278-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3007244\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,26]]},"assertion":[{"value":"31 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}