Steiner Tree complexity dichotomy for 1-colorful minor-closed classes
Steiner Tree complexity dichotomy for 1-colorful minor-closed classes
Let be a -colorful minor-closed class, meaning a class of -colorful graphs closed under taking colorful minors. A -colorful rainbow -grid is the specified -colorful rainbow grid of side length in the source. Steiner Tree complexity dichotomy conjecture. Unless , \textsc{Steiner Tree} can be solved in polynomial time in if and only if there is some such that excludes the -colorful rainbow -grid as a colorful minor.
This conjecture proposes a sharp polynomial-time tractability dichotomy for \textsc{Steiner Tree} on -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.