MWIS QPTAS in subdivision-of-forest-free graphs

Conjecture 1.3 · arXiv:1907.04585

arXiv Conjecture high confidence— first stated 2023-11-14

Authors: Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé

Status open high confidence

Conjecture 1.3 — that MWIS admits a QPTAS and a subexponential-time algorithm in graphs excluding any subdivision of a forest H of maximum degree at most three as an induced subgraph — remains open in full generality. The source paper itself proves the special case where H has at most three vertices of degree three. A 2024 STACS paper (Gartland et al.) extends polynomial-time tractability to sparse graphs (excluding a fixed biclique) with no long subdivided claws, which is a more restrictive setting and does not subsume the conjecture. A 2026 preprint (arXiv:2602.18317) extends QPTAS results to graphs with few independent long induced holes, a structurally different class. No verified follow-up fully resolves the conjecture.

Reviewer notes. No follow-up paper fully resolving Conjecture 1.3 was found across 7 web calls (4 searches + 3 fetches). The related 2024 STACS paper (Max Weight Independent Set in Sparse Graphs with No Long Claws, LIPIcs STACS 2024:4) achieves polynomial-time results only in the additional presence of biclique-freeness, which is a different and more restrictive setting. The 2026 preprint arXiv:2602.18317 (Bonnet, Czyzewska, Masarik, M. Pilipczuk, Rzazewski) handles graphs with few independent long holes via induced-minor exclusion, not subdivision-of-forest exclusion. The conjecture is recent (effective publication 2023) and the absence of a resolution is consistent with the high difficulty of the problem.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every forest $H$ of maximum degree at most three, MWIS admits a QPTAS and a subexponential-time algorithm in the class of graphs that do not contain any subdivision of $H$ as an induced subgraph.

Context

Following Theorems 1.1 and 1.2, which establish QPTASes and subexponential-time algorithms for MWIS in $H$-free graphs where every component of $H$ is a path or a subdivided claw, the authors conjecture a broader generalization to all forests of maximum degree at most three and graphs excluding any subdivision of $H$ as an induced subgraph. The paper itself proves Conjecture 1.3 for $H$ being a forest with at most three vertices of degree three (with a $2^{O(|V(G)|^{40/41}\log|V(G)|)}$ subexponential bound), but the full generality remains open.

Source paper

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé · 2023-11-14
https://arxiv.org/abs/1907.04585 PDF source