Efficient enumeration of the reachable leaves of nodes in a polytree

Question

A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart.

Given a polytree $T$ and a node $n \in T$, the set of reachable leaves $L(n)$ of $n$ is the set of nodes $n' \in T$ that have no child in $n'$ and such that $n'$ is reachable from $n$.

I would like intuitively to know an efficient algorithm to preprocess a polytree to be able to answer queries where I am given an arbitrary $n \in T$ and I must enumerate the contents of $L(n)$.

Specifically, a preprocessing algorithm takes as input the polytree $T$ and computes some data structure $D$ in some amount of time. An enumeration algorithm takes as input $T$, $D$, the query node $n \in T$, and the previous state $S_{i-1}$ of the enumeration (initially $S_0$ is empty), and outputs the $i$-th element $n' \in L(n)$ and a next state $S_i$ (with a special value used to signal termination of the enumeration). The enumeration, when called successively, must output exactly the elements of $L(n)$ in some arbitrary order, without outputting the same element multiple times.

What are the most efficient algorithms for this problem, in terms of preprocessing time and enumeration time? Specifically, I am looking for a linear-time preprocessing and for constant-delay enumeration, i.e., the preprocessing should take time $O(|T|)$ and, for any query node $n \in T$, each enumeration step should take $O(1)$ time. If this is known to be impossible, I am also interested in a lower bound.

[Note that we can just precompute the answer for all nodes with quadratic preprocessing time, or compute each answer on the fly with linear-time enumeration for each answer (to traverse the relevant part of $T$), hence my focus on linear-preprocessing and constant-delay.]

[Further note that, if $T$ is a directed tree, we can achieve what I request by precomputing in linear time, for each node, its first and last reachable leaf in pre-order traversal, and for each leaf, its next leaf in post-order traversal. Then we can do constant-delay enumeration by jumping to the first reachable leaf of the vertex, and go through the leaves in order until we reach the last reachable leaf of the vertex. But the extension to polytrees does not seem straightforward.]

Answer 1

It turns out that it is possible to do what I want with linear preprocessing and constant delay, by an argument suggested by my friend Louis. Here is my summary of his idea.

Edit: The scheme below, in a much more concise and understandable form, appears as Theorem C.1 in our recent preprint. I'm leaving the messy sketch below in case it's useful, but you should probably look at the preprint instead (the theorem and proof are independent from the surrounding material). The proof is generalized to multitrees and also refines the scheme slightly to show a logarithmic bound on memory usage.

---

Let's consider a polytree $P$. The linear preprocessing can insert intermediate nodes and collapse nodes with only one child to get a polytree which we can use to answer queries on the original polytree, so that we can assume without loss of generality that all internal nodes of $P$ have degree exactly 2.

We will do the linear-time preprocessing bottom-up following any topological order. For every node of $P$ that we process (whose children have all already been processed), we will construct an index structure for the node, which we call an "infix tree", and which may also include pointers to other previously defined such structures (but not modify them, of course: one can think of this as a purely functional data structure supporting constant-delay enumeration and constant-time union.)

The construction will work in linear time, and for any node we will be able to enumerate its descendants in constant delay by considering its infix tree.

There are three kinds of nodes in infix trees:

• leaves, which are labeled with an explicit set of at least one and at most four elements (which are leaves of the original polytree);
• small internal nodes, which are labeled with one explicit element and with pointers to one or two infix tree nodes;
• large internal nodes, which are labeled with two explicit elements and with pointers to one or two infix tree nodes.

We further require that there are no duplicate elements in the infix tree, i.e., for every node $x$ of the infix tree, each leaf of $P$ appears at most once in the labels of $x$ and its descendants. A node $x$ in an infix tree codes a set $S(x)$ of leaves of $P$, namely, those which appear in the node's label and its descendants (and as we just assumed it is always duplicate-free). The idea of the infix tree is that, by keeping around some explicit elements, we can both use them when enumerating to make progress when visiting the nodes, and use them when unioning two sets of descendants to have sufficiently many elements to annotate the newly created nodes in the infix tree.

Our indexing data structure will map each node $n$ of the polytree to an infix tree node $N(n)$ capturing exactly its reachable leaves, i.e., $S(N(n))$ is the set of leaves that are reachable from $n$ in $P$. There are two claims:

1. we can actually do this in linear time;
2. when we have done this, we can enumerate in constant delay.

Let's first see why claim 2 is true. From the infix tree $N(n)$ of a node $n$ of $P$, we can enumerate its contents in constant delay with the following algorithm. Maintain a working list $W$ of nodes of the infix tree to be enumerated, initially it is $\{N(n)\}$. Now, until $W$ is empty, take its first element $x$ and do the following:

• if $x$ is a leaf of the infix tree, enumerate its elements and discard $x$
• if $x$ is an internal node (small or large), enumerate its explicit elements and add its child nodes to $W$.

It is clear that this correctly enumerates $S(N(n))$, and that it is constant delay because at each step we enumerate something

So now let's turn to the proof of claim 1. To do this, we will proceed bottom-up as I pointed out above, further maintaining the following invariant: for any node $n$ of $P$, $N(n)$ is never a small internal node, so it is either a large internal node or a leaf. In other words, small internal nodes will only be used as an intermediate tool in the construction, but no node of $P$ directly points to such a node in the result of the indexing.

The base case is for a leaf $n$ of $P$, where we set $N(n)$ to be a fresh leaf node of the infix tree whose contents are $\{n\}$.

The inductive case is for an internal node $n$ of $P$ with children $n_1$ and $n_2$, for which $N_1 := N(n_1)$ and $N_2 := N(n_2)$ have already been prepared (and are not small internal nodes). We set $N(n)$ as follows depending on the types of $N_1$ and $N_2$. Note that, by design, in the nodes that we add, we will be pointing to $N_1$ and $N_2$ (and also to their children in some cases), but that's fine provided that we don't modify them.

• If $N_1$ and $N_2$ are leaves and their explicit lists contain at most four elements total, set $N(n)$ to be a fresh leaf node with an explicit list which is the union of the labels of $N_1$ and $N_2$.

• If $N_1$ and $N_2$ are leaves and their explicit lists contain five or more elements total, set $N(n)$ to be a fresh large internal node labeled with the first two elements of the union of the labels, and whose two children are two fresh leaves with the missing elements (the two lists can be made non-empty because there are at least two elements left).

• If $N_1$ is a large internal node and $N_2$ is a leaf, we make $N$ a fresh large internal node labeled with the elements of $N_1$, and having one child which is a fresh small internal node labeled with the first element of $N_2$ and whose children are (pointers to) the children of $N_1$. If $N_2$ has strictly more than one element, we create a fresh leaf node containing the remaining elements of $N_2$, that we add as a second child of $N$.

• The case where $N_1$ is a leaf and $N_2$ is a large internal node is symmetric to the case above.

• If $N_1$ and $N_2$ are large internal nodes, we create a fresh large internal node $N$ containing the elements of $N_1$, and whose children are two fresh small internal nodes, the first one containing the first element of $N_2$ and pointers to the children of $N_1$, the second one containing the second element of $N_2$ and pointers to the children of $N_2$.

This is clearly in constant time, and one can verify that the semantics is correct, i.e., $S(N)$ is the set of reachable leaves, with no dupes: this is obvious for leaves and proved in the inductive case from the contents of $N_1$, $N_2$ and their children. This concludes the proof of claim 2 and the proof of the overall scheme.