Fomin, Fedor V and Golovach, Petr A. and Panolan, Fahad and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav
(2020)
Going far from degeneracy.
SIAM Journal on Discrete Mathematics, 34 (3).
1587 1601.
ISSN 08954801
Full text not available from this repository.
(
Request a copy)
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 2O (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 2O (k) · nO (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 ∊ > 0 it is NPcomplete to decide whether a connected (2connected) graph of degeneracy d has a path (cycle) of length at least (1 + ∊)d. © 2020 Society for Industrial and Applied Mathematics.
[error in script]
IITH Creators: 
IITH Creators  ORCiD 

Panolan, Fahad  https://orcid/org/0000000162138687 

Item Type: 
Article

Additional Information: 
\ast Received by the editors September 30, 2019; accepted for publication (in revised form) April 29, 2020; published electronically July 20, 2020. A preliminary version of this paper appeared as an extended abstract in the proceedings of ESA 2019. https://doi.org/10.1137/19M1290577 Funding: The research was funded by the Research Council of Norway via the projects CLASSIS (grant 249994) and MULTIVAL (grant 263317), Swarnajayanti Fellowship grant DST/SJF/MSA01/201718, and by the European Research Council (ERC) via grant LOPPRE (reference 819416). \dagger Department of Informatics, University of Bergen, Bergen 5020, Norway (Fedor.Fomin@uib.no, Petr.Golovach@uib.no). \ddagger Department of Computer Science, University of California Santa Barbara, Santa Barbara, CA 93106 (daniello@ucsb.edu). \S Department of Computer Science and Engineering, IIT Hyderabad, Kandi 502285, India (fahad@iith.ac.in). \P Institute of Mathematical Sciences, HBNI, Chennai 400094, India (saket@imsc.res.in). \ B ... 
Uncontrolled Keywords: 
Above guarantee parameterization; Fixedparameter tractability; Longest cycle; Longest path 
Subjects: 
Computer science 
Divisions: 
Department of Computer Science & Engineering 
Depositing User: 
. LibTrainee 2021

Date Deposited: 
23 Nov 2022 12:57 
Last Modified: 
23 Nov 2022 12:57 
URI: 
http://raiith.iith.ac.in/id/eprint/11182 
Publisher URL: 
https://v2.sherpa.ac.uk/id/publication/32200 
OA policy: 
https://v2.sherpa.ac.uk/id/publication/32200 
Related URLs: 

Actions (login required)

View Item 