Proofs: PQ-tree

REDUCE keeps exactly the frontiers in which S is consecutive, and it terminates full

This proof shows: correctness, termination.

Let $T$ be a PQ-tree over $U$ in which every P-node has at least 2 children and every Q-node at least 3, and let $S \subseteq U$. For a node $x$, write $L(x)$ for its set of leaves and $\mathrm{Fr}(x)$ for its set of frontiers, as defined on the page. For sets of sequences $A, B$, write $A \cdot B = \{ ab : a \in A, b \in B \}$. Call a sequence over $L(x)$ right-full if it has the form $e g$ where $e$ has no element of $S$ and $g$ has only elements of $S$, and write $\mathrm{Fr}_{\to}(x)$ for the right-full frontiers of $x$. Write $\mathrm{Fr}_S(x)$ for the frontiers of $x$ in which the elements of $S \cap L(x)$ are consecutive. For a list of trees $y_1, \ldots, y_m$, let $\mathrm{Fr}(y_1, \ldots, y_m) = \mathrm{Fr}(y_1) \cdots \mathrm{Fr}(y_m)$.

Lemma 1 (reversal). For every node $x$, the reverse of a frontier of $x$ is a frontier of $x$.

Proof. By induction on the height. A leaf is its own reverse. If $f = f_{\sigma(1)} \cdots f_{\sigma(d)}$ for a node with children $c_1, \ldots, c_d$, then its reverse is $\bar f_{\sigma(d)} \cdots \bar f_{\sigma(1)}$, where $\bar f_i \in \mathrm{Fr}(c_i)$ by induction. The reversed order of the children is allowed at a P-node, which allows every order, and at a Q-node, which allows the given order and its reverse, and the reverse of the reverse is the given order. $\square$

So, for a list of trees, the reverses of the sequences in $\mathrm{Fr}(y_1, \ldots, y_m)$ form exactly $\mathrm{Fr}(y_m, \ldots, y_1)$.

Lemma 2 (normalization). Replacing a node with one child by that child, or a Q-node with two children by a P-node with the same children, does not change $\mathrm{Fr}$. Hence $\mathrm{Fr}(Q(y_1, \ldots, y_m)) = \mathrm{Fr}(y_1, \ldots, y_m) \cup \mathrm{Fr}(y_m, \ldots, y_1)$ for every $m \ge 1$, and $\mathrm{Fr}(P(y_1, \ldots, y_m))$ is the union of $\mathrm{Fr}(y_{\sigma(1)}, \ldots, y_{\sigma(m)})$ over all permutations $\sigma$, also after normalization.

Proof. A node with one child has one order of its children. With two children, the permutations are the identity and the swap, which are exactly the identity and the reversal. $\square$

Every node that REDUCE builds is normalized, so the node rules hold for its result.

Lemma 3 (labels). If $x$ is partial, every frontier of $x$ contains an element of $S$ and an element not in $S$. A child of an empty node is empty, and a child of a full node is full.

Proof. Immediate from the definitions $0 < k(x) < \lvert x \rvert$, $k(x) = 0$ and $k(x) = \lvert x \rvert$. $\square$

Lemma 4 (SINGLY). Let $x$ be a partial node. If $\mathrm{Fr}_{\to}(x) = \emptyset$, then SINGLY$(x)$ fails. Otherwise SINGLY$(x)$ returns a list $y_1, \ldots, y_m$ with $m \ge 2$, each $y_i$ empty or full, the empty ones before the full ones, and $\mathrm{Fr}(y_1, \ldots, y_m) = \mathrm{Fr}_{\to}(x)$.

Proof. By induction on the height of $x$. A partial node is not a leaf, so let $c_1, \ldots, c_d$ be its children.

