scientific article; zbMATH DE number 7204370

DOI10.4230/LIPIcs.MFCS.2017.36zbMath1441.68163MaRDI QIDQ5111250

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

Publication date: 26 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

parameterized algorithmskernelization(directed) feedback vertex set

Mathematics Subject Classification ID

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

Related Items

On the Complexity of Singly Connected Vertex Deletion, Towards a polynomial kernel for directed feedback vertex set, Adapting the Directed Grid Theorem into an FPT Algorithm, Unnamed Item, On the complexity of singly connected vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Fundamentals of parameterized complexity
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Disjoint cycles intersecting a set of vertices
• Improved algorithms for feedback vertex set problems
• A cubic kernel for feedback vertex set and loop cutset
• Packing directed circuits
• Approximating minimum feedback sets and multicuts in directed graphs
• Packing directed circuits fractionally
• Packing circuits in eulerian digraphs
• Faster deterministic \textsc{Feedback Vertex Set}
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Packing cycles through prescribed vertices
• On the hardness of losing width
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• 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
• (Meta) Kernelization
• On Feedback Vertex Set New Measure and New Structures
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Reducibility among Combinatorial Problems
• On Independent Circuits Contained in a Graph
• Inapproximability of H-Transversal/Packing
• Half-integrality, LP-branching and FPT Algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Packing directed cycles through a specified vertex set