Faster parameterized algorithm for r-pseudoforest deletion

被引：0
作者：
Tsur, Dekel [1 ]
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel
来源：
THEORETICAL COMPUTER SCIENCE | 2025年 / 1028卷
关键词：
Graph algorithms; Parameterized complexity; Branching algorithms;
D O I：
10.1016/j.tcs.2024.115034
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In the r-PSEUDOFOREST DELETION problem, the input is a graph G and integers k, r, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph in which every connected component can be made into a tree by deleting at most redges. In this paper we give an O<^> * ((8r + 1) <^> k) time algorithm for r-PSEUDOFOREST DELETION for every r >= 1.
引用
收藏
页数：4
相关论文
共 15 条
  • [1] An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
    Aoike, Yuuki
    Gima, Tatsuya
    Hanaka, Tesshu
    Kiyomi, Masashi
    Kobayashi, Yasuaki
    Kobayashi, Yusuke
    Kurita, Kazuhiro
    Otachi, Yota
    [J]. THEORY OF COMPUTING SYSTEMS, 2022, 66 (02) : 502 - 515
  • [2] A faster parameterized algorithm for PSEUDOFOREST DELETION
    Bodlaender, Hans L.
    Ono, Hirotaka
    Otachi, Yota
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 236 : 42 - 56
  • [3] Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
    Bonnet, Edouard
    Brettell, Nick
    Kwon, O-joung
    Marx, Daniel
    [J]. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, 2016, 9941 : 233 - 244
  • [4] Cygan Marek, 2015, Parameterized Algorithms, V1st
  • [5] Gowda K.N., 2020, P 31 INT S ALG COMP
  • [6] Iwatate Yasuya, 2021, Annual Report of the Society of Plant Protection of North Japan, P1, DOI 10.11455/kitanihon.2021.72_1
  • [7] Quick but Odd Growth of Cacti
    Kolay, Sudeshna
    Lokshtanov, Daniel
    Panolan, Fahad
    Saurabh, Saket
    [J]. ALGORITHMICA, 2017, 79 (01) : 271 - 290
  • [8] Li J, 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), P971
  • [9] An improved FPT algorithm for Almost Forest Deletion problem
    Lin, Mugang
    Feng, Qilong
    Wang, Jianxin
    Chen, Jianer
    Fu, Bin
    Li, Wenjun
    [J]. INFORMATION PROCESSING LETTERS, 2018, 136 : 30 - 36
  • [10] GENERALIZED PSEUDOFOREST DELETION: ALGORITHMS AND UNIFORM KERNEL
    Philip, Geevarghese
    Rai, Ashutosh
    Saurabh, Saket
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 882 - 901
12