On directed feedback Vertex Set parameterized by treewidth

M. Bonamy; Ł. Kowalik; J. Nederlof; M. Pilipczuk; A. Socała; M. Wrochna

On directed feedback Vertex Set parameterized by treewidth

M. Bonamy, Ł. Kowalik, J. Nederlof, M. Pilipczuk, A. Socała, M. Wrochna

Research output: Contribution to journal › Article › Academic

190 Downloads (Pure)

Abstract

We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time 2o(tlogt)⋅nO(1) on general directed graphs, where t is the treewidth of the underlying undirected graph. This is matched by a dynamic programming algorithm with running time 2O(tlogt)⋅nO(1). On the other hand, we show that if the input digraph is planar, then the running time can be improved to 2O(t)⋅nO(1).

Original language	English
Article number	arXiv:1707.01470v2
Number of pages	20
Journal	arXiv
Publication status	Published - 5 Jul 2017

Access to Document

publisher versionFinal author version , 944 KB

Cite this

@article{4ae07366c8c443d19e4080ef870904e0,

title = "On directed feedback Vertex Set parameterized by treewidth",

abstract = "We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time 2o(tlogt)⋅nO(1) on general directed graphs, where t is the treewidth of the underlying undirected graph. This is matched by a dynamic programming algorithm with running time 2O(tlogt)⋅nO(1). On the other hand, we show that if the input digraph is planar, then the running time can be improved to 2O(t)⋅nO(1).",

keywords = "cs.DS, cs.CC",

author = "M. Bonamy and {\L}. Kowalik and J. Nederlof and M. Pilipczuk and A. Soca{\l}a and M. Wrochna",

note = "20p",

year = "2017",

month = jul,

day = "5",

language = "English",

journal = "arXiv",

issn = "2331-8422",

publisher = "Cornell University Library",

}

TY - JOUR

T1 - On directed feedback Vertex Set parameterized by treewidth

AU - Bonamy, M.

AU - Kowalik, Ł.

AU - Nederlof, J.

AU - Pilipczuk, M.

AU - Socała, A.

AU - Wrochna, M.

N1 - 20p

PY - 2017/7/5

Y1 - 2017/7/5

N2 - We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time 2o(tlogt)⋅nO(1) on general directed graphs, where t is the treewidth of the underlying undirected graph. This is matched by a dynamic programming algorithm with running time 2O(tlogt)⋅nO(1). On the other hand, we show that if the input digraph is planar, then the running time can be improved to 2O(t)⋅nO(1).

AB - We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time 2o(tlogt)⋅nO(1) on general directed graphs, where t is the treewidth of the underlying undirected graph. This is matched by a dynamic programming algorithm with running time 2O(tlogt)⋅nO(1). On the other hand, we show that if the input digraph is planar, then the running time can be improved to 2O(t)⋅nO(1).

KW - cs.DS

KW - cs.CC

M3 - Article

SN - 2331-8422

JO - arXiv

JF - arXiv

M1 - arXiv:1707.01470v2

ER -

On directed feedback Vertex Set parameterized by treewidth

Abstract

Access to Document

Fingerprint

Cite this