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