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 |