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 | 2020-05-13T06:54:34Z | |
dc.date.available | 2020-05-13T06:54:34Z | |
dc.date.issued | 2019-09-06 | |
dc.Published | Fomin V, Golovach P, Lokshtanov D, Panolan F, Saurabh S, Zehavi M. Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 2019; Article No. 47; pp. 47:1–47:14 | eng |
dc.identifier.issn | 1868-8969 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/22211 | |
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\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erd\H{o}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^{O(k)}|V(G)|^{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^{O(k)}n^{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 \epsilon>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+\epsilon)d. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Schloss Dagstuhl | en_US |
dc.rights | Attribution CC BY | eng |
dc.rights.uri | https://creativecommons.org/licenses/by/3.0/ | eng |
dc.title | Going Far From Degeneracy | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2020-01-17T14:47:07Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright © Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.esa.2019.47 | |
dc.identifier.cristin | 1774855 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.relation.project | Norges forskningsråd: 263317 | |
dc.relation.project | Norges forskningsråd: 249994 | |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2019, 47. | |