TY - GEN

T1 - Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Dibek, Cemil

AU - Rzążewski, Paweł

N1 - Funding Information:
∗SupportedbyNSFGrantDMS-1763817andNSF-EPSRCGrantDMS-2120644. †SupportedbyNSFGrantDMS-1763817. ‡Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.
Publisher Copyright:
Copyright © 2022 by SIAM Unauthorized reproduction of this article is prohibited.

PY - 2022

Y1 - 2022

N2 - For graphs G and H, we say that G is H-free if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NP-hard in H-free graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in H-free graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomial-time solvable in H-free graphs of bounded degree.

AB - For graphs G and H, we say that G is H-free if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NP-hard in H-free graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in H-free graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomial-time solvable in H-free graphs of bounded degree.

UR - http://www.scopus.com/inward/record.url?scp=85126338524&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126338524&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85126338524

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1448

EP - 1470

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -