Fomin, Fedor V. ;
Golovach, Petr A. ;
Lokshtanov, Daniel ;
Panolan, Fahad ;
Saurabh, Saket ;
Zehavi, Meirav
Going Far From Degeneracy
Abstract
An undirected graph G is ddegenerate 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 NPcomplete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2connected. 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 2connected nvertex 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 NPcomplete. 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 NPcomplete to decide whether a connected (2connected) 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:147:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11168},
URN = {urn:nbn:de:0030drops111688},
doi = {10.4230/LIPIcs.ESA.2019.47},
annote = {Keywords: Longest path, longest cycle, fixedparameter tractability, above guarantee parameterization}
}
06.09.2019
Keywords: 

Longest path, longest cycle, fixedparameter tractability, above guarantee parameterization 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 