Faster deterministic \textsc{Feedback Vertex Set}
From MaRDI portal
Publication:2015151
DOI10.1016/J.IPL.2014.05.001zbMATH Open1371.68116arXiv1306.3566OpenAlexW2084595628MaRDI QIDQ2015151FDOQ2015151
Authors: Tomasz Kociumaka, Marcin Pilipczuk 
Publication date: 23 June 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: We present two new deterministic algorithms for the Feedback Vertex Set problem parameterized by the solution size. We begin with a simple algorithm, which runs in O*((2 + phi)^k) time, where phi < 1.619 is the golden ratio. It already surpasses the previously fastest O*((1+2sqrt(2))^k)-time deterministic algorithm due to Cao et al. [SWAT 2010]. In our developments we follow the approach of Cao et al., however, thanks to a new reduction rule, we obtain not only better dependency on the parameter in the running time, but also a solution with simple analysis and only a single branching rule. Then, we present a modification of the algorithm which, using a more involved set of branching rules, achieves O*(3.592^k) running time.
Full work available at URL: https://arxiv.org/abs/1306.3566
Recommendations
- Parameterized and Exact Computation
- An improved FPT algorithm for independent feedback vertex set
- An improved FPT algorithm for independent feedback vertex set
- On feedback vertex set: new measure and new structures
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Reducibility among Combinatorial Problems
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Title not available (Why is that?)
- Finding odd cycle transversals.
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- A \(4k^2\) kernel for feedback vertex set
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Subset feedback vertex set is fixed-parameter tractable
- On feedback vertex set new measure and new structures
- Title not available (Why is that?)
- ON DISJOINT CYCLES
- Title not available (Why is that?)
- Parameterized and Exact Computation
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- Title not available (Why is that?)
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- A cubic kernel for feedback vertex set and loop cutset
- Title not available (Why is that?)
- Directed Subset Feedback Vertex Set is fixed-parameter tractable
- Fast Hamiltonicity checking via bases of perfect matchings
- Title not available (Why is that?)
Cited In (52)
- Improved FPT Algorithms for Deletion to Forest-Like Structures
- Sparsity in covering solutions
- Parameterised algorithms for deletion to classes of DAGs
- A parameterized complexity view on collapsing \(k\)-cores
- A parameterized algorithm for subset feedback vertex set in tournaments
- Improved FPT Algorithms for Deletion to Forest-Like Structures.
- Conflict free version of covering problems on graphs: classical and parameterized
- A polynomial sized kernel for tracking paths problem
- Approximability of the independent feedback vertex set problem for bipartite graphs
- Towards a polynomial kernel for directed feedback vertex set
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Kernelization for feedback vertex set via elimination distance to a forest
- An improved FPT algorithm for independent feedback vertex set
- Independent feedback vertex set for \(P_5\)-free graphs
- Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
- On the tractability of \(( k , i )\)-coloring
- On the Complexity of Singly Connected Vertex Deletion
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Improved analysis of highest-degree branching for feedback vertex set
- Title not available (Why is that?)
- An improved FPT algorithm for almost forest deletion problem
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
- Dynamic parameterized problems
- MIP formulations for induced graph optimization problems: a tutorial
- Linear time parameterized algorithms for subset feedback vertex set
- On the feedback number of 3-uniform linear extremal hypergraphs
- An improved parameterized algorithm for the independent feedback vertex set problem
- Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- Title not available (Why is that?)
- Simultaneous feedback edge set: a parameterized perspective
- Kernels for deletion to classes of acyclic digraphs
- Odd cycle transversal in mixed graphs
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
- Euler Digraphs
- On the complexity of singly connected vertex deletion
- On feedback vertex set: new measure and new structures
- Deletion to scattered graph classes. I: Case of finite number of graph classes
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Title not available (Why is that?)
- FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters
- A faster parameterized algorithm for pseudoforest deletion
- A polynomial kernel for block graph deletion
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Faster exact algorithms for some terminal set problems
- Title not available (Why is that?)
- A randomized polynomial kernel for subset feedback vertex set
- A naive algorithm for feedback vertex set
- Title not available (Why is that?)
This page was built for publication: Faster deterministic \textsc{Feedback Vertex Set}
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2015151)
