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

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

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

CC BY-SA 3.0
2012-11-12T00:40:32.670Z
Is it possible to move the question between different stack sites ? I may not have enough reputation to do this.
Graddy
CC BY-SA 3.0
2012-11-12T02:27:35.447Z
assume you have a triangle formed by v, A, and B. With k=2, are both A and B what you are looking for?
Marsellus Wallace
CC BY-SA 3.0
2012-11-12T14:15:32.393Z
Seems this belongs on CS.StackExchange not SO, not CSTheory
Saeed
CC BY-SA 3.0
2012-11-12T14:19:37.890Z
A classical breadth-first search algorithm of depth $k$ doesn't make it?
Lamine
CC BY-SA 3.0
2012-11-12T16:34:50.277Z
@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
<graph-algorithms>
Vertices that are K away
Graddy
# Vertices that are K away

(Asked by: username_0 on 2012-11-12)

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.

**Tags:** graph-algorithms
> **Comments:**
> **username_0**: Is it possible to move the question between different stack sites ? I may not have enough reputation to do this.  
> **username_1**: assume you have a triangle formed by v, A, and B. With k=2, are both A and B what you are looking for?  
> **username_2**: Seems this belongs on CS.StackExchange not SO, not CSTheory  
> **username_3**: A classical breadth-first search algorithm of depth $k$ doesn't make it?  
> **username_2**: @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.  

---

## 0 answers

