A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
Vida Dujmović, Daniel J. Harvey, Gwenaël Joret, Bruce A. Reed, David R. Wood · SIAM Journal on Discrete Mathematics · 2013
Let $g(t)$ be the minimum number such that every graph $G$ with average degree $d(G) \geq g(t)$ contains a $K_{t}$-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that $g(t) \in \Theta(t\sqrt{\log t})$. This paper shows that for all fixed $\epsilon > 0$ and fixed sufficiently large $t \geq t(\epsilon)$, if $d(G) \geq (2+\epsilon)g(t)$, then we can find this $K_{t}$-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when $d(G) \geq 2^{t-2}$.