Polynomial-time MIS conjecture for graphs forbidding independent planar minors
Polynomial-time MIS conjecture for graphs forbidding independent planar minors
Let be a planar graph and let be a positive integer. A graph is -free if it contains no pairwise non-adjacent independent -minor models. MIS denotes the Maximum Independent Set problem.
Independent-planar-minor MIS conjecture. For every planar and every , MIS is polynomial-time solvable on the class of -free graphs.
The paper proves an -time algorithm for this problem, so the conjecture asks whether the quasi-polynomial bound can always be improved to polynomial time. It remains open in the -free case.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, Amadeus Reinald and Stéphan Thomassé, “Forbidding anticomplete planar minors: Induced Erdős–Pósa property and Maximum Independent Set in QP”, arXiv:2607.09646 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.