# The set of all vertices, such that each vertex in the set has a path to exactly $k$ vertices

I need to find algorithms for both undirected and directed graphs, with no assumption on them being connected. Also the algorithms must be $O(V+E)$, where the undirected one should not depend on $k$.

I have ideas for both, i'm just not very sure about the directed version, because I'm not sure on how to approach the correctness proof.

For the directed version, I thought about finding all the SCC's with two DFS runs, and then running a topological sort on the graph created by representatives from each SCC. Afterwards, i'll flip the edges and start a DFS from the end vertex. For every SCC node I visit i'll increment a counter by the number of nodes in the SCC I visited. If while vising a SCC node the counter shows $k+1$ nodes, all the nodes in the SCC will be added to the set. At this point the algorithm will go back as though we reached a leaf.

For the undirected version, I can just do run a BFS/DFS for every disconnected component to find all the connected components. If a connected component has exactly k+1 nodes, then all the nodes in that component belong to the set.

Any help regarding the directed version will be great, thanks!

• Prove that in the directed case you need to have an SCC of size exactly $k+1$ as otherwise you would have two vertices with different sized reachability set. Apr 26 '15 at 5:06