A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph

Authors:
  • VDVida Dujmović
    Vida Dujmović
  • DHDaniel J. Harvey
    Daniel J. Harvey
  • GJGwenaël Joret
    Gwenaël Joret
  • BRBruce Reed
    Bruce Reed

Abstract
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}$.

This publication has 10 references indexed in Scilit: