Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

DOI10.1007/978-3-642-31594-7_20zbMath1272.68149OpenAlexW2569542361MaRDI QIDQ2843251

Dániel Marx, Rajesh Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: http://eprints.sztaki.hu/8572/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Parameterized Resiliency Problems via Integer Linear Programming ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Hitting Selected (Odd) Cycles ⋮ Multi-Budgeted Directed Cuts ⋮ List H-coloring a graph by removing few vertices ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Multi-budgeted directed cuts ⋮ Backdoors to tractable answer set programming

This page was built for publication: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable