Is it possible to check, whether graph contains K_5 as a sub-graph in linear time? (There obviously exists an algorithm to check whether graph contains K_5 OR K_3_3, but what about K_5 only?).
A more general question, is it possible to check whether graph G(V, E), contains some other sub-graph G2(V2, E2) in a way, that will be linear depending on E (or at least polynomial) (probably exponential or even worse depending depending on E2) (e. g. wрether there is an algorithm that solves this problem in something like O((E ^ k) * A(E2, E2)) for fixed k?