Directed Feedback Vertex Set is Fixed-Parameter Tractable

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Data Structures and Algorithms, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/132817

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0707.0282
 http://arxiv.org/abs/0707.0282

Collections

arXiv