Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a graph G(V,E) and a vertex v, how do i find all the vertices that are reachable via simple paths ( no vertex on the path repeats) of length exactly k.

Powers of adjacency matrix gives the number of paths between vertices but it includes non simple paths.

Is this problem solvable in polynomial time ? If not are there any known approximation algorithms. Any pointers to literature would be great.

share|cite|improve this question

migrated from Nov 12 '12 at 14:06

This question came from our site for professional and enthusiast programmers.

closed as off topic by Kaveh Nov 12 '12 at 18:46

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Is it possible to move the question between different stack sites ? I may not have enough reputation to do this. – Graddy Nov 12 '12 at 0:40
Somebody can do it, but as far as I can tell, I don't have enough reputation to do it either. :-/ – Jamey Sharp Nov 12 '12 at 0:41
assume you have a triangle formed by v, A, and B. With k=2, are both A and B what you are looking for? – Gevorg Nov 12 '12 at 2:27
Seems this belongs on CS.StackExchange not SO, not CSTheory – Saeed Nov 12 '12 at 14:15
@Lamine, he doesn't look for shortest path, so BFS is wrong, and this is NPC problem. just set K to n-1, it's as hard as Hamiltonian path problem. – Saeed Nov 12 '12 at 16:34