Treffer: A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
Title:
A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
Authors:
Contributors:
Hao Sun
Publisher Information:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publication Year:
2024
Collection:
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics )
Subject Terms:
Document Type:
Fachzeitschrift
article in journal/newspaper<br />conference object
File Description:
application/pdf
Language:
English
Relation:
Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.18
DOI:
10.4230/LIPIcs.APPROX/RANDOM.2024.18
Availability:
Accession Number:
edsbas.CF02D0CE
Database:
BASE
Weitere Informationen
The minimum directed feedback vertex set problem consists in finding the minimum set of vertices that should be removed in order to make a directed graph acyclic. This is a well-known NP-hard optimization problem with applications in various fields, such as VLSI chip design, bioinformatics and transaction processing deadlock prevention and node-weighted network design. We show a constant factor approximation for the directed feedback vertex set problem in graphs of bounded genus.