-6
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ It's not clear to me that this question is even in scope from a 'research-level' perspective. $\endgroup$ Nov 12, 2011 at 21:20
  • $\begingroup$ If this is not reserach level then what is research level??No one has come up with poly time algo.. $\endgroup$
    – user997704
    Nov 13, 2011 at 12:48
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Nov 13, 2011 at 17:12

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – user997704
    Nov 12, 2011 at 19:58
  • 3
    $\begingroup$ @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). $\endgroup$ Nov 12, 2011 at 20:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.