Vis enkel innførsel

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSaurabh, Saket
dc.contributor.authorZehavi, Meirav
dc.PublishedFomin 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:14eng
dc.description.abstractAn 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.publisherSchloss Dagstuhlen_US
dc.rightsAttribution CC BYeng
dc.titleGoing Far From Degeneracyen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright © Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavien_US
dc.source.journalLeibniz International Proceedings in Informatics
dc.relation.projectNorges forskningsråd: 263317
dc.relation.projectNorges forskningsråd: 249994
dc.identifier.citationLeibniz International Proceedings in Informatics. 2019, 47.

Tilhørende fil(er)


Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY