Optimal Antimatroid Sorting

Since we want our analysis to be independent of the candidate data structure, we split the work done by topological heapsort into two essential parts.

• $\mathrm{■}$

  The total time $t^{\mathrm{total}}(C)$ spend by the candidate data structure, as defined above.

• $\mathrm{■}$

  The time required to initialize $Q$ (given the initial elements), delete the minimum from $Q$, and insert given elements into $Q$ in each step. Call this the queue time $t^{\mathrm{Q}}$.

Since the loop performs at most $n=|\mathrm{\Sigma }|$ iterations, the running time of topological heapsort is $t^{\mathrm{total}}(C)+t^{\mathrm{Q}}+𝒪(n)$.

Note that the queue time does not depend on the representation of $S$ at all. In the following, we show that $t^{\mathrm{Q}}$ is always $𝒪(n+\log |𝒫(S)|)$, by reducing to the special case where $S$ is a partial order, which has been solved by Haeupler et al. [14]. The number of comparisons can be as large as the queue time, which is not optimal if $\log (|𝒫(S)|)\ll n$. In Section 5, we improve this bound to the optimal $𝒪(\log |𝒫(S)|)$ by modifying the algorithm.

We first consider an explicit representation of general full antimatroids based on monotone precedence systems. The precedence formula representation of a full antimatroid $A$ on $\mathrm{\Sigma }$ is a collection ${\{F_x\}}_{x\in \mathrm{\Sigma }}$, where $F_x$ is a monotone boolean formula on the variable set $V_x=\mathrm{\Sigma }\setminus \{x\}$. (A monotone boolean formula allows only the operators $\vee$ and $\wedge$ and the constants 0 and 1, notably prohibiting the negation $\neg$.)

Each formula $F_x$ represents a precedence function $p_x$ as follows: For $Y\subseteq \mathrm{\Sigma }$, we let $p_x(Y)$ be the value of $F_x$ when setting each $y\in Y$ to 1, and each $y\in X\setminus (Y\cup \{x\})$ to 0. Since any monotone function $f$ can be represented as a monotone boolean formula, this representation is suitable for every antimatroid. In the following, we assume each formula is given as a linked list of symbols with each variable, operator, constant, or parenthesis in the formula occupying one machine word. Other representations, like parsing trees and circuits, are also possible.

An CDS $C$ for ${\{F_x\}}_{x\in \mathrm{\Sigma }}$ is implemented as follows. We need two preprocessing steps. First, for each formula, we simplify it. We repeatedly replace substrings $(1\wedge x)\to x$, $(1\vee x)\to 1$, $(0\wedge x)\to 0$, and so on, in linear overall time. Afterwards, we have $F_x=1$ for each $x$ with $p_x(\mathrm{\varnothing })=1$.

Second, compute a directed graph $G$, where $V(G)=\mathrm{\Sigma }$, and $(x,y)\in E(G)$ if $F_y$ contains the variable $x$. For each such edge, we store a list of pointers to each occurrence of $x$ within $F_y$. Note that the size of $G$ (including pointers) is at most the total size of all formulas.

The initial candidate set reported by $\text{init}()$ is the set of sources in $G$. $\text{step}(\mathrm{x})$ is implemented as follows: For each out-neighbor $y$ of $x$, replace each occurrence of $x$ in $F_y$ with 1. Then, simplify $F_y$ as outlined above, and report $y$ if $F_y=1$ after the simplification. Finally, remove $x$ from the graph. To see that the data structure is correct, observe that after calling $\text{step}(\mathrm{x})$ on each $x$ in some set $X\subset \mathrm{\Sigma }$, we have $F_y=1$ for each $y$ with $p_y(X)=1$.

The total running time is linear, since each edge is visited once, and simplification is linear overall. Thus, the data structure is efficient, and so:

There are two representations of antimatroids that are similar to precedence formulas: rooted set collections and alternative precedence structures [27]. These roughly correspond to precedence formulas in conjuctive normal form and disjunctive normal form, respectively. A third related characterization with so-called elementary ranking conditions [30] is used in linguistics (see the full version of the paper for details). In the following, we discuss two more examples that only apply to subclasses of antimatroids.

Given a connected graph $G$ and a designated root $r\in V(G)$, the vertex search antimatroid on $(G,r)$, written $A_{G,r}^{\mathrm{VS}}$, contains the empty word $\epsilon$ as well as each simple word $v_1{v}_2\mathrm{\dots }{v}_k$ where $v_1=r$ and each prefix $v_1{v}_2\mathrm{\dots }{v}_i$ induces a connected subgraph of $G$. The words in $A_{G,r}^{\mathrm{VS}}$ model each way of traversing the graph in a manner similar to BFS or DFS. The basic idea is easily extended to directed graphs; here we require that each prefix $v_1{v}_2\mathrm{\dots }{v}_i$ induces a subgraph of $G$ where every vertex is reachable from $r=v_1$. (We assume that each vertex is reachable from $r$ in $G$.)

