A single exponential-time FPT algorithm for cactus contraction

DOI10.1016/J.TCS.2023.113803MaRDI QIDQ2697543zbMATH OpenOpenAlexFDO

Authors R. Krithika, Pranabendu Misra, Prafullkumar Tale

Publication date 12 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.113803

zbMATH Keywords

cactus graphsfixed parameter tractable algorithmsgraph contraction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• An FPT algorithm for contraction to cactus
• A fast algorithm for cactus representations of minimum cuts
• A near-linear time algorithm for constructing a cactus representation of minimum cuts
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• scientific article; zbMATH DE number 7378605
• Faster deterministic algorithm for cactus vertex deletion
• A linear time algorithm for computing longest paths in cactus graphs
• Designing FPT algorithms for cut problems using randomized contractions

Cites work

• Contracting few edges to remove forbidden induced subgraphs
• Edge-contraction problems
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Increasing the minimum degree of a graph by contractions
• Kernelization. Theory of parameterized preprocessing
• Lossy kernels for graph contraction problems
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• On the NP-hardness of edge-deletion and -contraction problems
• On the parameterized complexity of contraction to generalization of trees
• On the Parameterized Complexity Of Grid Contraction
• On the parameterized complexity of maximum degree contraction problem
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• Parameterized algorithms
• Parameterized complexity of three edge contraction problems with degree constraints
• Paths to trees and cacti
• Split contraction: the untold story
• The computational complexity of disconnected cut and \(2 K_2\)-partition

Cited in

(1)

• Graph modification of bounded size to minor-closed classes as fast as vertex deletion

This page was built for publication: A single exponential-time FPT algorithm for cactus contraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2697543)