Kernels for deletion to classes of acyclic digraphs
From MaRDI portal
Publication:1678165
DOI10.1016/j.jcss.2017.07.008zbMath1380.68207OpenAlexW2751689185MaRDI QIDQ1678165
Roohani Sharma, Saket Saurabh, Meirav Zehavi, Akanksha Agrawal
Publication date: 14 November 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6777/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items
On the Complexity of Singly Connected Vertex Deletion ⋮ Faster algorithm for pathwidth one vertex deletion ⋮ A polynomial kernel for funnel arc deletion set ⋮ Faster parameterized algorithm for pumpkin vertex deletion set ⋮ Unnamed Item ⋮ A Polynomial Kernel for Funnel Arc Deletion Set. ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ On the complexity of singly connected vertex deletion ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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 kernelization algorithm for \(d\)-hitting set
- 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
- Fixed-parameter tractability results for feedback set problems in tournaments
- Packing cycles through prescribed vertices
- 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
- 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
- Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- 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
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Packing directed cycles through a specified vertex set
This page was built for publication: Kernels for deletion to classes of acyclic digraphs
