Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached.

I thought to run an SCC algorithm to find binding components and then return them. This is true? Or is there a better algorithm?

  • 1
    $\begingroup$ What are the strongly connected components of a graph without circles? Are you familiar with the concepts of sources and sinks? $\endgroup$ – Pål GD Jan 21 at 11:03
  • $\begingroup$ Try using a topological sort. $\endgroup$ – Yuval Filmus Jan 21 at 11:17
  • $\begingroup$ After the use of topological sort, there is a row of vertices arranged by a forward edge, what is the next step? $\endgroup$ – Kate Jan 21 at 13:35

Considering the strongly connected component is a good start if graph $G$ may have cycles. However, as implied by Pål GD, every vertex is a strongly connected component of a graph without cycles. We need to do more work to find the minimum set of vertices from which all vertices can be reached.

Here is the outline of an algorithm that does the job.

  1. Find one root $r$ of $G$ by repeatedly going to the ancestor of a node. Mark $r$ as an wanted vertex.
  2. Remove all vertices reachable from $r$.
  3. Go to step 1 unless there is no more vertex.
  4. return all vertices that are marked as wanted.

Exercise. Given a directed graph (that may have cycles), describe an algorithm that finds a minimum set of vertices from which all vertices can be reached. (Hint, strongly connected components are useful now. Try reducing the problem to the current question.)


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.