Towards a polynomial kernel for directed feedback vertex set

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

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

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

kernelization parameterized algorithms (directed) feedback vertex set

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 \(4k^2\) kernel for feedback vertex set
Faster fixed parameter tractable algorithms for finding feedback vertex sets
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
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
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 (9)

Towards a polynomial kernel for directed feedback vertex set
Parameterized algorithms for generalizations of directed feedback vertex set
On directed feedback vertex set parameterized by treewidth
On the Complexity of Singly Connected Vertex Deletion
Adapting the directed grid theorem into an FPT algorithm
On the complexity of singly connected vertex deletion
Brief announcement: Treewidth modulator: emergency exit for DFVS
A randomized polynomial kernel for subset feedback vertex set
Lossy reduction rules for the directed feedback vertex set problem

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)