Towards a polynomial kernel for directed feedback vertex set
From MaRDI portal
Publication:2663705
DOI10.1007/S00453-020-00777-5OpenAlexW2775670884MaRDI QIDQ2663705FDOQ2663705
Authors: Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan 
Publication date: 19 April 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00777-5
Recommendations
- Towards a polynomial kernel for directed feedback vertex set
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Brief announcement: Treewidth modulator: emergency exit for DFVS
- Parameterized algorithms for generalizations of directed feedback vertex set
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
Cites Work
- Fundamentals of parameterized complexity
- Reducibility among combinatorial problems
- 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
- A fixed-parameter algorithm for the directed feedback vertex set problem
- On feedback vertex set new measure and new structures
- Title not available (Why is that?)
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Title not available (Why is that?)
- Half-integrality, LP-branching and FPT algorithms
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized algorithms
- Improved algorithms for feedback vertex set problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
- On Independent Circuits Contained in a Graph
- Kernelization using structural parameters on sparse graph classes
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Packing cycles through prescribed vertices
- A cubic kernel for feedback vertex set and loop cutset
- Approximating minimum feedback sets and multicuts in directed graphs
- Faster deterministic \textsc{Feedback Vertex Set}
- On the hardness of losing width
- Packing directed circuits
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Packing circuits in eulerian digraphs
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Disjoint cycles intersecting a set of vertices
- Packing directed circuits fractionally
- (Meta) kernelization
- Packing directed cycles through a specified vertex set
- Constant factor approximation for subset feedback set problems via a new LP relaxation
- Directed subset feedback vertex set is fixed-parameter tractable
- Inapproximability of \(H\)-transversal/packing
- Towards a polynomial kernel for directed feedback vertex set
- Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS
Cited In (10)
- Towards a polynomial kernel for directed feedback vertex set
- Parameterized algorithms for generalizations of directed feedback vertex set
- Slim tree-cut width
- On directed feedback vertex set parameterized by treewidth
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- Fine-grained parameterized complexity analysis of knot-free vertex deletion -- a deadlock resolution graph problem
- Kernels for deletion to classes of acyclic digraphs
- Kernels for deletion to classes of acyclic digraphs
- Brief announcement: Treewidth modulator: emergency exit for DFVS
- A randomized polynomial kernel for subset feedback vertex set
This page was built for publication: Towards a polynomial kernel for directed feedback vertex set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2663705)
