Header menu link for other important links
X
Quick but odd growth of cacti
S. Kolay, D. Lokshtanov, , S. Saurabh
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2015
Volume: 43
   
Pages: 258 - 269
Abstract
Let F be a family of graphs. Given an input graph G and a positive integer κ, testing whether G has a κ-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 Codd, families of cactus and odd cactus, respectively. The vertex deletion problems corresponding to C and Codd are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with running time 12κnO(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. © Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh;.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969