<p>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 <a href="https://louis.jachiet.com/" rel="nofollow noreferrer">Louis</a>. Here is my summary of his idea.</p>

<p><strong>Edit:</strong> The scheme below, in a much more concise and understandable form, appears as Theorem C.1 in our <a href="https://arxiv.org/abs/1702.05589" rel="nofollow noreferrer">recent preprint</a>. 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 <em><a href="https://en.wikipedia.org/wiki/Multitree" rel="nofollow noreferrer">multitrees</a></em> and also refines the scheme slightly to show a logarithmic bound on memory usage.</p>

<hr>

<p>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.</p>

<p>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.)</p>

<p>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.</p>

<p>There are three kinds of nodes in infix trees:</p>

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

<p>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.</p>

<p>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:</p>

<ol>
<li>we can actually do this in linear time;</li>
<li>when we have done this, we can enumerate in constant delay.</li>
</ol>

<p>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:</p>

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

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

<p>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.</p>

<p>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\}$.</p>

<p>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.</p>

<ul>
<li><p>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$.</p></li>
<li><p>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).</p></li>
<li><p>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$.</p></li>
<li><p>The case where $N_1$ is a leaf and $N_2$ is a large internal node is
symmetric to the case above.</p></li>
<li><p>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$.</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2017-01-06T11:15:02.453Z
2017-02-21T18:37:37.130Z
2017-02-21T18:37:37.130Z
Antoine Amarilli 'a3nm'
<p>A <em><a href="https://en.wikipedia.org/wiki/Polytree" rel="nofollow noreferrer">polytree</a></em> is a <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow noreferrer">directed acyclic graph</a> which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart.</p>

<p>Given a polytree $T$ and a node $n \in T$, the set of <em>reachable leaves</em> $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$.</p>

<p>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)$.</p>

<p>Specifically, a <em>preprocessing algorithm</em> takes as input the polytree $T$ and computes some data structure $D$ in some amount of time. An <em>enumeration algorithm</em> 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.</p>

<p><strong>What are the most efficient algorithms for this problem</strong>, in terms of preprocessing time and enumeration time? Specifically, I am looking for a <em>linear-time preprocessing</em> and for <em>constant-delay enumeration</em>, 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. </p>

<p>[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.]</p>

<p>[Further note that, if $T$ is a <em>directed tree</em>, 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.]</p>

<ds.algorithms><graph-algorithms><tree><transitive-closure>
Efficient enumeration of the reachable leaves of nodes in a polytree
Antoine Amarilli 'a3nm'
# Efficient enumeration of the reachable leaves of nodes in a polytree

(Asked by: username_0 on 2017-01-05)

A *[polytree](https://en.wikipedia.org/wiki/Polytree)* is a [directed acyclic graph](https://en.wikipedia.org/wiki/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.]

**Tags:** ds.algorithms, graph-algorithms, tree, transitive-closure

---

## 1 answers

### Answer by username_0 on 2017-01-06. Score: 0 | Accepted answer

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](https://louis.jachiet.com/). 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](https://arxiv.org/abs/1702.05589). 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](https://en.wikipedia.org/wiki/Multitree)* 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.


---

