Sink-Free Orientations: A Local Sampler with Applications

First, consider (a). If $v$ becomes a sink at any point, then for every $w\in S$ which is a neighbour of $v$, the edge $(w,v)$ is oriented towards $v$. Since $v\notin S$, the edge $(w,v)$ will not be resampled via $v$, and could only be resampled by $w$ becoming a sink. Since $w$ cannot become a sink without resampling $(w,v)$, $v$ will remain a sink. The other implication is obvious.

Now for (b1) and (b2), we first consider the forward implications. For a cycle $C$, every vertex $u\in C$ has an edge pointing outwards towards some $w\in C$ which also has an edge pointing outwards. None of these edges can be resampled without another edge $e\in C$ being resampled first, so no vertex in the cycle will ever become a sink again.

Consider a path $P$ that ends outside of $S$ or in a cycle. Inductively, we see that no edge on this path will be resampled without the edge after it being resampled. The edge connected to the cycle or $S^c$ will not be resampled, since that vertex may never be a sink, so no vertex in $P$ can become a sink.

For the reverse implication, suppose $v$ is eventually not a sink. In that case, there must be some edge $(v,w)$ pointing towards a neighbour $w$. If $w$ is a sink, then $w\notin S$ and we are in case (b2). Otherwise, $w$ is not a sink, and there is an adjacent edge pointing away from $w$, and we repeat this process. As the set of vertices is finite, if vertices considered in this process are all in $S$, then there must be repeated vertices eventually, in which case we are in (b1). $◀$

An illustration of Lemma 6 is given in Figure 1. Based on Lemma 6, we design a local sampling algorithm for determining whether some vertex $v\notin S$ is a sink or not, given in Algorithm 2. We assume that the undirected graph $G=(V,E)$ is stored as an adjacency list where the neighbors of each vertex are arbitrarily ordered. Algorithm 2 takes as input some $S\subseteq V$ and $v\notin S$, returns an indicator variable $x\in \{0,1\}$ such that $𝐏𝐫\left[x=1\right]={\mu }_S(v\text{ is not a sink})$. We treat the path $P$ as a subgraph, and $V(P)$ denotes the vertex set of $P$. When we remove the last vertex from $P$, we remove it and the adjacent edge as well. Informally, Algorithm 2 starts from the vertex $v$, and reveals adjacent edges one by one. If there is any edge pointing outward, say $(v,u)$, we move to $u$ and reveal edges adjacent to $u$. If a sink $w\in S$ is formed, then we mark all adjacent edges of $w$ as unvisited and backtrack. This induces a directed path starting from $v$. We repeat this process until any of the early termination criteria of Lemma 6 is satisfied, in which case we halt and output accordingly.

We claim that there exists a coupling between the execution of Algorithm 1 (with input $G,S$ and output $\sigma$), and $\text{Sample}(G,S,v)$ (with output $x$), such that

The claim implies the lemma because of Lemma 5.

To prove the claim, we first construct our coupling. We use the resampling table idea of Moser and Tardos [39]. For each edge, we associate it with an infinite sequence of independent random variables, each of which is a uniform orientation. This forms the “resampling table”. Our coupling uses the same resampling table for both Algorithm 1 and Algorithm 2. As showed in [39], the execution of Algorithm 1 can be viewed as first constructing this (imaginary) table, and whenever the orientation of an edge is randomised, we just reveal and use the next random variable in the sequence. For Algorithm 2, we reveal the orientation of an edge when its status changes from unvisited to visited in Line 11. We execute Line 14 if the random orientation from the resampling table is $(u,w)$, and otherwise do nothing. Namely, in the latter case, the revealed orientation is $(w,u)$, and we just move forward the “frontier” of that edge by one step in the resampling table. We claim that (2) holds with this coupling.

Essentially, the claim holds since for extremal instances, given a resampling table, the order of the bad events resampled in Algorithm 1 does not affect the output. This fact is shown in [24, Section 4]. (See also [16, Lemma 2.2] for the case of $S=V$.) We can “complete” Algorithm 2 after it finishes. Namely, once Algorithm 2 terminates, we randomise all edges that are not yet oriented, and resample edges adjacent to sinks until there are none, using the same resampling table. Note that at the end of Algorithm 2, some edges may be marked unvisited but are still oriented. Suppose that the output of the completed algorithm is ${\sigma }^{\prime }$, an orientation of all edges. This completed algorithm is just another implementation of Algorithm 1 with a specific order of resampling bad events. Thus the fact mentioned earlier implies that ${\sigma }^{\prime }=\sigma$.

