Directed Feedback Vertex Set is Fixed-Parameter Tractable

Razgon, Igor; O'Sullivan, Barry

doi:10.4230/DagSemProc.07281.4

Document

Directed Feedback Vertex Set is Fixed-Parameter Tractable

Authors Igor Razgon, Barry O'Sullivan

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 7281
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2007-11-28

PDF

File

DagSemProc.07281.4.pdf

Filesize: 242 kB
14 pages

Document Identifiers

DOI: 10.4230/DagSemProc.07281.4
URN: urn:nbn:de:0030-drops-12363

Author Details

Igor Razgon

Barry O'Sullivan

Cite As Get 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

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))$.

Subject Classification

Keywords

Directed FVS
Multicut
Directed Acyclic Graph (DAG)

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail