-1
$\begingroup$

Suppose a directed graph G=(V,E). I am interested in computing the smallest subset of nodes V' such that:

  1. Every node n in G is reachable from at least one node in V', with a directed path
  2. Every edge e in G is reachable from at least one node in V', with a directed path
  3. Again, V' is the smallest subset that satisfies the above properties

comment 1: Nodes in V' are considered reachable by definition.

comment 2: I suppose property 3. is already implied by property 2., but I added it to make sure there are no exceptions.

comment 3: Nodes with no links at all are also in V' for the same reason

comment 4: Nodes with no incoming links are in V' as they are not reachable by any other means

Questions:

  • Is there a name for this problem in the literature of graph theory?
  • Are there efficient algorithms to solve this problem?
$\endgroup$
1
$\begingroup$

An algorithm for solving this problem is given here. To wit: find the strongly connected components of the directed graph and pick one vertex from each "source" component. If you're not familiar with strongly connected components, the Wikipedia page might be helpful. I'm not aware of a name for this problem.

$\endgroup$

Your Answer

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

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