The classical Andr\'{a}sfai-Erd\H{o}s-S\'{o}s Theorem states that for , every -vertex -free graph with minimum degree greater than must be -partite. We establish a simple criterion for -graphs, , 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 -graph , we present a simple algorithm to decide the -freeness of an -vertex -graph with minimum degree greater than in time , where is a constant. In particular, for the complete graph , we can take . Based on a result by Chen-Huang-Kanj-Xia, we show that for every fixed , this problem cannot be solved in time if we replace with unless ETH fails. Furthermore, we establish an algorithm to decide the -freeness of an -vertex graph with edges in time for and , partially improving upon the recently provided running time of by Fomin--Golovach--Sagunov--Simonov. Moreover, we show that for every fixed , this problem cannot be solved in time if is of order unless ETH fails. As an intermediate step, we show that for a specific class of -graphs , the (surjective) -coloring problem can be solved in time , provided the input -graph has vertices and a large minimum degree, refining several previous results.