NP-hard graph problem.

Revision en2, by LordVoIdebug, 2019-07-02 03:55:38

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?


  Rev. Lang. By When Δ Comment
en2 English LordVoIdebug 2019-07-02 03:55:38 137
en1 English LordVoIdebug 2019-07-02 03:52:48 466 Initial revision (published)