Fomin, Fedor V and Golovach, Petr A and Joshi, Saurabh and et al, .
(2019)
Going far from degeneracy.
In: 27th Annual European Symposium on Algorithms, ESA, 911 September 2019, Munich/Garching, Germany.
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.
[error in script]
Actions (login required)

View Item 