Faster deterministic \textsc{Feedback Vertex Set}

DOI10.1016/J.IPL.2014.05.001zbMath1371.68116arXiv1306.3566OpenAlexW2084595628MaRDI QIDQ2015151

Marcin Pilipczuk, Tomasz Kociumaka

Publication date: 23 June 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.3566

zbMATH Keywords

graph algorithmsbranchingfixed-parameter algorithmFeedback Vertex Set

Mathematics Subject Classification ID

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

Related Items (51)

Faster exact algorithms for some terminal set problems ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ On the feedback number of 3-uniform linear extremal hypergraphs ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ A polynomial kernel for block graph deletion ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Odd cycle transversal in mixed graphs ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Unnamed Item ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A naive algorithm for feedback vertex set ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ On feedback vertex set: new measure and new structures ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ On the tractability of \(( k , i )\)-coloring ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures ⋮ Dynamic parameterized problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ Sparsity in covering solutions ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Unnamed Item ⋮ A polynomial sized kernel for tracking paths problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Euler Digraphs ⋮ On the complexity of singly connected vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• A cubic kernel for feedback vertex set and loop cutset
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• A 4 k ² kernel for feedback vertex set
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• On Feedback Vertex Set New Measure and New Structures
• ON DISJOINT CYCLES
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Reducibility among Combinatorial Problems
• Parameterized and Exact Computation
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: Faster deterministic \textsc{Feedback Vertex Set}