Parameterized Streaming Algorithms for Topological Sorting

Let $S$ be an antichain in $G$; that is, a subset of nodes in $G$ such that for any two nodes $u$ and $v$ in the subset, there exists no directed path from $u$ to $v$. Thus, $S$ is an independent set and $|S|\le \alpha$. This property holds also for any largest antichain in $G$. By Dilworth’s theorem [9], $G$ has a chain cover consisting of at most $\alpha$ chains. For each node $x$ in $G$, if $x$ has out-degree greater than $\alpha$, then by the pigeonhole principle, there exist two out-neighbors $u$ and $v$ of $x$ that belong to the same chain in the chain cover. Let the chain be $a_1\to a_2\to \mathrm{\cdots }\to a_t$ for some $t\ge 2$ and $u=a_i,v=a_j$ for some . If the edge $(x,v)$ is removed from $G$, then the resulting graph has the same transitive closure as $G$. This holds because $x$ can still reach $v$ via the edge $(x,u)$ followed by a directed path $P$ that witnesses the chain $a_i\to a_j$. Note that $x$ is not on $P$, as $G$ is acyclic, and neither is the edge $(x,v)$. Consequently, one can iteratively remove an edge from $G$ while retaining the transitive closure unchanged until every node in $G$ has out-degree at most $\alpha$.

The same argument works for any graph $G^{\prime }$ that has the same transitive closure as $G$, even if the independence number of $G^{\prime }$ exceeds $\alpha$. $◀$

One may find that Lemma 4 still holds if the number of nodes in a largest antichain in $G$ is $\alpha$. However, it is essential for our algorithm to have the independence number of $G$ bounded by $\alpha$. In this way, every node-induced subgraph of $G$ (rather than only $G$) has an antichain consisting of at most $\alpha$ chains, which is the key to find the subgraph $H$ efficiently in the streaming model.

First, we find the chain cover used in the proof of Lemma 4 as follows.

We begin with an $O(\log n)$-pass $O(\alpha n)$-space streaming algorithm. First, we partition the nodes of $G$ into subsets $\{S_{2i-1},S_{2i}:i\in [t]\}$ arbitrarily for some integer $t=O(n)$, each containing $O(1)$ nodes. We then scan the stream of all edges in $G$ once. For each $j\in [2t]$, we collect all edges in the node-induced subgraph $G[S_j]$ in memory. Next, we apply the approach from the proof of Lemma 4 to compute a chain cover consisting of $\alpha$ chains for $G[S_j]$ and trim $G[S_j]$ into a sparse subgraph with $O(\alpha |S_j|)$ edges.

We then scan the stream of all edges in $G$ again. For each pair of consecutive node-induced subgraphs $G[S_{2i-1}]$ and $G[S_{2i}]$, we collect edges with one endnode in $S_{2i-1}$ and the other in $S_{2i}$ (i.e., crossing edges). Since we have a chain cover consisting of $\alpha$ chains for both $G[S_{2i-1}]$ and $G[S_{2i}]$, at most $\alpha$ essential crossing edges per node in $S_{2i-1}$ and $S_{2i}$ are required to preserve the transitive closure. This can be done using $O(\alpha (|S_{2i-1}|+|S_{2i}|))$ space because, for each of the $\alpha$ chains in the node-induced subgraph $S_{2i-1}$ (resp. $S_{2i}$), each node $x$ in $S_{2i}$ (resp. $S_{2i-1}$) only needs to keep the single out-neighbor $y$ that appears first in the chain. Finally, we replace the union of $G[S_{2i-1}]$, $G[S_{2i}]$, and their essential crossing edges with an $O(\alpha (|S_{2i-1}|+|S_{2i}|))$-edge subgraph $H$, ensuring that $H$ and $G[S_{2i-1}\cup S_{2i}]$ have the same transitive closure and thus the chain cover of $H$ consists of at most $\alpha$ chains. Such a sparse subgraph $H$ can be found because the union of $G[S_{2i-1}]$, $G[S_{2i}]$, and the essential crossing edges has the same transitive closure as $G[S_{2i-1}\cup S_{2i}]$ and hence we can apply Lemma 4 though the independence number of the union may exceed $\alpha$.

The above process reduces the number of subsets by half. The space usage remains $O(\alpha n)$. Repeating this process for $O(\log n)$ iterations merges all subsets into a single subgraph with a chain cover of $\alpha$ chains.

The above approach groups two subsets at a time. More generally, we can group $n^{\epsilon }$ subsets at a time. This increases space usage by a factor of $n^{\epsilon }$ while reducing the number of passes to

$◀$

Then, we use the chain cover found in Lemma 5 to compute $H$ as follows.

By Lemma 5, we obtain a chain cover of $G$ consisting of $\alpha$ chains using the claimed number of passes and space. Then, in another pass over all edges of $G$, for each node $x$, we store all of its out-neighbors in a list. If the list exceeds $\alpha$ out-neighbors, at least one can be discarded, as established in the proof of Lemma 4. $◀$

