Name
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 (2^{o(tlog t)}cdot n^{mathcal {O}(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 (2^{mathcal {O}(tlog t)}cdot n^{mathcal {O}(1)}). On the other hand, we show that if the input digraph is planar, then the running time can be improved to (2^{mathcal {O}(t)}cdot n^{mathcal {O}(1)}). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-030-00256-5_6 | workshop on graph theoretic concepts in computer science |
DocType | Volume | Citations |
Conference | abs/1707.01470 | 0 |
PageRank | References | Authors |
0.34 | 13 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marthe Bonamy | 1 | 128 | 23.20 |
| Łukasz Kowalik | 2 | 258 | 22.43 |
| Jesper Nederlof | 3 | 294 | 24.22 |
| michal pilipczuk | 4 | 403 | 51.93 |
| Arkadiusz Socala | 5 | 11 | 4.37 |
| Marcin Wrochna | 6 | 47 | 7.61 |