{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:28Z","timestamp":1740107128743,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T00:00:00Z","timestamp":1724284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T00:00:00Z","timestamp":1724284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100018818","name":"National Research, Development and Innovation Office","doi-asserted-by":"publisher","award":["TKP2021-NVA-02","K-132696"],"award-info":[{"award-number":["TKP2021-NVA-02","K-132696"]}],"id":[{"id":"10.13039\/501100018818","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>t<\/jats:italic> be a positive real number. A graph is called <jats:italic>t<\/jats:italic>-<jats:italic>tough<\/jats:italic> if the removal of any vertex set <jats:italic>S<\/jats:italic> that disconnects the graph leaves at most |<jats:italic>S<\/jats:italic>|\/<jats:italic>t<\/jats:italic> components. The toughness of a graph is the largest <jats:italic>t<\/jats:italic> for which the graph is <jats:italic>t<\/jats:italic>-tough. We prove that toughness is fixed-parameter tractable parameterized with the treewidth. More precisely, we give an algorithm to compute the toughness of a graph <jats:italic>G<\/jats:italic> with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(|V(G)|^3\\cdot \\textrm{tw}(G)^{2\\textrm{tw}(G)})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mtext>tw<\/mml:mtext>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mtext>tw<\/mml:mtext>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textrm{tw}(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mtext>tw<\/mml:mtext>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the treewidth. If the treewidth is bounded by a constant, then this is a polynomial algorithm.<\/jats:p>","DOI":"10.1007\/s00373-024-02828-y","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T10:17:46Z","timestamp":1724408266000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Algorithm to Compute the Toughness in Graphs with Bounded Treewidth"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5119-8681","authenticated-orcid":false,"given":"Gyula Y.","family":"Katona","sequence":"first","affiliation":[]},{"given":"Humara","family":"Khan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,22]]},"reference":[{"issue":"2","key":"2828_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a $$k$$-tree. SIAM J. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2828_CR2","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0166-218X(90)90001-S","volume":"28","author":"D Bauer","year":"1990","unstructured":"Bauer, D., Hakimi, S.L., Schmeichel, E.: Recognizing tough graphs is NP-hard. Discrete Appl. Math. 28, 191\u2013195 (1990)","journal-title":"Discrete Appl. Math."},{"key":"2828_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0012-365X(92)00047-U","volume":"124","author":"D Bauer","year":"1994","unstructured":"Bauer, D., Morgana, A., Schmeichel, E.: On the complexity of recognizing tough graphs. Discrete Math. 124, 13\u201317 (1994)","journal-title":"Discrete Math."},{"key":"2828_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0166-218X(97)00030-9","volume":"79","author":"D Bauer","year":"1997","unstructured":"Bauer, D., van den Heuvel, J., Morgana, A., Schmeichel, E.: The complexity of recognizing tough cubic graphs. Discrete Appl. Math. 79, 35\u201344 (1997)","journal-title":"Discrete Appl. Math."},{"key":"2828_CR5","first-page":"47","volume":"130","author":"D Bauer","year":"1998","unstructured":"Bauer, D., van den Heuvel, J., Morgana, A., Schmeichel, E.: The complexity of toughness in regular graphs. Congressus Numerantium 130, 47\u201361 (1998)","journal-title":"Congressus Numerantium"},{"issue":"2","key":"2828_CR6","first-page":"185","volume":"30","author":"D Berend","year":"2010","unstructured":"Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Prob. Math. Stat. 30(2), 185\u2013205 (2010)","journal-title":"Prob. Math. Stat."},{"issue":"1\u20132","key":"2828_CR7","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"issue":"6","key":"2828_CR8","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"2828_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Bonsma, P., Lokshtanov, D.: The fine details of fast dynamic programming over tree decompositions, In: International Symposium on Parameterized and Exact Computation, Springer, 41-53 (2013)","DOI":"10.1007\/978-3-319-03898-8_5"},{"key":"2828_CR10","first-page":"28","volume":"117","author":"H Broersma","year":"2015","unstructured":"Broersma, H.: How tough is toughness? Bull. EATCS 117, 28\u201352 (2015)","journal-title":"Bull. EATCS"},{"issue":"3","key":"2828_CR11","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1002\/jgt.21734","volume":"75","author":"HJ Broersma","year":"2014","unstructured":"Broersma, H.J., Patel, V., Pyatkin, A.: On toughness and hamiltonicity of $$2K_2$$-free graphs. J. Graph Theory 75(3), 244\u2013255 (2014)","journal-title":"J. Graph Theory"},{"issue":"3","key":"2828_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Tough graphs and hamiltonian circuits. Discrete Math. 5(3), 215\u2013228 (1973)","journal-title":"Discrete Math."},{"key":"2828_CR13","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2015.12.026","volume":"619","author":"B Courcelle","year":"2016","unstructured":"Courcelle, B., Durand, I.: Computations by fly-automata beyond monadic second-order logic. Theo. Comput. Sci. 619, 32\u201367 (2016)","journal-title":"Theo. Comput. Sci."},{"key":"2828_CR14","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, Springer: ISBN 978-3-319-21274-6 (2015)","DOI":"10.1007\/978-3-319-21275-3_1"},{"key":"2828_CR15","first-page":"145","volume":"38","author":"B Jackson","year":"1994","unstructured":"Jackson, B., Katerinis, P.: A characterization of 3\/2-tough cubic graphs. Ars Combinatoria 38, 145\u2013148 (1994)","journal-title":"Ars Combinatoria"},{"key":"2828_CR16","unstructured":"Kant\u00e9, M.M.: personal communication"},{"issue":"2","key":"2828_CR17","doi-asserted-by":"publisher","first-page":"401","DOI":"10.7151\/dmgt.2372","volume":"43","author":"GY Katona","year":"2023","unstructured":"Katona, G.Y., Varga, K.: Strengthening Some Complexity Results on Toughness of Graphs. Discussiones Mathematicae Graph Theory 43(2), 401\u2013419 (2023)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"2828_CR18","unstructured":"Kratsch, D., Kloks, T., M\u00fcller, H.: Computing the toughness and the scattering number for interval and other graphs, INRIA Research Report RR\u20132237 (1994)"},{"issue":"1\u20133","key":"2828_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(95)00190-8","volume":"150","author":"D Kratsch","year":"1996","unstructured":"Kratsch, D., Lehel, J., M\u00fcller, H.: Toughness, hamiltonicity and split graphs. Discrete Math. 150(1\u20133), 231\u2013245 (1996)","journal-title":"Discrete Math."},{"issue":"1","key":"2828_CR20","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/jgt.3190080116","volume":"8","author":"MM Matthews","year":"1984","unstructured":"Matthews, M.M., Sumner, D.P.: Hamiltonian results in $$K_{1,3}$$-free graphs. J. Graph Theory 8(1), 139\u2013146 (1984)","journal-title":"J. Graph Theory"},{"key":"2828_CR21","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors.\u00a0I. Excluding a forest, Journal of Combinatorial\u00a0Theory Series\u00a0B 35(1):39\u201361 (1983)","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"2828_CR22","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors.\u00a0II. Algorithmic aspects of tree-width, Journal of Algorithms 7(3):309\u2013322 (1986)","DOI":"10.1016\/0196-6774(86)90023-4"},{"issue":"1\u20133","key":"2828_CR23","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0012-365X(98)00156-3","volume":"190","author":"GJ Woeginger","year":"1998","unstructured":"Woeginger, G.J.: The toughness of split graphs. Discrete Math. 190(1\u20133), 295\u2013297 (1998)","journal-title":"Discrete Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02828-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02828-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02828-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T15:04:26Z","timestamp":1729782266000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02828-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,22]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["2828"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02828-y","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,8,22]]},"assertion":[{"value":"9 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"100"}}