Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-15833
For citation please use:
Main Title: A polynomial kernel for funnel arc deletion set
Author(s): Milani, Marcelo Garlet
Type: Article
URI: https://depositonce.tu-berlin.de/handle/11303/17054
http://dx.doi.org/10.14279/depositonce-15833
License: https://creativecommons.org/licenses/by/4.0/
Abstract: In Directed Feedback Arc Set (DFAS) we search for a set of at most k arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider C-Arc Deletion Set (C-ADS), a variant of DFAS where we want to remove at most k arcs from the input digraph in order to turn it into a digraph of a class C. In this work, we choose C to be the class of funnels. Funnel-ADS is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to k. So far no polynomial kernels for this problem were known. Our main result is a kernel for Funnel-ADS with O(k6) many vertices and O(k7) many arcs, computable in O(nm) time, where n is the number of vertices and m the number of arcs in the input digraph.
Subject(s): graph editing
directed feedback arc set
parameterized algorithm
kernels
funnels
Issue Date: 4-Apr-2022
Date Available: 5-Aug-2022
Language Code: en
DDC Class: 510 Mathematik
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2022
Journal Title: Algorithmica
Publisher: Springer Nature
Volume: 84
Publisher DOI: 10.1007/s00453-022-00960-w
Page Start: 2358
Page End: 2378
EISSN: 1432-0541
ISSN: 0178-4617
TU Affiliation(s): Fak. 4 Elektrotechnik und Informatik » Inst. Softwaretechnik und Theoretische Informatik » FG Logik und Semantik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
GarletMilani_Polynomial_2022.pdf
Format: Adobe PDF | Size: 444.78 kB
DownloadShow Preview
Thumbnail

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons