2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Pål GD Apr 26 '15 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.