A single exponential-time FPT algorithm for cactus contraction

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 2 O ( k ) ⋅ | V ( G ) | O ( 1 ) time.

Authors

• R. Krithika
• Pranabendu Misra
• Prafullkumar Tale

Keywords

• Fixed parameter tractable algorithms
• Graph contraction
• Cactus graphs