Steiner Tree complexity dichotomy for 1-colorful minor-closed classes

Let C\mathcal{C} be a 11-colorful minor-closed class, meaning a class of 11-colorful graphs closed under taking colorful minors. A 11-colorful rainbow (k×k)(k\times k)-grid is the specified 11-colorful rainbow grid of side length kk in the source. Steiner Tree complexity dichotomy conjecture. Unless PNP\mathsf{P}\neq\mathsf{NP}, \textsc{Steiner Tree} can be solved in polynomial time in C\mathcal{C} if and only if there is some kk such that C\mathcal{C} excludes the 11-colorful rainbow (k×k)(k\times k)-grid as a colorful minor.

This conjecture proposes a sharp polynomial-time tractability dichotomy for \textsc{Steiner Tree} on 11-colorful minor-closed classes, refining the bidimensionality-frontier discussion. Its resolution is not given in the supplied text.

Sources & referencesView supporting material

Primary source

Evangelos Protopapas, Dimitrios M. Thilikos and Sebastian Wiederrecht, “Colorful Minors”, arXiv:2507.10467 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.