ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let HH be a planar graph and let kk be a positive integer. A graph is kHkH-free if it contains no kk pairwise non-adjacent independent HH-minor models. MIS denotes the Maximum Independent Set problem.

Independent-planar-minor MIS conjecture. For every planar HH and every kk, MIS is polynomial-time solvable on the class of kHkH-free graphs.

The paper proves an nO(log⁡n)n^{O(\log n)}-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 2K32K_3-free case.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.