P-node, lines L10 and L11. Take a right-full frontier $f = f_{\sigma(1)} \cdots f_{\sigma(d)}$. Each $f_i$ is a contiguous piece of $f$. If two children $c_i$, $c_j$ are partial with $c_i$ first in the order, then $f_i$ has an element of $S$ that comes before an element of $f_j$ that is not in $S$, by Lemma 3, which a right-full sequence does not allow. So there is at most one partial child, and if there are two or more, $\mathrm{Fr}_{\to}(x) = \emptyset$ and line L10 fails. Suppose there is at most one, $c_p$. In a right-full $f$, every empty child comes before every child with an element of $S$, every full child comes after every child with an element not in $S$, and $f_p$ is itself right-full. Conversely, every concatenation that puts the empty children first in any order, then a right-full frontier of $c_p$ if it exists, then the full children in any order, is right-full and is a frontier of $x$. So $\mathrm{Fr}_{\to}(x) = \mathrm{Fr}(P(\text{empty children})) \cdot \mathrm{Fr}_{\to}(c_p) \cdot \mathrm{Fr}(P(\text{full children}))$, with absent factors left out. If $\mathrm{Fr}_{\to}(c_p) = \emptyset$ the set is empty, and SINGLY$(c_p)$ fails by induction. Otherwise induction replaces the middle factor by $\mathrm{Fr}$ of the list SINGLY$(c_p)$, which is the list of line L11. The trees $P(\text{empty children})$ and $P(\text{full children})$ are empty and full. The list has at least 2 entries: $x$ is partial, so it has an element of $S$ and an element not in $S$, and either both groups are present, or $c_p$ is present and contributes at least 2 entries.

Q-node, lines L12 and L13. A frontier is $f_1 \cdots f_d$ or $f_d \cdots f_1$. Read in the chosen direction, the frontier is right-full if and only if the labels read some empty children, then at most one partial child, then some full children, and the frontier of the partial child is right-full: this is the same argument as for the P-node, with the order fixed. Both directions cannot satisfy the label condition at once. If they did, the label sequence and its reverse would both be monotone in the order empty, partial, full, so all $d$ labels would be equal; they are not all empty or all full, since $x$ is partial, and not all partial, since $d \ge 3$ and at most one is partial. So if neither direction satisfies the condition, $\mathrm{Fr}_{\to}(x) = \emptyset$ and line L12 fails. Otherwise $\mathrm{Fr}_{\to}(x) = \mathrm{Fr}(c_{i_1}) \cdots \mathrm{Fr}_{\to}(c_p) \cdots \mathrm{Fr}(c_{i_d})$ for the one valid direction $i_1, \ldots, i_d$, and induction on $c_p$ gives the list of line L13, or a failure exactly when this set is empty. Its entries are the empty and full children and the entries of SINGLY$(c_p)$, in the order empty before full, and there are at least $d - 1 + 2 \ge 2$ of them if $c_p$ exists and $d \ge 3$ otherwise. $\square$