On the other hand, the termination conditions of Algorithm 2 correspond to the cases of Lemma 6. One can show, via a simple induction over the while loop, that at the beginning of the loop, the path $P$ is always a directed path starting from $v$, and all other visited edges point towards the path $P$. This implies that Line 13 corresponds to case (b1) in Lemma 6, Line 5 corresponds to case (b2), and exiting the while loop in Line 3 corresponds to case (a). When Algorithm 2 terminates, we have decided whether or not $v$ is a sink. By Lemma 6, this decision stays the same under ${\sigma }^{\prime }$. As ${\sigma }^{\prime }=\sigma$, (2) holds. $◀$

We then analyse the efficiency of Algorithm 2. The main bottleneck is when there are degree $2$ vertices. It would take $\mathrm{\Omega }({\mathrm{\ell }}^2)$ time to resolve an induced path of length $\mathrm{\ell }$. We then focus on the case where the minimum vertex degree is at least $3$. Note that in this case we have ${\mathrm{\Omega }}_S\ne \mathrm{\varnothing }$ for any $S\subseteq V$. For two distributions $P$ and $Q$ over the state space $\mathrm{\Omega }$, their total variation distance is defined by $d_{\mathrm{TV}}(P,Q):={\sum }_{x\in \mathrm{\Omega }}|P(x)-Q(x)|/2$. For two random variables $x\sim P$ and $y\sim Q$, we also write $d_{\mathrm{TV}}(x,y)$ to denote $d_{\mathrm{TV}}(P,Q)$.

We will need the notion of martingales in the next lemma, so let us briefly recap the relevant notions. A sequence of random variables ${\{X_i\}}_{i\ge 0}$ is a submartingale if $\forall n\ge 0$, and $𝐄\left[X_{n+1}\mid X_0,\mathrm{\dots },X_n\right]\ge X_n$. Submartingales enjoy some nice concentration properties. What we will need is the Azuma-Hoeffding inequality, which states that if ${\{X_i\}}_{i\ge 0}$ is a submartingale and $\left|X_{i+1}-X_i\right|\le c$ for all $i\ge 0$, then for any $n\ge 0$ and $\epsilon >0$,

Then we have the following lemma.

We track the length of the path $P$ during the execution of Algorithm 2. When an edge is chosen in Line 4 and sampled in Line 12 of Algorithm 2, the following happens:

• $\mathrm{■}$

  with probability $1/2$, $w$ is appended to $P$ and the length of $P$ increases by one;

• $\mathrm{■}$

  with probability $1/2$, $\{u,w\}$ is marked as visited, and the length of $P$ decreases by one in the next iteration if and only if $\{u,w\}$ was the last unvisited edge incident to $u$.

Let $X_i$ be the random variable denoting the length of $P$ after the $i$-th execution of Line 12 in Algorithm 2. Then the observation above implies that ${\{X_i\}}_{i\ge 0}$ forms a submartingale. We construct another sequence of random variables ${\{Y_i\}}_{i\ge 0}$ modified from ${\{X_i\}}_{i\ge 0}$ as follows:

• $\mathrm{■}$

  $Y_0=X_0=1$.

• $\mathrm{■}$

  At the $i$-th execution of Line 12 in Algorithm 2:

  • –

    if $\{u,w\}$ is the only unvisited edge incident to $u$, set $Y_{i+1}=X_{i+1}-X_i+Y_i$,

  • –

    otherwise, set $Y_{i+1}=X_{i+1}-X_i+Y_i-1/2$.

It can be verified that the sequence ${\{Y_i\}}_{i\ge 0}$ is a martingale.

Note that $X_i-Y_i=X_{i-1}-Y_{i-1}+c_i$ where $c_i=0$ if $\{u,w\}$ is the only unvisited edge incident to $u$ at the $i$-th execution of Line 12 in Algorithm 2, and $c_i=1/2$ otherwise. Then we can write $X_i-Y_i$ as

For any $i$ such that $c_i=0$, let $i^{\prime }$ be the last index such that $c_{i^{\prime }}=0$, or $i^{\prime }=0$ if no such $i^{\prime }$ exists. Since the minimum degree of $G$ is at least $3$, when we append any vertex $u$ to $P$, there are at least two unvisited edges incident to $u$. It implies that there must be some $j$ such that and $c_j=1/2$. Thus $X_i-Y_i={\sum }_{k=1}^i{c}_k\ge i/4$. $\mathrm{⊲}$

Next we show that if Algorithm 2 doesn’t terminate after $32\ln (33/\epsilon )$ steps, with high probability the length of the path will not return to $0$. As ${\{Y_i\}}_{i\ge 0}$ is a martingale and $\left|Y_{i+1}-Y_i\right|\le 1$ for all $i\ge 0$, the Azuma–Hoeffding inequality, namely (3), implies that, for any $T>0$ and $C>0$,

