Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
DOI10.1007/S00453-018-0419-4zbMATH Open1397.68106OpenAlexW2789598654MaRDI QIDQ722549FDOQ722549
Authors: Diptapriyo Majumdar, Venkatesh Raman 
Publication date: 26 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0419-4
Recommendations
- Structural Parameterizations of Feedback Vertex Set
- FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
- Generalized pseudoforest deletion: algorithms and uniform kernel
- On feedback vertex set: new measure and new structures
- Generalized pseudoforest deletion: algorithms and uniform kernel
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- A fast branching algorithm for cluster vertex deletion
- Minimum weakly fundamental cycle bases are hard to find
- A unified approximation algorithm for node-deletion problems
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- A \(4k^2\) kernel for feedback vertex set
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized algorithms
- Kernelization Lower Bounds by Cross-Composition
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Infeasibility of instance compression and succinct PCPs for NP
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Graph theory
- Kernel bounds for disjoint cycles and disjoint paths
- A cubic kernel for feedback vertex set and loop cutset
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Faster deterministic \textsc{Feedback Vertex Set}
- Data reduction for graph coloring problems
- On graphs with polynomially solvable maximum-weight clique problem
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover problem parameterized above and below tight bounds
- On feedback vertex set: new measure and new structures
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Vertex cover structural parameterization revisited
- Parameterized algorithms for deletion to \((r,\ell)\)-graphs
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Feedback vertex set on AT-free graphs
Cited In (8)
- Kernelization for feedback vertex set via elimination distance to a forest
- Kernelization for feedback vertex set via elimination distance to a forest
- FPT algorithms for connected feedback vertex set
- FPT algorithms and kernels for the directed \(k\)-leaf problem
- Structural parameterizations with modulator oblivion
- Structural parameterizations with modulator oblivion
- Structural parameterizations of Tracking Paths problem
- Structural Parameterizations of Feedback Vertex Set
This page was built for publication: Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722549)
