Quick but odd growth of cacti
Peer reviewed, Journal article
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/1956/12024/25.pdf.jpg?sequence=7&isAllowed=y)
View/ Open
Date
2015Metadata
Show full item recordCollections
Original version
Leibniz International Proceedings in Informatics 2015, 43:258-269 https://doi.org/10.4230/lipics.ipec.2015.258Abstract
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.