An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

2020/12/09 by Yuuki Aoike, Aoike, Yuuki, Tatsuya Gima +13 · 1 citation
Agricultural and Biological Sciences · #Banana Cultivation and Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2012.04910

openalex publication_date 2020/12/09 · openalex created_date 2021/05/24 · openalex updated_date 2026/07/28

Abstract

A cactus is a connected graph that does not contain K₄ - 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.

Cited by

• Kernelization dichotomies for hitting minors under structural parameterizations

Related

• Cactus Representation of Minimum Cuts: Derandomize and Speed up
• Cactus Graphs and Some Algorithms
• Faster parameterized algorithm for Cluster Vertex Deletion
• Vertex Deletion Parameterized by Elimination Distance and Even Less
• Compact Cactus Representations of all Non-Trivial Min-Cuts