# Vertices that are K away [closed]

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.

-

## migrated from stackoverflow.comNov 12 '12 at 14:06

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

## closed as off topic by KavehNov 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