I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language.
The language specifies that a graph is only part of this language if it has a cycle on 40 vertices. (The cycle doesn't need to be induced.)
Now, I'm considering the fact that there could be a huge number of vertices within this graph. For example, we could have 100000 vertices, and there could be a cycle of 300, but this would not be in the language. If this graph had a cycle of 300 AND a cycle of 40, then it is.
I'm thinking that depth-first search would be the proper way to approach this question. Then, using this, we'd possibly have check every vertex within the graph?
This is just a guess at the moment though, and help/thoughts would be greatly appreciated.