Classifying Subset Feedback Vertex Set for H-Free Graphs

被引：3
|
作者：
Paesani, Giacomo [1 ]
Paulusma, Daniel [2 ]
Rzazewski, Pawel [3 ,4 ]
机构：
[1] Univ Leeds, Sch Comp, Leeds, England
[2] Univ Durham, Dept Comp Sci, Durham, England
[3] Warsaw Univ Technol, Fac Math & Informat Sci, Warsaw, Poland
[4] Univ Warsaw, Fac Math Informat & Mech, Warsaw, Poland
来源：
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022) | 2022年 / 13453卷
关键词：
Feedback vertex set; H-free graph; Complexity dichotomy;
D O I：
10.1007/978-3-031-15914-5_30
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the WEIGHTED SUBSET FEEDBACK VERTEX SET problem, where each vertex u has weight w(u) > 0 and we ask that S has small weight. By combining known N P-hardness results with new polynomial-time results we prove full complexity dichotomies for SUBSET FEEDBACK VERTEX SET and WEIGHTED SUBSET FEEDBACK VERTEX SET for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.
引用
收藏
页码：412 / 424
页数：13
相关论文
共 50 条
  • [1] Classifying subset feedback vertex set for H-free graphs
    Paesani, Giacomo
    Paulusma, Daniel
    Rzazewski, Pawel
    THEORETICAL COMPUTER SCIENCE, 2024, 1003
  • [2] FEEDBACK VERTEX SET AND EVEN CYCLE TRANSVERSAL FOR H-FREE GRAPHS: FINDING LARGE BLOCK GRAPHS
    Paesani, Giacomo
    Paulusma, Daniel
    Rzazewski, Pawel
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (04) : 2453 - 2472
  • [3] Computing subset transversals in H-free graphs
    Brettell, Nick
    Johnson, Matthew
    Paesani, Giacomo
    Paulusma, Daniel
    THEORETICAL COMPUTER SCIENCE, 2022, 902 : 76 - 92
  • [4] Vertex Cover at Distance on H-Free Graphs
    Dallard, Clement
    Krbezlija, Mirza
    Milanic, Martin
    COMBINATORIAL ALGORITHMS, IWOCA 2021, 2021, 12757 : 237 - 251
  • [5] Computing Weighted Subset Odd Cycle Transversals in H-free graphs
    Brettell, Nick
    Johnson, Matthew
    Paulusma, Daniel
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2022, 128 : 71 - 85
  • [6] Computing Weighted Subset Transversals in H-Free Graphs
    Brettell, Nick
    Johnson, Matthew
    Paulusma, Daniel
    ALGORITHMS AND DATA STRUCTURES, WADS 2021, 2021, 12808 : 229 - 242
  • [7] Feedback vertex set on AT-free graphs
    Kratsch, Dieter
    Mueller, Haiko
    Todinca, Ioan
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (10) : 1936 - 1947
  • [8] Classifying k-edge colouring for H-free graphs
    Galby, Esther
    Lima, Paloma T.
    Paulusma, Daniel
    Ries, Bernard
    INFORMATION PROCESSING LETTERS, 2019, 146 : 39 - 43
  • [9] Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
    Le, Hoang-Oanh
    Le, Van Bang
    THEORY OF COMPUTING SYSTEMS, 2024, 68 (02) : 250 - 270
  • [10] Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
    Hoang-Oanh Le
    Van Bang Le
    Theory of Computing Systems, 2024, 68 : 250 - 270
12345