An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

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

研究成果: ジャーナルへの寄稿学術誌査読

3 被引用数 (Scopus)


A cactus is a connected graph that does not contain K4 − e as a minor. Given a graph G = (V,E) and an 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 previously best deterministic parameterized algorithm for this problem was due to Bonnet et al. [WG 2016], which runs in time 26knO(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.64knO(1). As an almost straightforward application of our algorithm, we also give a deterministic 17.64knO(1)-time algorithm for Even Cycle Transversal, which improves the previous running time 50knO(1) of the known deterministic parameterized algorithm due to Misra et al. [WG 2012].

ジャーナルTheory of Computing Systems
出版ステータス出版済み - 4月 2022

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • 計算理論と計算数学


「An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。