It is easy to see that $A_{G,r}^{\mathrm{VS}}$ is indeed an antimatroid; for example, as a precedence formula for each vertex $v\ne r$, take $F_v=u_1\vee u_2\vee \mathrm{\cdots }\vee u_k$, where $u_1,u_2,\mathrm{\dots },u_k$ are the neighbors (resp. in-neighbors) of $v$. However, not every antimatroid is a vertex search antimatroid.

Again, the restricted sorting problem for vertex search antimatroids is solved in optimal time with the precedence formula representation given above.

The vertex search antimatroid plays a role in the distance ordering problem, a variant of single-source shortest path (SSSP) problem. Given is an edge-weighted directed graph $(G,w)$ with a designated root $r$, and the task is to order the vertices by distance from $r$. Recently, Haeupler et al. [12] showed that Dijkstra’s classical SSSP is universally optimal when equipped with a certain working-set heap (which is more powerful than the one presented in Section 2). Universally optimal means, informally, that for every fixed graph, the algorihtm is worst-case optimal w.r.t. the weight function. In fact, they essentially match the information-theoretic lower bound with a running time of $𝒪(\log |T|+|V(G)|+|E(G)|)$, where $T$ is the set of possible distance orderings for the input graph $G$ with root $r$, with any weight function.

We now demonstrate a strong connection between antimatroid sorting and the distance ordering problem.⁴⁴4Such a connection is not surprising, since the technique used in the analysis of Dijkstra’s algorithm [12] inspired the original analysis of topological heapsort [14] and large parts of this paper. First off, the set $T$ of possible distance orderings is precisely the vertex search antimatroid (see the full version of the paper for a proof). Thus, we can run topological heapsort to find a distance ordering with optimal running time – if we are allowed to directly compare two vertices. That means comparing the distances of two vertices to $r$, which we cannot do in the distance ordering problem (without computing the distances first).

Still, it can be seen that the transcript (see the proof of Theorem 5) of a run of Dijsktra’s algorithm on an input $(G,w,r)$ is the same as running topological heapsort on the corresponding vertex search antimatroid. This gives an alternative proof of universal optimality; details are found in the full version of the paper. It should be noted that Haupler et al. also give an algorithm that is universally optimal in both time and number of comparisons, which is harder (c.f. Section 5).

An undirected graph is chordal if has no induced cycles of length four or more. It is well-known that chordal graphs can be characterized by the existence of perfect elimination orderings (PEOs). A PEO is obtained by successively removing simplicial vertices, that is, vertices whose neighborhood form a clique.

The set of elimination orderings form an antimatroid, also known as the simplicial vertex pruning [1] or simplicial shelling [27] antimatroid. Given a graph $G$, we can define the simplicial vertex pruning antimatroid $A_G^{\mathrm{SVP}}$ via the MPS ${\{p_v\}}_{v\in V(G)}$ with

A candidate data structure for $A_G$ is essentially a data structure that maintains the set of simplicial vertices in $G$ under simplicial vertex deletion.

There are known static and fully-dynamic algorithms to compute simplicial vertices in arbitrary graphs [22, 28]. Since we only care about chordal graphs and only need vertex deletion, we can use a relatively simple data structure based on clique trees. Details are found in the full version of the paper. The total running time of removing all vertices is $𝒪(m+n)$. Thus, we can solve the corresponding restricted sorting problem in optimal time.

Let $S={\{p_x\}}_{x\in \mathrm{\Sigma }}$ be a monotone precedence system on $\mathrm{\Sigma }$. The layer sequence of $S$ is a partition of $\mathrm{\Sigma }$ into nonempty layers $L_1,L_2,\mathrm{\dots },L_k$ inductively defined as follows:

• $\mathrm{■}$

  $L_1=\{x\in \mathrm{\Sigma }\mid p_x(\mathrm{\varnothing })=1\}$.

• $\mathrm{■}$

  $L_i=\{x\in \mathrm{\Sigma }\setminus {\overline{L}}_{i-1}\mid p_x({\overline{L}}_{i-1})=1\}$, where ${\overline{L}}_{i-1}=L_1\cup L_2\cup \mathrm{\cdots }\cup L_{i-1}$, for each $2\le i\le k$.

Observe that a layer sequence exists if and only if $𝒫(S)\ne \mathrm{\varnothing }$, and that a layer sequence is always unique. If a candidate data structure $C$ is available, we can compute the layer sequence in $𝒪(t^{\mathrm{total}}(C))$ time as follows: Call $C.\text{init}()$ and add the reported elements to $L_1$. Then, call $C.\text{step}(\mathrm{x})$ for each $x\in L_1$, add the reported elements to $L_2$, and so on.

In this section, we show how to sort the non-bottleneck elements $\mathrm{\Sigma }\setminus \tilde{\beta }$ of an antimatroid $A$. Recall that a candidate data structure $C$ is given, and we want to sort in overall time $𝒪(t^{\mathrm{total}}(C)+\log |𝒫(A)|)$, with $𝒪(\log |𝒫(A)|)$ comparisons (see Theorem 7). We show how to sort any subset $\mathrm{\Gamma }\subseteq \mathrm{\Sigma }$ within this budget.

