License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.47
URN: urn:nbn:de:0030-drops-111688
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11168/
Go to the corresponding LIPIcs Volume Portal


Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Going Far From Degeneracy

pdf-format:
LIPIcs-ESA-2019-47.pdf (0.5 MB)


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^{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.

BibTeX - Entry

@InProceedings{fomin_et_al:LIPIcs:2019:11168,
  author =	{Fedor V. Fomin and Petr A. Golovach and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
  title =	{{Going Far From Degeneracy}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11168},
  URN =		{urn:nbn:de:0030-drops-111688},
  doi =		{10.4230/LIPIcs.ESA.2019.47},
  annote =	{Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization}
}

Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization
Seminar: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI