On directed feedback vertex set parameterized by treewidth

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)

Samenvatting

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

Originele taal-2Engels
TitelGraph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings
RedacteurenAndreas Brandstädt, Ekkehard Köhler, Klaus Meer
UitgeverijSpringer
Pagina's65-78
Aantal pagina's14
ISBN van geprinte versie9783030002558
DOI's
StatusGepubliceerd - 1 jan 2018
Evenement44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Duitsland
Duur: 27 jun 201829 jun 2018
https://www.wg2018.b-tu.de/

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11159 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)
Verkorte titelWG2018
LandDuitsland
StadCottbus
Periode27/06/1829/06/18
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'On directed feedback vertex set parameterized by treewidth'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Bonamy, M., Kowalik, Ł., Nederlof, J., Pilipczuk, M., Socała, A., & Wrochna, M. (2018). On directed feedback vertex set parameterized by treewidth. In A. Brandstädt, E. Köhler, & K. Meer (editors), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings (blz. 65-78). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11159 LNCS). Springer. https://doi.org/10.1007/978-3-030-00256-5_6