Quick but Odd Growth of Cacti

Abstract

Let F be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, 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 the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by C and C_odd, the families of forests of cacti and forests of odd cacti, 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 worst case run time 12knO(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.