An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

Abstract

A cactus is a connected graph that does not contain $K_4-e$ as a minor. Given a graph $G=(V,E)$ and integer $k\ge 0$, Cactus Vertex Deletion (also known as Diamond Hitting Set) is the problem of deciding whether $G$ has a vertex set of size at most $k$ whose removal leaves a forest of cacti. The current best deterministic parameterized algorithm for this problem was due to Bonnet et al. [WG 2016], which runs in time $26^k{n}^{O(1)}$, where $n$ is the number of vertices of $G$. In this paper, we design a deterministic algorithm for Cactus Vertex Deletion, which runs in time $17.64^k{n}^{O(1)}$. As a straightforward application of our algorithm, we give a $17.64^k{n}^{O(1)}$-time algorithm for Even Cycle Transversal. The idea behind this improvement is to apply the measure and conquer analysis with a slightly elaborate measure of instances.

11 pages, 1 figure