Thus,

where the first inequality is by Claim 9, and the last inequality is by plugging $C=T/4$ into (4). Then, we have

To finish the proof, we couple $x$ and $x^{\prime }$ by the same execution of Algorithm 2. Thus, if it terminates within $32\ln (33/\epsilon )$ executions of Line 12, then $x=x^{\prime }$ with probability $1$. If not, (5) implies that $x=0$ with probability at most $\epsilon$. As we always output $x=1$ in this case, $x^{\prime }\ne x$ with probability at most $\epsilon$, which finishes the proof. $◀$

Note that Lemma 8 does not require ${\mathrm{\Omega }}_S\ne \mathrm{\varnothing }$. This is because it is implied by the minimum degree requirement. This implication is an easy consequence of the symmetric Shearer’s bound. It is also directly implied by Lemma 10 which we show next.

Lemma 8 implies the first part of Theorem 1. For the second part, we will need a modified version of Algorithm 2 to sample from the marginal distributions of the orientation of edges. This is given in Algorithm 3. It takes as input a subset of vertices $S\subseteq V$ and an edge $e\in E$, then outputs a random orientation ${\sigma }_e$ following the marginal distribution induced from ${\mu }_S$ on $e$. The differences between Algorithm 2 and Algorithm 3 are:

• $\mathrm{■}$

  In Algorithm 2, the number of vertices in $P$ is initialised as $|V(P)|=1$, while in Algorithm 3, it is initialised as $|V(P)|=2$.

• $\mathrm{■}$

  Algorithm 2 can terminate when $|V(P)|=1$ while Algorithm 3 can not terminate due to (a) of Lemma 6 unless $x$ or $y$ are not in $S$.

The correctness of Algorithm 3 is due to a coupling argument similar to Lemma 7. We couple Algorithm 1 and Algorithm 3 by using the same resampling table. By the same argument as in Lemma 7, given the same resampling table, the orientation of $e$ is the same in the outputs of both Algorithm 1 and Algorithm 3. Thus, ${\sigma }_e$ follows the desired marginal distribution by Lemma 5. As for efficiency, we notice that the same martingale argument as in Lemma 8 applies to the length of $P$ as well. Early truncation of the edge sampler only incurs a small error. This finishes the proof of Theorem 1.

By (1), we just need to $\epsilon /(2n)$-approximate ${\mu }_{V_{i-1}}(v_i\text{ is not a sink})$ for each $i$ to $\epsilon$-approximate $|{\mathrm{\Omega }}_V|$, the number of sink-free orientations to $G$. The only random choice Algorithm 2 makes is Line 12. In view of Lemma 8, we enumerate the first $32\ln (132n/\epsilon )$ random choices of Algorithm 2, and just output $1$ if the algorithm does not terminate by then. Let the estimator be the average of all enumeration. Note that Lemma 10 implies that ${\mathrm{\Omega }}_{V_i}\ne \mathrm{\varnothing }$ for any $i$. Then, Lemmas 7 and 8 imply that the estimator is an $\epsilon /(4n)$ additive approximation. By Lemma 10, it is also an $\epsilon /(2n)$ relative approximation, which is what we need.

For the running time, there are $n$ marginals, it takes $\exp (32\ln (132n/\epsilon ))$ enumerations for each marginal probability, and each enumeration takes at most $O(\ln (132n/\epsilon ))$ time. Therefore, the overall running time is bounded by $O(n{(n/\epsilon )}^{32}\log (n/\epsilon ))$. $◀$

We use (1) again. Denote ${\nu }_i={\mu }_{V_{i-1}}(v_i\text{ is not a sink})$ and $\nu ={\prod }_{i=1}^n{\nu }_i$. Let ${\tilde{X}}_i:=\frac{1}{n}{\sum }_{t=1}^n{x}_{i,t}^{\prime }$ be the average of $n$ independent samples from Algorithm 2 truncated after $32\ln (33\times 12n/\epsilon )$ executions of Line 12. Let $\tilde{X}:={\prod }_{i=1}^n{\tilde{X}}_i$ be an estimator for $\nu$.

For any $i$ and $t$, let ${\tilde{\nu }}_i$ be the expectation of $x_{i,t}^{\prime }$ (note that it does not depend on $t$). By Lemmas 7 and 8, $\left|{\tilde{\nu }}_i-{\nu }_i\right|\le \frac{\epsilon }{12n}$. By Lemma 10, $1-\frac{\epsilon }{6n}\le \frac{{\tilde{\nu }}_i}{{\nu }_i}\le 1+\frac{\epsilon }{6n}$. Let $\tilde{\nu }={\prod }_{i=1}^n{\tilde{\nu }}_i$ so that $𝐄\left[\tilde{X}\right]=\tilde{\nu }$. Then, as ,