Lemma 5 (ROOT). Let $x$ be a node with $S \subseteq L(x)$ such that either $x$ has at least two non-empty children, or $x$ has exactly one non-empty child and it is full. Then ROOT$(x)$ fails if $\mathrm{Fr}_S(x) = \emptyset$, and otherwise returns a tree $x'$ with $L(x') = L(x)$ and $\mathrm{Fr}(x') = \mathrm{Fr}_S(x)$.

Proof. No child contains all of $S$ and is partial: if a child $c$ is partial and $S \subseteq L(c)$, then $c$ is the only non-empty child, which the hypothesis excludes. Take $f \in \mathrm{Fr}(x)$ in which $S$ is consecutive, and let $B$ be the block of positions of $S$ in $f$. Each child $c_i$ occupies a contiguous segment of $f$. A child whose segment lies inside $B$ is full, and one disjoint from $B$ is empty. A partial child has a segment that meets $B$ and its complement, so the segment contains one end of $B$ and sticks out on that side; it cannot contain both ends, since then $S \subseteq L(c_i)$. Each end of $B$ lies in one segment, so there are at most two partial children, the non-empty children have adjacent segments, the partial ones are the outer ones of these, and the left one has a right-full frontier while the right one has the reverse of a right-full frontier. Conversely, any frontier of $x$ of this shape has $S$ consecutive.

P-node, lines L5 to L7. If there are three or more partial children, $\mathrm{Fr}_S(x) = \emptyset$ and line L5 fails. If there is none, the condition says only that the full children are adjacent, in any order, among the empty ones in any order, which is $\mathrm{Fr}(P(\text{empty children}, P(\text{full children})))$, the tree of line L7. If there are partial children $p_1$ and possibly $p_2$, the frontiers in $\mathrm{Fr}_S(x)$ place the block "$p_1$ right-full, the full children in any order, $p_2$ reversed right-full" or its mirror image with $p_1$ and $p_2$ swapped, as one contiguous piece among the empty children in any order. By Lemma 4 and Lemma 1, the block sequences in the first orientation are $\mathrm{Fr}(Z)$ for the list $Z$ of line L6, and those of the second are, by Lemma 1 applied to each entry, the reverses $\mathrm{Fr}$ of the reversed list. By Lemma 2 these together are $\mathrm{Fr}(Q(Z))$, so $\mathrm{Fr}_S(x) = \mathrm{Fr}(P(\text{empty children}, Q(Z)))$. If SINGLY fails for $p_1$ or $p_2$, Lemma 4 says that that child has no right-full frontier, and by Lemma 1 none whose reverse is right-full, so $\mathrm{Fr}_S(x) = \emptyset$, and the failure is correct.

Q-node, lines L8 and L9. In each of the two directions, the shape above says: the non-empty children are consecutive in the list of children, the inner ones are full, the left outer one, if partial, has a right-full frontier, and the right outer one, if partial, the reverse of one. The label part of this condition is the same in both directions, since reversing a list keeps adjacency and the set of inner positions. If it fails, line L8 fails and $\mathrm{Fr}_S(x) = \emptyset$. If it holds, the frontiers in the given direction are $\mathrm{Fr}$ of the list of line L9, by Lemma 4 for the outer partial children, and those in the reverse direction are the reverses, by Lemma 1. So $\mathrm{Fr}_S(x) = \mathrm{Fr}(Q(\text{list}))$ by Lemma 2. A failure of SINGLY again means $\mathrm{Fr}_S(x) = \emptyset$. $\square$

Theorem. REDUCE$(T, S)$ returns a tree $T'$ with $\mathrm{Fr}(T') = \{\, \pi \in \mathrm{Fr}(T) : S \text{ is consecutive in } \pi \,\}$, every P-node of $T'$ has at least 2 children and every Q-node at least 3, and REDUCE fails exactly when this set is empty. REDUCE terminates after $O(n)$ steps.

Proof. If $\lvert S \rvert \le 1$, $S$ is consecutive in every sequence, and line L1 returns $T$. Otherwise the walk of line L3 keeps the invariant $S \subseteq L(x)$: it holds at the root, and it moves to $c$ only when $c$ is the only non-empty child of $x$. When it stops, $x$ is not a leaf, since $\lvert L(x) \rvert \ge \lvert S \rvert \ge 2$, and $x$ meets the hypothesis of Lemma 5: either $x$ has at least two non-empty children, or one non-empty child that is full. (If $x$ is full, all of its at least 2 children are full.) Let $x_0, x_1, \ldots, x_t = x$ be the nodes of the walk. For $s < t$, $S \subseteq L(x_{s+1})$, and $L(x_{s+1})$ is a contiguous piece of every frontier of $x_s$, so $S$ is consecutive in a frontier of $x_s$ if and only if it is consecutive in the piece of $x_{s+1}$. Hence replacing $x_{s+1}$ by a tree with frontiers $\mathrm{Fr}_S(x_{s+1})$ turns $x_s$ into a tree with frontiers $\mathrm{Fr}_S(x_s)$, and by induction from $s = t$, where Lemma 5 applies, up to $s = 0$, the result is $\mathrm{Fr}(T') = \mathrm{Fr}_S(T)$. A failure at line L4 means $\mathrm{Fr}_S(x) = \emptyset$, so $\mathrm{Fr}_S(T) = \emptyset$ by the same equivalence. The node rules hold because every node built is normalized and the other nodes are unchanged.

For termination, line L2 visits each node once. The walk of line L3 goes down one level per step. ROOT is called once, and each call of SINGLY is on a proper descendant of the node that calls it, a different node each time, so there are fewer calls than nodes. A tree with $n$ leaves in which every inner node has at least 2 children has at most $2n - 1$ nodes, and each call does work proportional to the number of children of its node, so the total is $O(n)$. $\square$

Corollary. Starting from UNIVERSAL$(U)$ and reducing by $S_1, \ldots, S_m$ in turn gives a tree whose frontiers are exactly the orders of $U$ in which every $S_i$ is consecutive, or a failure exactly when no such order exists. This follows from the theorem by induction on $m$, since $\mathrm{Fr}(\text{UNIVERSAL}(U))$ is the set of all orders of $U$. $\blacksquare$