  The classical Andr\'{a}sfai-Erd\H{o}s-S\'{o}s Theorem states that for
$\ell\ge 2$, every $n$-vertex $K_{\ell+1}$-free graph with minimum degree
greater than $\frac{3\ell-4}{3\ell-1}n$ must be $\ell$-partite. We establish a
simple criterion for $r$-graphs, $r \geq 2$, to exhibit an
Andr\'{a}sfai-Erd\H{o}s-S\'{o}s-type property (AES), leading to a
classification of most previously studied hypergraph families with this
property.
  For every AES $r$-graph $F$, we present a simple algorithm to decide the
$F$-freeness of an $n$-vertex $r$-graph with minimum degree greater than
$(\pi(F) - \varepsilon_F)\binom{n}{r-1}$ in time $O(n^r)$, where $\varepsilon_F
>0$ is a constant. In particular, for the complete graph $K_{\ell+1}$, we can
take $\varepsilon_{K_{\ell+1}} = (3\ell^2-\ell)^{-1}$. Based on a result by
Chen-Huang-Kanj-Xia, we show that for every fixed $C > 0$, this problem cannot
be solved in time $n^{o(\ell)}$ if we replace $\varepsilon_{K_{\ell+1}}$ with
$(C\ell)^{-1}$ unless ETH fails. Furthermore, we establish an algorithm to
decide the $K_{\ell+1}$-freeness of an $n$-vertex graph with
$\mathrm{ex}(n,K_{\ell+1})-k$ edges in time $(\ell+1)n^2$ for $k \le n/30\ell$
and $\ell \le \sqrt{n/6}$, partially improving upon the recently provided
running time of $2.49^k n^{O(1)}$ by Fomin--Golovach--Sagunov--Simonov.
Moreover, we show that for every fixed $\delta > 0$, this problem cannot be
solved in time $n^{o(\ell)}$ if $k$ is of order $n^{1+\delta}$ unless ETH
fails.
  As an intermediate step, we show that for a specific class of $r$-graphs $F$,
the (surjective) $F$-coloring problem can be solved in time $O(n^r)$, provided
the input $r$-graph has $n$ vertices and a large minimum degree, refining
several previous results.
