DagSemProc.07281.4.pdf
- Filesize: 242 kB
- 14 pages
Document
Directed Feedback Vertex Set is Fixed-Parameter Tractable
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 AsGet BibTex
Igor Razgon and Barry O'Sullivan. Directed Feedback Vertex Set is Fixed-Parameter Tractable. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07281.4
https://doi.org/10.4230/DagSemProc.07281.4
Abstract
We resolve positively a long standing open question regarding the
fixed-parameter tractability of the parameterized Directed Feedback
Vertex Set problem. In particular, we propose an algorithm which
solves this problem in $O(8^kk!*poly(n))$.
Keywords
- Directed FVS
- Multicut
- Directed Acyclic Graph (DAG)
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads