LordVoIdebug's blog

By LordVoIdebug, history, 5 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it