An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
share
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 ≥ 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^kn^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^kn^O(1). As a straightforward application of our algorithm, we give a 17.64^kn^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.
READ FULL TEXT