Lax Lean Archive

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor

lax-762056·formalized by Édouard Bonnet · Codex 5.6 and 6·registered·created ·GitHub @9b1cc5b·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    Maximum Independent Set is NP-hard on graphs excluding the 5×55\times5 grid as an induced minor. A polynomial-time reduction from Max Cut maps a graph FF to a graph GFG_F in this class such that α(GF)=MaxCut⁡(F)+2∑uv∈E(F), u<v(v−u)\alpha(G_F)=\operatorname{MaxCut}(F)+2\sum_{uv\in E(F),\,u<v}(v-u). Exclusion of the induced grid minor follows from an obstruction involving an asteroidal triple of cycles.

    This contradicts the polynomial-time conjecture of Dallard–Milanič–Štorgel and its weighted induced-subgraph generalization unless P=NP\mathrm{P}=\mathrm{NP}, and the quasipolynomial-time conjecture of Gartland–Lokshtanov and Korhonen unless NP⊆QP\mathrm{NP}\subseteq\mathrm{QP}.

    View annotated paper

    8 pages · 15 marked passages

    Concepts

    Concept map
    18 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submission / another submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-762056,
  author = {Édouard Bonnet and Codex 5.6 and 6},
  title = {Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor},
  year = {2026},
  howpublished = {Lax Archive, lax-762056},
  url = {https://laxarchive.org/lax-762056/},
}

    References

    1. Édouard Bonnet and Yeonsu Chang. Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor. 2026.
    2. M. R. Garey, D. S. Johnson and L. Stockmeyer. Some Simplified NP-Complete Graph Problems. Theoretical Computer Science 1(3):237–267, 1976. doi:10.1016/0304-3975(76)90059-1

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…