I\'m trying to create an algorithm in polynomial time, that detects wether or no
ID: 647688 • Letter: I
Question
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
Explanation / Answer
When you say "cycle", do you mean a simple cycle of length 40 (so no vertex is allowed to be repeated), or would you allow an arbitrary walk of length 40 that ends where it starts (i.e., vertices are allowed to be repeated in the cycle)? The answer to your question depends on what you mean by cycle, so I'll answer both cases.
Simple cycles
The problem of testing whether a graph contains a simple cycle of length k is hard.
No efficient algorithm is known; all known algorithms have running time that is exponential in k; and if k is part of the input, the problem is NP-hard. See here and here. In your case, k=40. The best algorithms that I know of have either a O(k!) factor or a O(nk/2) factor in the running time, so they will be totally infeasible: O(n20) is not feasible for any non-trivial value of n, and k!?2159?1048, which is also infeasibly large. (See Louis's answer for pointers to an algorithm of the former type.)
If you allow repeated vertices
If you allow the cycle to contain repeated vertices, then the problem becomes much easier, and there is a polynomial-time solution.
Hint: Consider the adjacency matrix of the graph, M. Look at M2. Can you find any relationship between the i,j entry of M2 and paths of some length? Can you generalize?
(Since this looks like a natural exercise problem, I am just giving you a hint, and letting you take it from here.)