A Polynomial Kernel for Funnel Arc Deletion Set.

DOI10.4230/lipics.ipec.2020.13OpenAlexW3117660523MaRDI QIDQ6089658

Unnamed Author

Publication date: 13 November 2023

Full work available at URL: http://arxiv.org/pdf/1911.05520.pdf

zbMATH Keywords

kernelsparameterized algorithmgraph editingfunnelsdirected feedback arc set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Fundamentals of parameterized complexity
• A kernelization algorithm for \(d\)-hitting set
• Kernels for deletion to classes of acyclic digraphs
• Polynomial kernels for deletion to classes of acyclic digraphs
• Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS
• Kernelization – Preprocessing with a Guarantee
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Kernelization
• Parameterized Algorithms
• Efficient algorithms for measuring the funnel-likeness of DAGs