Faster deterministic \textsc{Feedback Vertex Set}
From MaRDI portal
Publication:2015151
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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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, 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, 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
- 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 2 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
