2026-08-17T23:50:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9114 2024-03-06T10:43:24Z ddc:004 open_access

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS Lokshtanov, Daniel Ramanujan, M. S. Saurabh, Saket Sharma, Roohani Zehavi, Meirav Polynomial Kernel Directed Feedback Vertex Set Treewidth Modulator In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F=D-S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-eta modulator, for any positive integer eta. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-eta DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D-S is a DAG and the treewidth of D-S is at most eta. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh and Roohani Sharma and Meirav Zehavi 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.110 urn:nbn:de:0030-drops-91146 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.110 eng https://creativecommons.org/licenses/by/3.0/legalcode