-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$

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.

  • 5
    $\begingroup$ It's not clear to me that this question is even in scope from a 'research-level' perspective. $\endgroup$ – Suresh Venkat Nov 12 '11 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 '11 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 '11 at 17:12
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$
  • 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 '11 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$ – Radu GRIGore Nov 12 '11 at 20:14

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