Directed Feedback Vertex Set is Fixed-Parameter Tractable

Igor Razgon; Barry O'Sullivan

Directed Feedback Vertex Set is Fixed-Parameter Tractable

Igor Razgon
, Barry O'Sullivan

University College Cork

Research output: Contribution to journal › Article › peer-review

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

Original language	English
Journal	Dagstuhl Seminar Proceedings
Volume	7281
Publication status	Published - 2007
Event	Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007 - Wadern, Germany Duration: 8 Jul 2007 → 13 Jul 2007

Keywords

Directed Feedback Vertex Set
Fixed-Parameter Tractability

Cite this

@article{839ff9bdac1745378e08295a1bad7d13,

title = "Directed Feedback Vertex Set is Fixed-Parameter Tractable",

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(8kk!∗poly(n)).",

keywords = "Directed Feedback Vertex Set, Fixed-Parameter Tractability",

author = "Igor Razgon and Barry O'Sullivan",

note = "Publisher Copyright: {\textcopyright} 2007 Dagstuhl Seminar Proceedings. All rights reserved.; Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007 ; Conference date: 08-07-2007 Through 13-07-2007",

year = "2007",

language = "English",

volume = "7281",

journal = "Dagstuhl Seminar Proceedings",

issn = "1862-4405",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

}

TY - JOUR

T1 - Directed Feedback Vertex Set is Fixed-Parameter Tractable

AU - Razgon, Igor

AU - O'Sullivan, Barry

PY - 2007

Y1 - 2007

N2 - 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(8kk!∗poly(n)).

AB - 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(8kk!∗poly(n)).

KW - Directed Feedback Vertex Set

KW - Fixed-Parameter Tractability

UR - https://www.scopus.com/pages/publications/84864177406

M3 - Article

AN - SCOPUS:84864177406

SN - 1862-4405

VL - 7281

JO - Dagstuhl Seminar Proceedings

JF - Dagstuhl Seminar Proceedings

T2 - Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007

Y2 - 8 July 2007 through 13 July 2007

ER -

Directed Feedback Vertex Set is Fixed-Parameter Tractable

Abstract

Keywords

Other files and links

Fingerprint

Cite this