On directed feedback vertex set parameterized by treewidth

Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

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 )· 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 2 O ( t log t )· nO ( 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 )· nO ( 1 ).

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings
EditorsAndreas Brandstädt, Ekkehard Köhler, Klaus Meer
PublisherSpringer
Pages65-78
Number of pages14
ISBN (Print)9783030002558
DOIs
Publication statusPublished - 1 Jan 2018
Event44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Germany
Duration: 27 Jun 201829 Jun 2018
https://www.wg2018.b-tu.de/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11159 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)
Abbreviated titleWG2018
Country/TerritoryGermany
CityCottbus
Period27/06/1829/06/18
Internet address

Fingerprint

Dive into the research topics of 'On directed feedback vertex set parameterized by treewidth'. Together they form a unique fingerprint.

Cite this