Finally, given the subgraph $H$, a topological ordering of $G$ can be computed by topologically sorting $H$. This gives an $O(1/\epsilon )$-pass $O(\alpha n^{1+\epsilon })$-space deterministic streaming algorithm to compute a topological ordering for any n-node directed acyclic graph $G$ in the insertion-only model. This proves the few-pass algorithm stated in Theorem 1.

It suffices to show that no edge goes from $G\setminus H_3$ to $H_3$. Since $H_3$ is a source subgraph of $H_1$, we only need to prove that that no edge goes from $G\setminus H_1$ to $H_3$.

Let $\sigma$ be a topological ordering of $G$ such that $|\sigma (v)-A(v)|\le \delta$ for all nodes $v$. For any node $u_1\in H_3$, we have $\sigma (u_1)\le A(u_1)+\delta \le t+2\delta$. Similarly, for any node $u_2\in G\setminus H_1$, we have $\sigma (u_2)>t+2\delta$. Combining the two inequalities, we have . Therefore, no edge goes from $G\setminus H_1$ to $H_3$, which completes the proof. $◀$

Using the above lemma, to find a source subgraph in $G$, it suffices to remember the induced subgraph $H_1$ and find the maximum source subgraph $H_3$ that satisfies the conditions listed. This can be done by remembering the entire induced subgraph $H_1$ in a single pass. The following two lemmas show that keeping the entire subgraph $H_1$ takes $O(t\delta +{\delta }^2)$ space, and the resulting source subgraph has size at least $t$.

Let $\sigma$ be a topological ordering of $G$ such that $|\sigma (v)-A(v)|\le \delta$ for all nodes $v$. Only the first $t+4\delta$ nodes of $\sigma$ can satisfy $A(v)\le t+3\delta$. $◀$

Lemma 12 shows that the subgraph $H_1$ defined in Lemma 11 has $O(t+\delta )$ nodes. Since the maximum displacement between the advice and the true ordering is at most $\delta$, any pair of nodes whose advice values differ by more than $2\delta$ must appear in the same relative order as suggested by the advice. Therefore, when computing a topological ordering, it suffices to retain only the edges between nodes whose advice values differ by less than $2\delta$. These edges will be referred to as relevant edges. The subgraph $H_1$ can be stored in $O(t\delta +{\delta }^2)$ space if we only keep the relevant edges.

Let $\sigma$ be a topological ordering of $G$ such that $|\sigma (v)-A(v)|\le \delta$ for all nodes $v$. The subgraph $H$ induced by the first $t$ nodes in $\sigma$ has $A(v)\le t+\delta$ and thus is a subgraph of $H_2$. Since $H$ is the first $t$ nodes in a topological ordering, $H$ has no incoming edges and thus is a source subgraph of $H_1$. $◀$

We are now ready to present the algorithm stated in Theorem 2. Given a graph $G$ and an advice function $A$, the algorithm makes a single pass over the input and stores the subgraph $H_1$ induced by all nodes $v$ with $A(v)\le t+3\delta$, along with all relevant edges between them. It then identifies the largest source subgraph of $H_1$ by iteratively expanding $H_3$, starting from the empty set and adding nodes whose advice values are at most $t+\delta$ and whose in-neighbors have all already been included in $H_3$. By Lemma 13, this source subgraph, denoted $H_3$, contains at least $t$ nodes. The algorithm sorts the nodes of $H_3$ and places them at the front of the final topological ordering. Repeating this process $O(n/t)$ times yields a topological ordering of the entire graph $G$.

According to Lemma 12, the space requirement for keeping the subgraph $H_1$ in each step is $O(t\delta +{\delta }^2)$. $O(n)$ space is needed to keep the final topological ordering. Therefore, the total space usage for our streaming algorithm is $O(n+t\delta +{\delta }^2)$. Note that when $t=n$, the algorithm just remembers all relevant edges in a single pass using space $O(n\delta )$.

For each node $v\in V$, the in-degree $d_{in}(v)$ is a random variable that follows a binomial distribution with $\sigma (v)-1$ trials and success probability $p$. By applying Chernoff Bound we have

$◀$

By Lemma 14, $A(v)=d_{in}(v)/p$ is an advice with maximum displacement $O(\sqrt{p^{-1}n\log n})$ with high probability. The calculation of $A$ can be done in one pass and $O(n)$ space by counting the incoming degrees of the nodes.

Using $A(v)=d_{in}(v)/p$ as an advice, Theorem 2 directly gives an $O(n/t)$-pass $O(n+t\delta +{\delta }^2)$-space streaming algorithm where $\delta =O(\sqrt{p^{-1}n\log n})$. Furthermore, notice that the space requirement $O(t\delta +{\delta }^2)$ is for keeping the $O(\delta )$ relevant edges for each of $O(t+\delta )$ nodes in $H_1$. However, in a random graph $𝒢(n,p)$, the probability that all subgraphs that could potentially be chosen as $H_1$ have only $O(pt\delta +p{\delta }^2)$ edges is at least $1-1/n^{\mathrm{\Omega }(1)}$. As a result, the algorithm described in Theorem 2 only uses $O(n/t)$-pass $O(t\sqrt{pn\log n}+n\log n)$-space with probability $1-1/n^{\mathrm{\Omega }(1)}$. Choosing $t$ to be $\sqrt{n{p}^{-1}\log n}$, we have an $O(\sqrt{np/\log n})$-pass $O(n\log n)$-space streaming algorithm.

