Directed Feedback Vertex Set Problem is FPT

Authors Jianer Chen, Yang Liu, Songiian Lu



PDF
Thumbnail PDF

File

DagSemProc.07281.5.pdf
  • Filesize: 263 kB
  • 17 pages

Document Identifiers

Author Details

Jianer Chen
Yang Liu
Songiian Lu

Cite AsGet 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)})$.
Keywords
  • Directed feedback vertex set problem
  • parameterized algorithm,

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail