2026-08-17T07:55:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5588 2024-03-06T10:36:36Z ddc:004 open_access

Quick but Odd Growth of Cacti Kolay, Sudeshna Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Even Cycle Transversal Diamond Hitting Set Randomized Algorithms Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a k-sized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when F is either a family of cactus graphs or a family of odd-cactus graphs. A graph H is called a cactus graph if every pair of cycles in H intersect on at most one vertex. Furthermore, a cactus graph H is called an odd cactus, if every cycle of H is of odd length. Let us denote by C and C_{odd}, families of cactus and odd cactus, respectively. The vertex deletion problems corresponding to C and C_{odd} are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with running time 12^{k}*n^{O(1)} for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sudeshna Kolay and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.258 urn:nbn:de:0030-drops-55883 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.258 eng https://creativecommons.org/licenses/by/3.0/legalcode