Tell me more ×
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.
up vote 2 down vote favorite

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|improve this 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
2  
Seems this belongs on CS.StackExchange not SO, not CSTheory – Saeed Nov 12 '12 at 14:15
3  
@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
show 1 more comment

migrated from stackoverflow.com Nov 12 '12 at 14:06

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

Questions on Theoretical Computer Science Stack Exchange are expected to relate to theoretical computer science within the scope defined in the FAQ. 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 closed questions here.

Browse other questions tagged or ask your own question.