Towards a polynomial kernel for directed feedback vertex set

DOI10.4230/LIPICS.MFCS.2017.36zbMATH Open1441.68163MaRDI QIDQ5111250FDOQ5111250

Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, M. S. Ramanujan, Sebastian Ordyniak

Publication date: 26 May 2020

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

zbMATH Keywords

kernelizationparameterized algorithms(directed) feedback vertex set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Reducibility among Combinatorial Problems
• A 4 k ² 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?)
• 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}
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Disjoint cycles intersecting a set of vertices
• Packing directed circuits fractionally
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• (Meta) Kernelization
• Packing directed cycles through a specified vertex set
• Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
• Inapproximability of H-Transversal/Packing

Cited In (7)

• Towards a polynomial kernel for directed feedback vertex set
• Adapting the Directed Grid Theorem into an FPT Algorithm
• Parameterized algorithms for generalizations of directed feedback vertex set
• On the Complexity of Singly Connected Vertex Deletion
• Title not available (Why is that?)
• On the complexity of singly connected vertex deletion
• 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 Q5111250)