The input $G$ is given in the insertion-only streaming model. That is, we know $V$ in advance, and the set $E$ is being revealed one edge at a time. For each edge $\left(u,v\right)\in E$ that we get, we need to assign a direction (i.e. an orientation), meaning to decide that it either points to $u$ or to $v$ . When $u$ points to $v$ we denote it by $u\rightarrow v$ . Note that when we assign a direction to a new edge, we may as well update the orientation of previously seen edges. When the stream ends, we left with a directed version of $G$ , denote it $\hat{G}=\left(V,\hat{E}\right)$ .

We are interested in two metrics: the first is the outgoing degree bound, which is defined by the term $$deg\left(\hat{G}\right):=\max_{v\in V}deg_{out}\left(v;\hat{G}\right)$$ where $deg_{out}(v;\hat{G}):=\left|\left\{ u\in V\mid v\rightarrow u\right\} \right|$ is the number of $v$ ’s neighbors which $v$ points to, in the oriented graph $\hat{G}$ .

The second metric is a bound on the orientation cost for a single step of the stream. That is, a bound on the number of edge updates for every time a new edge is being revealed.

Due to the fact that $G$ is acyclic, we know it is actually a collection of one or more trees, then there exists an orientation $\hat{G}$ in which $deg\left(\hat{G}\right)\le1$ (think that each node points to its parent in its corresponding tree).

Obviously, that update rule has constant orientation cost (in particular it never change the orientations of previous edges). However, the outgoing degree bound is $\mathcal{O}\left(\log n\right)$ . To prove that, consider some arbitrary vertex $v$ . We increase its outgoing degree by $1$ when we make it points to another larger connected component. So every time the outgoing degree of $v$ increases by $1$ , the size of its connected component is at least doubled. Since we have $n$ vertices, we cannot double that size more than $\log_{2}n$ times.

Upon receiving $e_{i}=\left(u,v\right)$ , orient it $v\rightarrow u$ . Then, if the outgoing degree of $v$ exceeds $4$ , we apply $makeSink\left(v\right)$ . This procedure will flip the orientation of any outgoing edge of $v$ . Next, check any neighbor $u$ that was affected by this change, and apply $makeSink\left(u\right)$ if it has more than $4$ outgoing edges. This process continues recursively until no orientation is changed.

Interesting question that immediately pops to mind is, why this process of recursive updates eventually terminates?

To see that infinite oscillation is impossible, consider some optimal orientation of $G$ , denote it $\hat{G}^{*}$ , in which $deg\left(\hat{G}^{*}\right)\le1$ . Suppose that $e_{i}=\left(v,u_{1}\right)$ was revealed to the stream, and let $u_{1},u_{2},...$ be the chain of vertices that we applied $makeSink\left(\cdot\right)$ to, after orienting it. Denote by $\phi_{k}$ the number of edges in $G_{i}=\left(V,E_{i}\right)$ that don’t agree with $\hat{G}^{*}$ , after applying $makeSink\left(\cdot\right)$ on $u_{1},..,u_{k}$ . So for example, $\phi_{0}$ is the number of conflicting edges right after we inserted $e_{i}$ but before we start the recursive fixing process, and $\phi_{1}$ is the number of conflicting edges after we flip all the outgoing edges of $u_{1}$ , and so on.

We will show that $\phi_{0},\phi_{1},..$ is a strictly decreasing series, and since $\phi_{k}$ cannot be negative, that series must terminates. Fix some $\phi_{k}$ , which is the number of edges conflicting with $\hat{G}^{*}$ before applying $makeSink\left(u_{k+1}\right)$ . In that moment, $deg_{out}\left(u_{k+1}\right)>4$ , but in the optimal orientation it should be at most $1$ , which means that at least $4$ of $u_{k+1}$ ’s outgoing edges have wrong orientations. So applying $makeSink\left(u_{k+1}\right)$ adding up to one conflicting edge, but on the other hand, fixing the orientation of at least $4$ other edges, thus the total number of conflicting edges with $\hat{G}^{*}$ decreased by at least $3$ , i.e. $\phi_{k}\ge3+\phi_{k+1}$ .

It is immediate that this algorithm yields an orientation with outgoing degree bound of $4$ . We now move to show that the amortize orientation cost is also constant. To show that we will use the accounting method, in which we assign positive and negative values to different operations that we perform during processing the stream. As long as those values are constants, if in every step of the stream the aggregated value is non-negative, then we may conclude that the amortize cost per operation is also constant. So suppose that the action of inserting a new edge has a value of $+2$ , and flipping orientation of an existing edge has a value of $-1$ . We first prove the following claim.

It is left to show that at any point in time, the total value of previous operation is non negative. The following claim prove that.