Going far from degeneracy

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 0895-4801

Full text not available from this repository. (Request a copy)

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 2O (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 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 NP-complete to decide whether a connected (2-connected) 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/0000-0001-6213-8687

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/MSA-01/2017-18, 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; Fixed-parameter 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