Open: $f(\mathrm{OPT})$-approximation for largest (general) complete minor
Open Problem: polytime $f(\mathrm{OPT})$-approximation for largest complete minor · arXiv:2505.05997
Status open high confidence
The best known polynomial-time approximation for the size of a largest complete minor remains O(\sqrt{n}), due to Alon, Lingas, and Wahlén, with no PTAS unless P=NP (Wahlén). The source paper (arXiv:2505.05997, APPROX-RANDOM 2025) resolves the analogous question for complete interval minors in ordered graphs via a polytime f(t)-approximation (f triply exponential), but the open problem for general complete minors is explicitly cited as unresolved motivation. No follow-up paper resolving the f(OPT)-approximation question for general complete minors was found in the indexed literature.
Reviewer notes. Paper published at APPROX-RANDOM 2025 (LIPIcs vol. 353, article 15). The conjecture is very recent (May 2025); absence of follow-up in web search is consistent with open status. The O(\sqrt{n}) upper bound and no-PTAS lower bound are confirmed from the abstract and search results, but no paper closing the f(OPT)-approximation gap was found.
Context
The best known polynomial-time approximation factor for the size of a largest complete minor is $O(\sqrt{n})$, due to Alon, Lingas and Wahlén [1]. No PTAS exists unless $\mathsf{P}=\mathsf{NP}$ (Wahlén [32]). The authors cite this open problem as direct motivation for studying the analogous question for complete interval minors in ordered graphs, where they obtain a polytime $f(t)$-approximation.
Notes. Stated in the introduction as a known open problem without a labelled environment and without explicit attribution to specific authors; captured because the authors explicitly flag it as open and use it to motivate the paper.
Source paper
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang, Stéphan Thomassé · 2025-05-09
https://arxiv.org/abs/2505.05997