Faster deterministic \textsc{Feedback Vertex Set}
From MaRDI portal
Publication:2015151
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.
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
Cites work
- Title not available (Why is no real title available?)
- scientific article; zbMATH DE number 5485529 (Why is no real title available?)
- scientific article; zbMATH DE number 3904590 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1467487 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- 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
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Directed Subset Feedback Vertex Set is fixed-parameter tractable
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Finding odd cycle transversals.
- Improved algorithms for feedback vertex set problems
- ON DISJOINT CYCLES
- On feedback vertex set new measure and new structures
- Parameterized and Exact Computation
- Reducibility among combinatorial problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
Cited in
(52)- A parameterized complexity view on collapsing \(k\)-cores
- 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
- Generalized pseudoforest deletion: algorithms and uniform kernel
- 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
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Towards a polynomial kernel for directed feedback vertex set
- scientific article; zbMATH DE number 7286685 (Why is no real title available?)
- scientific article; zbMATH DE number 7650230 (Why is no real title available?)
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Independent feedback vertex set for \(P_5\)-free graphs
- An improved FPT algorithm for independent feedback vertex set
- Kernelization for feedback vertex set via elimination distance to a forest
- On the tractability of ( k , i )-coloring
- Improved analysis of highest-degree branching for feedback vertex set
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- An improved FPT algorithm for almost forest deletion problem
- On the Complexity of Singly Connected Vertex Deletion
- Dynamic parameterized problems
- FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
- Parameterized complexity of deletion to scattered graph classes
- Euler digraphs
- MIP formulations for induced graph optimization problems: a tutorial
- On the feedback number of 3-uniform linear extremal hypergraphs
- Linear time parameterized algorithms for subset feedback vertex set
- 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
- Simultaneous feedback edge set: a parameterized perspective
- Kernels for deletion to classes of acyclic digraphs
- Conflict free feedback vertex set: a parameterized dichotomy
- Odd cycle transversal in mixed graphs
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
- On the complexity of singly connected vertex deletion
- Improved FPT Algorithms for Deletion to Forest-Like Structures
- On feedback vertex set: new measure and new structures
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Deletion to scattered graph classes. I: Case of finite number of graph classes
- scientific article; zbMATH DE number 7278081 (Why is no real title available?)
- 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
- A randomized polynomial kernel for subset feedback vertex set
- A naive algorithm for feedback vertex set
- Parameterized vertex deletion problems for hereditary graph classes with a block property
- Sparsity in covering solutions
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)
