Kolay, Sudeshna ;
Lokshtanov, Daniel ;
Panolan, Fahad ;
Saurabh, Saket
Quick but Odd Growth of Cacti
Abstract
Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a ksized 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 oddcactus 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.
BibTeX  Entry
@InProceedings{kolay_et_al:LIPIcs:2015:5588,
author = {Sudeshna Kolay and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh},
title = {{Quick but Odd Growth of Cacti}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {258269},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5588},
URN = {urn:nbn:de:0030drops55883},
doi = {10.4230/LIPIcs.IPEC.2015.258},
annote = {Keywords: Even Cycle Transversal, Diamond Hitting Set, Randomized Algorithms}
}
2015
Keywords: 

Even Cycle Transversal, Diamond Hitting Set, Randomized Algorithms 
Seminar: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Issue date: 

2015 
Date of publication: 

2015 