We bound $\mathrm{𝐕𝐚𝐫}\left[{\tilde{X}}_i\right]$ and $\mathrm{𝐕𝐚𝐫}\left[\tilde{X}\right]$ next. First,

as each $x_{i,t}^{\prime }$ is an indicator variable. Then,

To further reduce the variance, let $\widehat{X}$ be the average of $N$ independent samples of $\tilde{X}$, where $N:=\lceil 36\times 54/{\epsilon }^2\rceil$. Then, $\mathrm{𝐕𝐚𝐫}[\widehat{X}]\le \frac{\mathrm{𝐕𝐚𝐫}\left[\tilde{X}\right]}{N}$. By Chebyshev’s bound, we have

Thus with probability at least $\frac{3}{4}$, we have that $(1-\frac{\epsilon }{3})\tilde{\nu }\le \widehat{X}\le (1+\frac{\epsilon }{3})\tilde{\nu }$. By (6), when this holds, $(1-\epsilon )\nu \le \widehat{X}\le (1+\epsilon )\nu$. It is then easy to have an $\epsilon$-approximation of $\left|{\mathrm{\Omega }}_V\right|$.

For the running time, each sample $x_{i,t}^{\prime }$ takes $O(\log (n/\epsilon ))$ time. We draw $n$ samples for each of the $n$ vertices, and we repeat this process $N=O({\epsilon }^{-2})$ times. Thus, the total running time is bounded by $O({(n/\epsilon )}^2\log (n/\epsilon ))$. $◀$

For Corollary 3, we need the second part of Theorem 1 and Algorithm 3. In addition, some extra care for the self-reduction in the overall sampling algorithm is required.

We sequentially sample the orientation of edges in $G$ (approximately) from its conditional marginal distribution. Suppose we choose an edge $e=\{u,v\}$, and the sampled orientation is $(u,v)$. Then, we can remove $e$ from the graph, and let $S\leftarrow S\setminus \{u\}$. The conditional distribution is effectively the same as ${\mu }_S$ in the remaining graph.

One subtlety here is that doing so may create vertices of degree $\le 2$. To cope with this, we keep sampling edges adjacent to one vertex in $S$ as much as possible before moving on to the next. Suppose the current focus is on $v$. We use SampleEdge to sample the orientation of edges adjacent to $v$ one at a time until either $v$ is removed from $S$ or the degree of $v$ becomes $1$. In the latter case, the leftover edge must be oriented away from $v$, which also results in removing $v$ from $S$. Note that, when either condition holds, the last edge sampled is oriented as $(v,u)$ for some neighbour $u$ of $v$. We then move our focus to $u$ if $u\in S$, and move to an arbitrary vertex in $S$ otherwise. The key property of choosing edges this way is that, whenever $\text{SampleEdge}(G,S,e)$ is invoked, there can only be at most one vertex of degree $2$ in $S$, and if it exists, it must be an endpoint of $e$. If all vertices are removed from $S$, we finish by simply outputing a uniformly at random orientation of the remaining edges.

To maintain efficiency, we truncate $\text{SampleEdge}(G,S,e)$ in each step of the sampling process. More specifically, for some constant $C$, we output the first edge of $P$ once the number of executions of Line 15 in Algorithm 3 exceeds $C\ln (m/\epsilon )$. We claim that there is a constant $C$ such that the truncation only incurs an $\epsilon /m$ error in total variation distance between the output and the marginal distribution. This is because the same martingale argument as in Lemma 8 still applies. Note that if $P$ visits any vertex not in $S$, the algorithm immediately terminates. Thus degrees of vertices not in $S$ do not affect the argument. Moreover, the only degree $2$ vertex in $S$, say $x$, is adjacent to the first edge $e=\{x,y\}$ of $P$. If $e$ is initialised as $(x,y)$, then when $P$ returns to $x$, the algorithm immediately terminates. Otherwise $e$ is initialised as $(y,x)$, in which case there is no drift in the first step of $P$. Thus, as long as we adjust the constant to compensate the potential lack of drift in the first step, the martingale argument in Lemma 8 still works and the claim holds. As the truncation error is $\epsilon /m$, we may couple the untruncated algorithm with the truncated version, and a union bound implies that the overall error is at most $\epsilon$.

As we process each edge in at most $O(\log (m/\epsilon ))$ time, the overall running time is then $O(m\log (m/\epsilon ))$. This finishes the proof of the fast sampling algorithm. $◀$