We first need some definitions. Let $\mathrm{\Sigma }$ be an alphabet. Given a word $\alpha$ and a subset $\mathrm{\Gamma }\subseteq \mathrm{\Sigma }$, the restriction of $\alpha$ to $\mathrm{\Gamma }$, written ${\alpha |}_{\mathrm{\Gamma }}$, is obtained by removing all letters in $\mathrm{\Sigma }\setminus \mathrm{\Gamma }$ from $\alpha$. For a simple language $L\subseteq {\mathrm{\Sigma }}_{\mathrm{s}}^{\ast }$, let ${L|}_{\mathrm{\Gamma }}=\{{\alpha |}_{\mathrm{\Gamma }}\mid \alpha \in L\}$. It is known that if $A\subseteq {\mathrm{\Sigma }}_{\mathrm{s}}^{\ast }$ is an antimatroid, then the restriction ${A|}_{\mathrm{\Gamma }}$ is also an antimatroid (called the trace [27, 1]).

Let us now assume we have a candidate data structure $C_{\mathrm{\Gamma }}$ for ${A|}_{\mathrm{\Gamma }}$. Then we can use topological heapsort to sort $\mathrm{\Gamma }$. The running time is $t^{\mathrm{total}}(C_{\mathrm{\Gamma }})+𝒪(\log |𝒫(A{|}_{\mathrm{\Gamma }})|)$, and we need $𝒪(|\mathrm{\Gamma }|+\log |𝒫(A{|}_{\mathrm{\Gamma }})|)$ comparisons. First, observe that $|𝒫(A{|}_{\mathrm{\Gamma }})|\le |𝒫(A)|$, since the restriction operation surjectively maps $𝒫({A|}_{\mathrm{\Gamma }})$ to $𝒫(A)$. Second, recall that $|\mathrm{\Gamma }|\le 2\log |𝒫(A)|$ if $\mathrm{\Gamma }$ is obtained by removing all bottleneck elements (Corollary 10). If we further assume that $t^{\mathrm{total}}(C_{\mathrm{\Gamma }})\le 𝒪(t^{\mathrm{total}}(C))$, then we are within the budget of Theorem 7.

It remains to build a candidate data structure $C_{\mathrm{\Gamma }}$ for ${A|}_{\mathrm{\Gamma }}$ with $t^{\mathrm{total}}(C_{\mathrm{\Gamma }})\le 𝒪(t^{\mathrm{total}}(C))$. Suppose $C$ is given. Then $C_{\mathrm{\Gamma }}.\text{init}()$ is implemented as follows. First, call $C.\text{init}()$, and store the result in a set $Y$. Then, we repeat the following as long as there is an element $y\in Y\setminus \mathrm{\Gamma }$: Discard $y$, call $C.\text{step}(\mathrm{y})$, and add all reported elements to $Y$. At the end, report the final set $Y$.

To implement $C_{\mathrm{\Gamma }}.\text{step}(\mathrm{y})$, we similarly first call $C.\text{step}(\mathrm{y})$, store the result in a set $Y$, and perform the repeated replacement as above.

The (rather technical) correctness proof for $C_{\mathrm{\Gamma }}$ is found in the full version of the paper. The running time is clearly $t^{\mathrm{total}}(C)+𝒪(|\mathrm{\Sigma }|)=𝒪(t^{\mathrm{total}}(C))$. Thus, we have:

We now want to optimally merge under antimatroid constraints:

A proof of Theorem 13 is given in the full version of the paper. The algorithm used can be seen as a simplified version of Haeupler et al.’s heapsort with lookahead algorithm [14]; in fact, if the antimatroid $A$ is given as a collection of precedence formulas, it simplifies to a partial order under the assumption that $\gamma$ and $\delta$ are sorted. (However, our proof works with general candidate data structures.)

We now prove Theorem 7. First, we compute the bottleneck sequence $\beta$ with Lemma 11. Then, we use Lemma 12 to sort the subset $\mathrm{\Gamma }=\mathrm{\Sigma }\setminus \tilde{\beta }$. In other words, if $\pi$ is the underlying total order, we compute $\gamma ={\pi |}_{\mathrm{\Gamma }}$. Finally, we merge $\beta$ and $\gamma$ using Theorem 13. The overall running time is $𝒪(t^{\mathrm{total}}(C)+\log |𝒫(A)|+\log |R|)$, and we use $𝒪(\log |𝒫(A)|+|\mathrm{\Gamma }|+\log |R|)$ comparisons, where $R$ is as defined in Theorem 13. Note that $R\subseteq 𝒫(A)$. Moreover, we have $|\mathrm{\Gamma }|=n-|\beta |\le 2\log |𝒫(A)|$ by Lemma 11. Thus, we need $𝒪(t^{\mathrm{total}}(C)+\log |𝒫(A)|)$ time and $𝒪(\log |𝒫(A)|)$ comparisons, as desired.