An improved deterministic parameterized algorithm for cactus vertex deletion

DOI10.1007/S00224-022-10076-XMaRDI QIDQ2135634zbMATH OpenOpenAlexFDO

Authors Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi

Publication date 9 May 2022

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.04910

zbMATH Keywords

fixed-parameter tractablecactus vertex deletioneven cycle transversalmeasure and conquer analysis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Connectivity (05C40)

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 $kge0$, 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.

Recommendations

• scientific article; zbMATH DE number 6784975
• Quick but odd growth of cacti
• Parameterized algorithms for even cycle transversal
• Faster parameterized algorithm for cluster vertex deletion
• Chordal deletion is fixed-parameter tractable

Cites work

• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• A faster parameterized algorithm for pseudoforest deletion
• A measure \& conquer approach for the analysis of exact algorithms
• A parameterized algorithm for bounded-degree vertex deletion
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Exact exponential algorithms.
• Finding odd cycle transversals.
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Hitting diamonds and growing cacti
• Hitting forbidden minors: approximation and kernelization
• Improved FPT Algorithms for Deletion to Forest-Like Structures.
• Improved analysis of highest-degree branching for feedback vertex set
• Improved upper bounds for vertex cover
• Parameterized algorithms for even cycle transversal
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• Quick but odd growth of cacti
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Cited in

(7)

• Quick but odd growth of cacti
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Faster parameterized algorithm for pumpkin vertex deletion set
• Faster deterministic algorithm for cactus vertex deletion
• Obtaining approximately optimal and diverse solutions via dispersion
• Faster parameterized algorithm for r-pseudoforest deletion

This page was built for publication: An improved deterministic parameterized algorithm for cactus vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2135634)