Max Weight Independent Set in Sparse Graphs with No Long Claws

被引：0
|
作者：
Abrishami, Tara [1 ]
Chudnovsky, Maria [2 ]
Pilipczuk, Marcin [3 ]
Rzazewski, Pawel [3 ,4 ]
机构：
[1] Univ Hamburg, Dept Math, Hamburg, Germany
[2] Princeton Univ, Princeton, NJ 08544 USA
[3] Univ Warsaw, Fac Math Informat & Mech, Inst Informat, Warsaw, Poland
[4] Warsaw Univ Technol, Fac Math & Informat Sci, Warsaw, Poland
来源：
41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024 | 2024年 / 289卷
基金：
欧洲研究理事会; 英国工程与自然科学研究理事会; 美国国家科学基金会;
关键词：
Max Weight Independent Set; subdivided claw; hereditary classes; P-T-FREE; MAXIMUM WEIGHT; STABLE SETS; POLYNOMIAL ALGORITHM; TIME ALGORITHM; SUBCLASSES; (P-6; HARD;
D O I：
10.4230/LIPIcs.STACS.2024.4
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We revisit the recent polynomial-time algorithm for the Max Weight Independent Set ( MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzazewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n(O(Delta 2)), where n is the number of vertices of the instance and Delta is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.
引用
收藏
页数：15
相关论文
共 32 条
  • [21] Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
    Eto, Hiroshi
    Ito, Takehiro
    Liu, Zhilong
    Miyano, Eiji
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 2017, 10167 : 228 - 240
  • [22] Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs
    Wiese, Andreas
    Kranakis, Evangelos
    AD HOC & SENSOR WIRELESS NETWORKS, 2009, 7 (3-4) : 273 - 293
  • [23] Maximum Weight Independent Sets in hole- and co-chair-free graphs
    Brandstaedt, Andreas
    Giakoumakis, Vassilis
    INFORMATION PROCESSING LETTERS, 2012, 112 (03) : 67 - 71
  • [24] A subexponential-time algorithm for the Maximum Independent Set Problem in Pt-free graphs
    Brause, Christoph
    DISCRETE APPLIED MATHEMATICS, 2017, 231 : 113 - 118
  • [25] Maximum weight independent sets in (P6, co-banner)-free graphs
    Mosca, Raffaele
    INFORMATION PROCESSING LETTERS, 2013, 113 (03) : 89 - 93
  • [26] Maximum Weight Independent Sets for (P7,triangle)-free graphs in polynomial time
    Brandstaedt, Andreas
    Mosca, Raffaele
    DISCRETE APPLIED MATHEMATICS, 2018, 236 : 57 - 65
  • [27] A polynomial algorithm for minimum-weight feedback vertex set problem in series-parallel graphs
    Zhang, SQ
    Li, GJ
    6TH WORLD MULTICONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL X, PROCEEDINGS: MOBILE/WIRELESS COMPUTING AND COMMUNICATION SYSTEMS II, 2002, : 72 - 77
  • [28] Maximum weight stable set in (P7, bull)-free graphs and (S1,2,3, bull)-free graphs
    Maffray, Frederic
    Pastor, Lucas
    DISCRETE MATHEMATICS, 2018, 341 (05) : 1449 - 1458
  • [29] Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs
    Bacso, Gabor
    Lokshtanov, Daniel
    Marx, Daniel
    Pilipczuk, Marcin
    Tuza, Zsolt
    van Leeuwen, Erik Jan
    ALGORITHMICA, 2019, 81 (02) : 421 - 438
  • [30] Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Rzazewski, Pawel
    2021 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX, 2021, : 204 - +
1234