Is there a term for these “descendancy” subgraphs of directed acyclic graphs?

Question

Consider a directed acyclic graph $G$ with vertex set $V$. Choose a vertex $v$, and let $H$ be the subgraph containing $v$ and all other vertices in $G$ that are reachable from $v$ (along with the associated directed edges).

(In other words, if we choose $v \in V$, then we are interested in the subset consisting of $v$ and all of its descendants).

Is there an accepted term for this particular subset of vertices (or the subgraph)? It seems to be a fairly elementary concept so I expected to find a commonly used phrase for this, but my search is coming up empty so far. Thanks for any answers or leads!

Answer 1

Kind of. But we're going to use the usual computer sciency way of describing this, using the language of binary relations.

You're probably already familiar with binary relations, like equality $=$, less-than-or-equal-to $\le$, subset $\subseteq$, and so on. In general, a binary relation $R$ over a set $X$ is a subset $R \subseteq X \times X$. If $(x,y) \in R$, we denote this as $xRy$.

If $\forall x \in X, xRx$, then $R$ is reflexive. The relations $=$ and $\le$ are reflexive, but $\lt$ is not.

If $\forall x, y, z \in X, xRy\,\wedge\,yRz \Rightarrow xRz$, then $R$ is transitive. Plenty of relations are transitive, including all of the ones given above. If $x \le y$ and $y \le z$, then $x \le z$.

Given a relation $R$, the reflexive transitive closure of $R$, denoted $R^*$, is the smallest relation $R^*$ such that $R \subseteq R^*$, and $R^*$ is reflexive and transitive.

Interpreting your graph as a binary relation (since the edges don't really seem to matter to you, you're only interested in the set of vertices), this is exactly what you want: $xR^*y$ if and only if $y$ is a "descendant" (by your meaning) of $x$.

When looking at the literature, you will need to know one more piece of notation: the transitive closure of $R$, denoted $R^+$, is the smallest relation $R^+$ such that $R \subseteq R^+$, and $R^+$ is transitive. Algorithms for computing the transitive closure and the reflexive transitive closure are related, since they differ only by the "diagonal" entries: $R^+ \cup \left\{ (x,x)\,|\,x \in X \right\} = R^*$.

There are several standard algorithms for computing the RTC of a relation. If the relation is dense, in the sense that it's feasible to represent it as a bit matrix, the Floyd-Warshall algorithm is one of the fastest practical algorithms; its run time is $\Theta(|V|^3)$ in theory, but the inner loop is quite fast on real hardware given that it it a bunch of bit vector manipulations.

For sparse relations, see Esko Nuutila's thesis, which contains a very good survey as well as some more recent algorithms.