Exact algorithms for restricted subset feedback vertex set in chordal and split graphs

被引:0
作者
Bai, Tian [1 ]
Xiao, Mingyu [1 ]
机构
[1] Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Chengdu, Peoples R China
基金
中国国家自然科学基金;
关键词
Subset feedback vertex set; Chordal graphs; Split graphs; Exact exponential algorithms; Parameterized algorithms;
D O I
10.1016/j.tcs.2023.114326
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The RESTRICTED SUBSET FEEDBACK VERTEX SET problem (R-SFVS) takes a graph G = (V, E), a terminal set T C V, an integer k as the input. The task is to determine whether there exists a subset S C V ⧵ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal , split graphs can be solved in 0(1.1550|V|) time and exponential space or in 0(1.1605|V|) time and polynomial space, significantly improving all previous results. As a by-product, we show that the MAXIMUM INDEPENDENT SET problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to VERTEX COVER, we obtain an 0*(1.2738k)-time parameterized algorithm and a tight 0(k2)-kernel for R-SFVS in chordal and split graphs.
引用
收藏
页数:13
相关论文
共 30 条
  • [1] Buneman P., 1974, Discrete Mathematics, V9, P205, DOI 10.1016/0012-365X(74)90002-8
  • [2] Improved upper bounds for vertex cover
    Chen, Jianer
    Kanj, Iyad A.
    Xia, Ge
    [J]. THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) : 3736 - 3756
  • [3] Faster exact algorithms for some terminal set problems
    Chitnis, Rajesh
    Fomin, Fedor V.
    Lokshtanov, Daniel
    Misra, Pranabendu
    Ramanujan, M. S.
    Saurabh, Saket
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 88 : 195 - 207
  • [4] Dehne R, 2004, LECT NOTES COMPUT SC, V3162, P271
  • [5] Dell H, 2010, ACM S THEORY COMPUT, P251
  • [6] DIRAC A., 1961, Abh. Math. Sem. Univ. Hamburg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]
  • [7] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .2. ON COMPLETENESS FOR W[1]
    DOWNEY, RG
    FELLOWS, MR
    [J]. THEORETICAL COMPUTER SCIENCE, 1995, 141 (1-2) : 109 - 131
  • [8] REPRESENTATION OF A GRAPH BY SET INTERSECTIONS
    ERDOS, P
    GOODMAN, AW
    POSA, L
    [J]. CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (01): : 106 - &
  • [9] An 8-approximation algorithm for the subset feedback vertex set problem
    Even, G
    Naor, JS
    Zosin, L
    [J]. SIAM JOURNAL ON COMPUTING, 2000, 30 (04) : 1231 - 1252
  • [10] Foldes S., 1977, P 8 SE C COMB GRAPH, P311