ACM Transactions on Algorithms· 2026Q1
Max Weight Independent Set in sparse graphs with no long claws
- 1citations
- Q1SCImago
- 2026year
Short summary
A polynomial-time algorithm is presented for the Max Weight Independent Set (MWIS) problem in graphs that exclude specific structures: a fixed forest of paths and subdivided claws as an induced subgraph, and a fixed biclique as a subgraph.
AI-generated from the title and abstract; the full text is not read.
Abstract
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 the Max Weight Independent Set problem ( MWIS ) remains NP -hard in \(H\) -free graphs, unless every component of \(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. In this paper we make an important step towards solving the problem by providing a polynomial-time algorithm for MWIS in graphs excluding a fixed graph forest of paths and subdivided claws as an induced subgraph, and a fixed biclique as a subgraph.
The authors' abstract, as published at the source. ACM Transactions on Algorithms, 2026 · DOI ↗
The rest is in the Pofolia app
Takeaways, key points and questions to the paper; new summaries every day for your field. Free.
Sign in on the web to openField: Computational Theory and Mathematics
Computational Theory and MathematicsComputer Science