<p>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). </p>

<p>For the directed case:
If k is constant, or at most logarithmic, there is an efficient algorithm:
<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3377</a>
(This algorithm uses the observation that the problem can be solved in linear time using dynamic programming when the graph is directed and acyclic)</p>

<p>For the simple path case:
k=n is a special case of the Hamiltonian path problem</p>

CC BY-SA 3.0
2011-11-12T19:58:37.553Z
it is well accepted fact that path means 'simple path' so u can't visit one vertex or one edge twice..more formally,given unweighted undirected graph is it polynomial time algorithm to find path of length k in given graph?
user997704
CC BY-SA 3.0
2011-11-12T20:14:11.730Z
@user997704: It's now clear from your comment what you wanted to ask in the first place, but it's not clear that you noticed that Dana Moshkovitz already answered (last sentence).
Radu GRIGore
CC BY-SA 3.0
2011-11-12T19:31:50.093Z
2011-11-12T19:31:50.093Z
Dana Moshkovitz
<p>I was reading NP complete theory just thought.
"Is there any path of length k in given graph"
Is it polynomial time algorithm? </p>

CC BY-SA 3.0
2011-11-12T21:20:17.683Z
It's not clear to me that this question is even in scope from a 'research-level' perspective.
Suresh Venkat
CC BY-SA 3.0
2011-11-13T12:48:16.753Z
If this is not reserach level then what is research level??No one has come up with poly time algo..
user997704
CC BY-SA 3.0
2011-11-13T17:12:54.760Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
<ds.algorithms><graph-algorithms>
Path of length k in graph
user997704
# Path of length k in graph

(Asked by: username_0 on 2011-11-12)

I was reading NP complete theory just thought.
"Is there any path of length k in given graph"
Is it polynomial time algorithm?

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: It's not clear to me that this question is even in scope from a 'research-level' perspective.  
> **username_0**: If this is not reserach level then what is research level??No one has come up with poly time algo..  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  

---

## 1 answers

### Answer by username_3 on 2011-11-12. Score: 4

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

> **Comments:**
> **username_0**: it is well accepted fact that path means 'simple path' so u can't visit one vertex or one edge twice..more formally,given unweighted undirected graph is it polynomial time algorithm to find path of length k in given graph?  
> **username_4**: @user997704: It's now clear from your comment what you wanted to ask in the first place, but it's not clear that you noticed that Dana Moshkovitz already answered (last sentence).  

---

