Show simple item record

dc.contributor.authorNeogi, Rian
dc.contributor.authorRamanujan, M.S.
dc.contributor.authorSaurabh, Saket
dc.contributor.authorSharma, Roohani
dc.description.abstractDirected Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the H-SCC Deletion problem. Here, one is given a digraph D, an integer k and the objective is to decide whether there is a vertex set of size at most k whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family H as (not necessarily induced) subgraphs. When H comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if H only contains rooted graphs or if H contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of Göke et al. [CIAC 2019] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Göke et al. [CIAC 2019].en_US
dc.publisherSchloss Dagstuhl – Leibniz Center for Informaticsen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleOn the parameterized complexity of deletion to H-free strong componentsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright the authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2020, 170, 75.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal