LordVoIdebug's blog

By LordVoIdebug, history, 5 years ago,

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?

• +5

 » 5 years ago, # |   0 I don't think so. The k-Clique problem is W[1] — hard. That means that there's a very high chance it doesn't admit an FPT algorithm. An FPT algorithm gives the running time of $O(n^{c}*f(k))$ where $c$ is a constant, $n$ is the size of the original graph $G$ and $k$ is the size of the clique you want to find in $G$.
 » 5 years ago, # |   0 What do you mean by „containing”? I can understand is as „there are five vertices in G and every two of them are connected with edge” or „there is a subgraph isomorphic with clique of 5 vertices”.
 » 5 years ago, # |   +21 There obviously exists an algorithm to check whether graph contains K_5 OR K_3_3 You are misunderstanding between subgraph and minor graph. The theorem about planer graph is for graph minor, not subgraph. So, linear-time algorithm for planarity cannot be used.By the way, I don't think such an algorithm exists, as Mindjolt pointed out (but still a bit ambiguous). We have no linear-time algorithm even for triangle detection.