dc.contributor.author Fomin, Fedor dc.contributor.author Golovach, Petr dc.contributor.author Lokshtanov, Daniel dc.contributor.author Panolan, Fahad dc.contributor.author Saurabh, Saket dc.contributor.author Zehavi, Meirav dc.date.accessioned 2021-05-19T12:08:05Z dc.date.available 2021-05-19T12:08:05Z dc.date.created 2021-01-04T11:40:57Z dc.date.issued 2020 dc.Published SIAM Journal on Discrete Mathematics. 2020, 34 (3), 1578-1601. dc.identifier.issn 0895-4801 dc.identifier.uri https://hdl.handle.net/11250/2755693 dc.description.abstract 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ös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at least $d+1$. The proof of Erdös 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 “above guarantee parameterization” is optimal in the following sense: For any $\varepsilon>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$. en_US dc.language.iso eng en_US dc.publisher SIAM en_US dc.title Going Far from Degeneracy en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2020 Society for Industrial and Applied Mathematics en_US cristin.ispublished true cristin.fulltext postprint cristin.qualitycode 1 dc.identifier.doi https://doi.org/10.1137/19M1290577 dc.identifier.cristin 1864692 dc.source.journal SIAM Journal on Discrete Mathematics en_US dc.source.40 34 dc.source.14 3 dc.source.pagenumber 1578-1601 en_US dc.relation.project Norges forskningsråd: 263317 en_US dc.relation.project ERC-European Research Council: 819416 en_US dc.identifier.citation SIAM Journal on Discrete Mathematics. 2020, 34(3), 1587–1601 en_US dc.source.volume 34 en_US dc.source.issue 3 en_US
﻿