4
$\begingroup$

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!

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is great, thank you! It makes sense that there would be a solid way to define it using relations. The reference to the FW algorithm is helpful. Most of the time I just see it defined as "the set of all descendants" and it's left at that, without bothering to give a more playful or colorful term for it. $\endgroup$ Commented Feb 5, 2020 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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