Back to Search
Start Over
Going Far From Degeneracy
- Source :
- Leibniz International Proceedings in Informatics, SIAM Journal on Discrete Mathematics
- Publication Year :
- 2019
- Publisher :
- Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2019.
-
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$. publishedVersion
- Subjects :
- FOS: Computer and information sciences
Vertex (graph theory)
Discrete mathematics
Mathematics::Combinatorics
000 Computer science, knowledge, general works
Discrete Mathematics (cs.DM)
General Mathematics
010102 general mathematics
0102 computer and information sciences
Longest cycle
01 natural sciences
Degeneracy (graph theory)
Longest path problem
Combinatorics
Computer Science::Discrete Mathematics
010201 computation theory & mathematics
Computer Science - Data Structures and Algorithms
Computer Science
Data Structures and Algorithms (cs.DS)
0101 mathematics
Computer Science::Data Structures and Algorithms
Undirected graph
Classical theorem
Mathematics
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Leibniz International Proceedings in Informatics, SIAM Journal on Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....0a005c35d215a3d0a45c79dcb18a1b1c
- Full Text :
- https://doi.org/10.4230/lipics.esa.2019.47