Faster fixed parameter tractable algorithms for finding feedback vertex sets

DOI10.1145/1159892.1159898zbMath1321.05275OpenAlexW2125350407MaRDI QIDQ2944523

C. R. Subramanian, Venkatesh Raman, Saket Saurabh

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1159892.1159898

zbMATH Keywords

girthfeedback vertex setparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

On the Complexity of Singly Connected Vertex Deletion ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Unnamed Item ⋮ Backdoors to Satisfaction ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Extremal properties of the bipartite vertex frustration of graphs ⋮ Enumerating minimal subset feedback vertex sets ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ On feedback vertex set: new measure and new structures ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Improved algorithms for feedback vertex set problems ⋮ New formulae for the bipartite vertex frustration and decycling number of graphs ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Mim-width. II. The feedback vertex set problem ⋮ Parameterizing above or below guaranteed values ⋮ Unnamed Item ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ On the complexity of singly connected vertex deletion ⋮ On group feedback vertex set parameterized by the size of the cutset

This page was built for publication: Faster fixed parameter tractable algorithms for finding feedback vertex sets