License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07281.5
URN: urn:nbn:de:0030-drops-12333
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1233/
|
Go to the corresponding Portal |
Chen, Jianer ;
Liu, Yang ;
Lu, Songiian
Directed Feedback Vertex Set Problem is FPT
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)})$.
BibTeX - Entry
@InProceedings{chen_et_al:DagSemProc.07281.5,
author = {Chen, Jianer and Liu, Yang and Lu, Songiian},
title = {{Directed Feedback Vertex Set Problem is FPT}},
booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
pages = {1--17},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2007},
volume = {7281},
editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2007/1233},
URN = {urn:nbn:de:0030-drops-12333},
doi = {10.4230/DagSemProc.07281.5},
annote = {Keywords: Directed feedback vertex set problem, parameterized algorithm,}
}
|
Keywords: |
|
Directed feedback vertex set problem, parameterized algorithm, |
|
Collection: |
|
07281 - Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs |
|
Issue Date: |
|
2007 |
|
Date of publication: |
|
28.11.2007 |