Combining the above algorithms, we have two topological sort algorithms for random DAGs with almost identical (up to poly-logarithmic improvement) pass and space requirement as [5]. Unlike [5] which requires a chain that goes through all nodes, our algorithms apply to random DAGs $𝒢(n,p)$.

Furthermore, both of our algorithm exhibit trade-offs between pass and space. Also, both of our algorithms and their analysis directly apply to graphs of type $G\cup H$, where $G\sim 𝒢(n,p)$ is a random DAG and $H$ can be any given graph with maximum in-degree $o(\sqrt{np\log n})$ that has the same node set and same node ordering as $G$. The independence number only decreases after adding the edge set of $H$ to $G$, and the advice derived from Lemma 14 is still correct with high probability for sparse $H$.

Let ${\sigma }_H$ be a topological ordering of $H$. Let $S$ be the set of nodes placed at the first $t$ positions of ${\sigma }_H$. Let $G[S]$ be the subgraph $G$ induced by the node set $S$. It suffices to show that the concatenation of any topological ordering of $G[S]$ and $G[V\setminus S]$ is a topological ordering of $G$.

For any node $v\in S$, because all in-neighbors of $v$ in $H$ have to precede $v$ in ${\sigma }_H$. Combining this observation with the definition of $N_t^{-}(v)$, we have that for any node $v\in S$ $N_t^{-}(v)=N^{-}(v)$. Hence, no edges crossing $V\setminus S$ and $S$ in $G$ can be directed from $V\setminus S$ to $S$. Consequently, let ${\sigma }_1$ (resp. ${\sigma }_2$) be the topological ordering of $G[S]$ (resp. $G[V\setminus S]$), the concatenation ${\sigma }_1\circ {\sigma }_2$ will not induce any backward edge. Because $G[S]$ and $G[V\setminus S]$ both are subgraphs of $G$ and $G$ is acyclic, this ensures the existence of ${\sigma }_1$ and ${\sigma }_2$. $◀$

The remaining to show is how to obtain $N_t^{-}(v)$ for all $v$ deterministically in the turnstile model. To achieve this, we use the characteristic polynomials introduced in the study of the set reconciliation problem [19]. The reason not to use ${\mathrm{\ell }}_0$-samplers [15] to obtain $N_t^{-}(v)$, a standard building block for the computations in the dynamic streams, is that our algorithm has to be deterministic here. Unfortunately, we have no idea how to obtain $N_t^{-}(v)$ for all $v$ deterministically in the turnstile stream. To get around with this issue, we note that the nodes with $|N_t^{-}(v)|=t$ are not involved in the computation of the first $t$ positions in ${\sigma }_H$, as shown in the proof of Lemma 15. We maintain the degree of node $v$ using $O(1)$ space to decide whether $v$ has $N_t^{-}(v)=t$ or not. If $N_t^{-}(v)=t$, the edges incident to $v$ does not involve the computation of the first $t$ positions in ${\sigma }_H$, so there is no need to compute $N_t^{-}(v)$; otherwise , we use Lemma 16 to recover $N_t^{-}(v)$ based on the characteristic polynomials used for the set reconciliation [19].

Define the characteristic polynomial of $v$ to be the univariate polynomial

noting that the roots of $P(Z)$ comprise the set $N^{-}(v)$ and the degree of $P_v(v)$ corresponds to $|N^{-}(v)|$. Though at the end of the dynamic input stream, it can be much larger than $t$ in the middle of processing the input. Hence, to recover $N_t^{-}(v)$ using $O(t)$ space we cannot directly maintain $P_v(Z)$. Instead, we maintain the values of $P_v(Z)$ at $t$ distinct points $a_1,a_2,\mathrm{\dots },a_t$ outside the range $[1,n]$. That is, for each $i\in [1,t]$, while processing an edge insertion $(u,v)$ update $P(a_i)$ with $P(a_i)\cdot (a_i-u)$ and while processing an edge deletion $(u,v)$ update $P(a_i)$ with $P(a_i)\cdot {(a_i-u)}^{-1}$, i.e. the multiplicative inverse of $(a_i-u)$. Given the point-value pairs $\{(a_i,P(a_i)):i\in [1,t]\}$, by the standard interpolation [19], if the degree of $P_v(Z)$ less than $t$ at the end of the dynamic input stream (i.e. the given premise ) $P_v(Z)$ can be recovered. $◀$

We are now ready to prove Theorem 3. We use $O(t)$-certificates $n/t$ times, each requiring a single pass and using $O(tn)$ space. Set $k$ as $n/t$, so our algorithm uses $O(n^2/k)$ space as claimed.