DagSemProc.07281.5.pdf
- Filesize: 263 kB
- 17 pages
Document
Directed Feedback Vertex Set Problem is FPT
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7281
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-11-28
Cite As Get BibTex
Jianer Chen, Yang Liu, and Songiian Lu. Directed Feedback Vertex Set Problem is FPT. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07281.5
Abstract
To decide if the {sc parameterized feedback vertex set} problem
in directed graph is fixed-parameter tractable is a long standing
open problem. In this paper, we prove that the {sc parameterized
feedback vertex set} in directed graph is fixed-parameter
tractable and give the first FPT algorithm of running time
$O((1.48k)^kn^{O(1)})$ for it. As the {sc feedback arc set}
problem in directed graph can be transformed to a {sc
feedback vertex set} problem in directed graph,
hence we also show that the {sc parameterized feedback arc set}
problem can be solved in time of $O((1.48k)^kn^{O(1)})$.
Subject Classification
Keywords
- Directed feedback vertex set problem
- parameterized algorithm,
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads