Vertices that are K away

Question

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.

Answer 1

I'm answering only the first question: "is it solvable in polynomial time?".

Suppose it is solvable in polynomial time. Then solve it for k=|V|-1 and pick any resulting vertex. Remove this vertex and solve this problem for k=|V|-2. Resulting set of vertices should contain at least one vertex that was connected to the last removed vertex. Remove this vertex and continue process for k=|V|-i until single starting vertex remains. You've just found a Hamiltonian path for the original graph with polynomial time algorithm.

Since Hamiltonian path problem is NP-complete, the problem in OP is also very unlikely to be solvable in polynomial time.