Back to Search
Start Over
Quick but Odd Growth of Cacti.
- Source :
-
Algorithmica . Sep2017, Vol. 79 Issue 1, p271-290. 20p. - Publication Year :
- 2017
-
Abstract
- Let $${\mathcal {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 $${\mathcal {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 $${\mathcal {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 $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ , the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time $$12^k n^{\mathcal {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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH theory
*GEOMETRIC vertices
*ALGORITHMS
*INTEGERS
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 79
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 124177006
- Full Text :
- https://doi.org/10.1007/s00453-017-0317-1