• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • University of Bergen Library
  • Registrations from Cristin
  • View Item
  •   Home
  • University of Bergen Library
  • Registrations from Cristin
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Going Far from Degeneracy

Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav
Journal article, Peer reviewed
Published version
Thumbnail
View/Open
PDF (387.3Kb)
URI
https://hdl.handle.net/11250/2755693
Date
2020
Metadata
Show full item record
Collections
  • Department of Informatics [1076]
  • Registrations from Cristin [12914]
Original version
SIAM Journal on Discrete Mathematics. 2020, 34(3), 1587–1601   https://doi.org/10.1137/19M1290577
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^{\mathcal{O}(k)}\cdot|V(G)|^{\mathcal{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^{\mathcal{O}(k)}\cdot n^{\mathcal{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 $\varepsilon>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+\varepsilon)d$.
Publisher
SIAM
Journal
SIAM Journal on Discrete Mathematics
Copyright
Copyright 2020 Society for Industrial and Applied Mathematics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit