  A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained
from $G$ by vertex deletions and edge contractions. The class of
$H$-induced-minor-free graphs generalizes the class of $H$-minor-free graphs,
but unlike $H$-minor-free graphs, it can contain dense graphs. We show that if
an $n$-vertex $m$-edge graph $G$ does not contain a graph $H$ as an induced
minor, then it has a balanced vertex separator of size $O_{H}(\sqrt{m})$, where
the $O_{H}(\cdot)$-notation hides factors depending on $H$. More precisely, our
upper bound for the size of the balanced separator is $O(\min(|V(H)|^2, \log n)
\cdot \sqrt{|V(H)|+|E(H)|} \cdot \sqrt{m})$. We give an algorithm for finding
either an induced minor model of $H$ in $G$ or such a separator in randomized
polynomial-time. We apply this to obtain subexponential $2^{O_{H}(n^{2/3} \log
n)}$ time algorithms on $H$-induced-minor-free graphs for a large class of
problems including maximum independent set, minimum feedback vertex set,
3-coloring, and planarization.
  For graphs $H$ where every edge is incident to a vertex of degree at most 2,
our results imply a $2^{O_{H}(n^{2/3} \log n)}$ time algorithm for testing if
$G$ contains $H$ as an induced minor. Our second main result is that there
exists a fixed tree $T$, so that there is no $2^{o(n/\log^3 n)}$ time algorithm
for testing if a given $n$-vertex graph contains $T$ as an induced minor unless
the Exponential Time Hypothesis (ETH) fails. Our reduction also gives
NP-hardness, which solves an open problem asked by Fellows, Kratochv\'il,
Middendorf, and Pfeiffer [Algorithmica, 1995], who asked if there exists a
fixed planar graph $H$ so that testing for $H$ as an induced minor is NP-hard.
