In its most basic form, the subgraph isomorphism problem asks if a given graph \(G\)  on \(m\)  edges contains a fixed size pattern \(H\)  as a (not necessarily induced) subgraph.
It is natural to conjecture that the subgraph isomorphism problem can be solved in \(m^{1+o(1)}\)  time if and only if \(H\)  is acyclic.
A linear time algorithm for forests follows from the Color-Coding technique [1]}, and this paper proves that all cycles require super-linear time (assuming the hardness of triangles).
Thus, all we have to do is reduce \(k\) -cycle detection to the detection of any pattern that contains a \(k\) -cycle.
Such a reduction is known for odd \(k\)  [2]} but not for even.
