## 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}
^{(}
^{t}
^{log}
^{t}
^{)}· n
^{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
^{O}
^{(}
^{t}
^{log}
^{t}
^{)}· n
^{O}
^{(}
^{1}
^{)}. On the other hand, we show that if the input digraph is planar, then the running time can be improved to 2
^{O}
^{(}
^{t}
^{)}· n
^{O}
^{(}
^{1}
^{)}.

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings |

Editors | Andreas Brandstädt, Ekkehard Köhler, Klaus Meer |

Publisher | Springer |

Pages | 65-78 |

Number of pages | 14 |

ISBN (Print) | 9783030002558 |

DOIs | |

Publication status | Published - 2018 |

Event | 44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Germany Duration: 27 Jun 2018 → 29 Jun 2018 https://www.wg2018.b-tu.de/ |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11159 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) |
---|---|

Abbreviated title | WG2018 |

Country/Territory | Germany |

City | Cottbus |

Period | 27/06/18 → 29/06/18 |

Internet address |