{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T00:28:41Z","timestamp":1787358521110,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["MULTIVAL (grant 263317)"],"award-info":[{"award-number":["MULTIVAL (grant 263317)"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["CLASSIS (grant 249994)"],"award-info":[{"award-number":["CLASSIS (grant 249994)"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"crossref","award":["LOPPRE (819416)"],"award-info":[{"award-number":["LOPPRE (819416)"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erd\u00f6s and Gallai from 1959, every graph of degeneracy $d&gt;1$ contains a cycle of length at least $d+1$. The proof of Erd\u00f6s and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least $d+1$. But can we decide in polynomial time whether a graph contains a cycle of length at least $d+2$? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least $d+2$ is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether $G$ contains a cycle of length at least $d+k$ can be done in time $2^{\\mathcal{O}(k)}\\cdot|V(G)|^{\\mathcal{O}(1)}$. In other words, deciding whether a 2-connected $n$-vertex $G$ contains a cycle of length at least $d+\\log{n}$ can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least $d+1$ is NP-complete. However, we prove that if graph $G$ is connected, then deciding whether $G$ contains a path of length at least $d+k$ can be done in time $2^{\\mathcal{O}(k)}\\cdot n^{\\mathcal{O}(1)}$. We complement these results by showing that the choice of degeneracy as the \u201cabove guarantee parameterization\u201d is optimal in the following sense: For any $\\varepsilon&gt;0$ it is NP-complete to decide whether a connected (2-connected) graph of degeneracy $d$ has a path (cycle) of length at least $(1+\\varepsilon)d$.<\/jats:p>","DOI":"10.1137\/19m1290577","type":"journal-article","created":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T10:24:24Z","timestamp":1595240664000},"page":"1587-1601","source":"Crossref","is-referenced-by-count":8,"title":["Going Far from Degeneracy"],"prefix":"10.1137","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":true,"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":true,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,7,20]]},"reference":[{"key":"atypb1","first-page":"511","author":"Alon N.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/17M1148566"},{"key":"atypb4","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, P. Kaski, and M. Koivisto,\n                      Narrow Sieves for Parameterized Paths and Packings\n                      , preprint,https:\/\/arxiv.org\/abs\/1007.1161, 2010."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1001"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/080716475"},{"key":"atypb7","first-page":"298","author":"Chen J.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb8","first-page":"43","author":"Crowston R.","year":"2013","journal-title":"Germany"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, Cham, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024498"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.04.018"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328918"},{"key":"atypb15","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"atypb16","first-page":"1152","author":"Garg S.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9262-y"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.01.004"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/140980946"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1330-6"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1963-001-x"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9008-7"},{"key":"atypb23","first-page":"58","author":"Kneis J.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb24","first-page":"575","author":"Koutis I.","year":"2008","journal-title":"Berlin"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.08.004"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"atypb29","first-page":"239","author":"Monien B.","year":"1985","journal-title":"Amsterdam"},{"key":"atypb30","first-page":"182","author":"Naor M.","year":"1995","journal-title":"IEEE"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1004"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.04.024"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.02.005"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1290577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:30:30Z","timestamp":1787319030000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1290577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1290577"],"URL":"https:\/\/doi.org\/10.1137\/19m1290577","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}