I was reading NP complete theory just thought. "Is there any path of length k in given graph" Is it polynomial time algorithm?
closed as not a real question by Jukka Suomela, Mohammad Al-Turkistany, Robin Kothari, Suresh Venkat Nov 13 '11 at 18:11
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.
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