License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.258
URN: urn:nbn:de:0030-drops-55883
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5588/
Go to the corresponding LIPIcs Volume Portal

Kolay, Sudeshna ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket

Quick but Odd Growth of Cacti

pdf-format:
25.pdf (0.5 MB)

Abstract

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.

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 =	{258--269},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5588},
  URN =		{urn:nbn:de:0030-drops-55883},
  doi =		{10.4230/LIPIcs.IPEC.2015.258},
  annote =	{Keywords: Even Cycle Transversal, Diamond Hitting Set, Randomized Algorithms}
}

Keywords: Even Cycle Transversal, Diamond Hitting Set, Randomized Algorithms
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI