Header menu link for other important links
X
A single exponential-time FPT algorithm for cactus contraction
, Pranabendu Misra, Prafullkumar Tale
Published in Elsevier B.V.
2023
Volume: 954
   
Abstract
For a collection F of graphs, the F-CONTRACTION problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F-CONTRACTION problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F-CONTRACTION in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F-CONTRACTION where F is the set of all cactus graphs and show that we can solve it in 2O(k)⋅|V(G)|O(1) time. © 2023 Elsevier B.V.
About the journal
JournalTheoretical Computer Science
PublisherElsevier B.V.
ISSN03043975
Open AccessNo