I was reading NP complete theory just thought. "Is there any path of length k in given graph" Is it polynomial time algorithm?
Is the graph directed or undirected? Can the path go through the same vertex more than once? The same edge? (Note that if the graph is undirected and the path can go through the same edge more than once, then the problem becomes very easy).
For the directed case: If k is constant, or at most logarithmic, there is an efficient algorithm: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377 (This algorithm uses the observation that the problem can be solved in linear time using dynamic programming when the graph is directed and acyclic)
For the simple path case: k=n is a special case of the Hamiltonian path problem