Suppose a directed graph G=(V,E). I am interested in computing the smallest subset of nodes V' such that:
- Every node n in G is reachable from at least one node in V', with a directed path
- Every edge e in G is reachable from at least one node in V', with a directed path
- 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
- Is there a name for this problem in the literature of graph theory?
- Are there efficient algorithms to solve this problem?