A nearly-mlogn time solver for SDD linear systems

Introduction

Solvers for symmetric diagonally dominant (SDD)A system $Ax=b$ is SDD when $A$ is symmetric and $A_{ii}\geq\sum_{j\not=i}|A_{ij}|$. systems are a crucial component of the fastest known algorithms for a multitude of problems that include (i) Computing the first non-trivial (Fiedler) eigenvector of the graph, with well known applications to the sparsest-cut problem [Fie73, ST96, Chu97]; (ii) Generating spectral sparsifiers that also act as cut-preserving sparsifiers [SS08]; (iii) Solving linear systems derived from elliptic finite element discretizations of a significant class of partial differential equations [BHV04]; (iv) Generalized lossy flow problems [SD08]; (v) Generating random spanning trees [KM09]; (vi) Faster maximum flow algorithms [CKM+11]; and (vii) Several optimization problems in computer vision [KMST09b, KMT11] and graphics [MP08, JMD+07].

The $O(\log n)$ speedup of the SDD solver applies to all algorithms listed above, and we believe that it will prove to be quite important in practice, as applications of SDD solvers frequently involve massive graphs [Ten10].

The key to all known near-linear work SDD solvers is spectral graph sparsification, which on a given input graph $G$ constructs a sparser graph $H$ such that $G$ and $H$ are ‘spectrally similar’ in the condition number sense, defined in Section 2. Spectral graph sparsification can be seen as a significant strengthening of the notion of cut-preserving sparsification [BK96].

The new solver follows the framework of recursive preconditioned Chebyshev iterations [ST06, KMP10a]. The iterations are driven by a so-called preconditioning chain $\{G_{1},H_{1},G_{2},H_{2},\ldots,\}$ of graphs, where $H_{i}$ is a spectral sparsifier for $G_{i}$ and $G_{i+1}$ is generated by contracting $H_{i}$ via a greedy elimination of degree 1 and 2 nodes. The total work of the solver includes the time for constructing the chain, and the work spent on actual iterations which is a function on the preconditioning quality of the chain. The preconditioning quality of the chain in turn depends on the guarantees of the sparsification algorithm.

The incremental sparsification algorithm in [KMP10a] computes and keeps in $H$ a properly scaled copy of a low-stretch spanning tree of $G$, and adds to $H$ a number of off-tree samples from $G$. The key enabling observation in the new analysis is that the total stretch of the off-tree edges is essentially invariant under sparsification. In other words, the total stretch of the off-tree edges in $H_{i}$ is at most equal to that $G_{i}$. The total stretch is invariable under the graph contraction process as well. The elimination process that generates $G_{i+1}$ from $H_{i}$ naturally generates a spanning tree for $G_{i+1}$. The total stretch of the off-tree edges in $G_{i+1}$ is at most equal to that in $H_{i}$. This effectively allows us to compute only one low-stretch spanning tree for the first graph in the chain, and keep the same tree for the rest of the chain. This is a significant departure from previous constructions, where a low-stretch spanning tree had to be calculated for each $G_{i}$.

In order to analyze this new chain we view the graphs $H_{i}$ as multi-graphs or graphs of samples. In the sampling procedure that generates $H_{i}$, some off-tree edges of $G_{i}$ can be sampled multiple times, and so $H_{i}$ is naturally a multi-graph, where the weight of a ‘traditional’ edge $e$ is split among a number of parallel multi-edges with the same endpoints. The progress of the overall sparsification in the chain is then monitored in terms of the number of multi-edges in the $H_{i}$’s. In other words, when the algorithm appears to be stagnated in terms of the edge count in the $G_{i}$’s, progress is still happening by ‘thinning’ the off-tree edges. The details are given in Section 4.

Background and notation

A matrix $A$ is symmetric diagonally dominant if it is symmetric and $A_{ii}\geq\sum_{j\not=i}|A_{ij}|$. It is well understood that any linear system whose matrix is SDD is easily reducible to a system whose matrix is the Laplacian of a weighted graph with positive weights [Gre96]. The Laplacian matrix of a graph $G=(V,E,w)$ is the matrix defined as

There is a one-to-one correspondence between graphs and Laplacians which allows us to extend some algebraic operations to graphs. Concretely, if $G$ and $H$ are graphs, we will denote by $G+H$ the graph whose Laplacian is $L_{G}+L_{H}$, and by $cG$ the graph whose Laplacian is $cL_{G}$.

[Spectral ordering of graphs] We define a partial ordering $\preceq$ of graphs by letting

If there is a constant $c$ such that $G\preceq cH\preceq\kappa G$, we say that the condition of the pair $(G,H)$ is $\kappa$. In our proofs we will find useful to view a graph $G=(V,E,w)$ as a graph with multiple edges.

[Graph of samples] A graph $G=(V,E,w)$ is called a graph of samples, when each edge $e$ of weight $w_{e}$ is considered as a sum of a set ${\cal L}_{e}$ of parallel edges, each of weight $w_{l}=w_{e}/|{\cal L}_{e}|$. When needed we will emphasize the fact that a graph is viewed as having parallel edges, by using the notation $G=(V,{\cal L},w).~{}~{}\bullet$

[Stretch of edge by tree] Let $T=(V,E_{T},w)$ be a tree. For $e\in E_{T}$ let $w^{\prime}_{e}=1/{w_{e}}$. Let $e$ be an edge not necessarily in $E_{T}$, of weight $w_{e}$. If the unique path connecting the endpoints of $e$ in $T$ consists of edges $e_{1}\dots e_{k}$, the stretch of $e$ by $T$ is defined to be

A key to our results is viewing graphs as resistive electrical networks [DS00]. More concretely, if $G=(V,{\cal L},w)$ each $l\in{\cal L}$ corresponds to a resistor of capacity $1/w_{l}$ connecting the two endpoints of ${\cal L}$. We denote by $R_{G}(e)$ the effective resistance between the endpoints of $e$ in $G$. The effective resistance on trees is easy to calculate; we have $R_{T}(e)=\sum_{i=1}^{k}1/w(e_{i})$. Thus

We extend the definition to $l\in{\cal L}_{e}$ in the natural way

and note that $stretch_{T}(e)=\sum_{l\in{\cal L}_{e}}stretch_{T}(l)$.

This definition can also be extended to set of edges. Thus $stretch_{T}(E)$ denotes the vector of stretch values of all edges in $E$. We also let $stretch_{T}(G)$ denote the vector of stretch for edges in $E_{G}-E_{T}$.

[Total Off-Tree Stretch] Let $G=(V,E_{G},w)$ be a graph, $T=(V,E_{T},w)$ be a spanning tree of $G$. We define

Incremental Sparsifier

In their remarkable work [SS08], Spielman and Srivastava analyzed a spectral sparsification algorithm based on a simple sampling procedure. The sampling probabilities were proportional to the effective resistances $R_{G}(e)$ of the edges on the input graph $G$. Our solver in [KMP10a] was based on an incremental sparsification algorithm which used upper bounds on the effective resistances, that are more easily calculated. In this section we give a more careful analysis of the incremental sparsifier algorithm given in [KMP10a].

We start by reviewing the basic Sample procedure. The procedure takes as input a weighted graph $G$ and frequencies $p^{\prime}_{e}$ for each edge $e$. These frequencies are normalized to probabilities $p_{e}$ summing to $1$. It then picks in $q$ rounds exactly $q$ samples which are weighted copies of the edges. The probability that given edge $e$ is picked in a given round is $p_{e}$. The weight of the corresponding sample is set so that the expected weight of the edge $e$ after sampling is equal to its actual weight in the input graph. The details are given in the following pseudocode.

The following Theorem characterizes the quality of $G^{\prime}$ as a spectral sparsifier for $G$ and it was proved in [KMP10a].

(Oversampling) Let $G=(V,E,w)$ be a graph. Assuming that $p^{\prime}_{e}\geq w_{e}R_{G}(e)$ for each edge $e\in E$, and $\xi\in\Omega(1/n)$, the graph $G^{\prime}=\textsc{Sample}(G,p^{\prime},\xi)$ satisfies

Suppose we are given a spanning tree $T$ of $G=(V,E,w)$. The incremental sparsification algorithm of [KMP10a] was based on two key observations: (a) By Rayleigh’s monotonicity law [DS00] we have $R_{T}(e)\geq R_{G}(e)$ because $T$ is a subgraph of $G$. Hence the numbers $stretch_{T}(e)$ satisfy the condition of Theorem 3.1 and they can be used in Sample. (b) Scaling up the edges of $T$ in $G$ by a factor of $\kappa$ gives a new graph $G^{\prime}$ where the stretches of the off-tree are smaller by a factor of $\kappa$ relative to those in $G$. This forces Sample (when applied on $G^{\prime}$) to sample more often edges from $T$, and return a graph with a smaller number of off-tree edges. In other words, the scale-up factor $\kappa$ allows us to control the number of off-tree edges. Of course this comes at the cost of incurring condition $\kappa$ between $G$ and $G^{\prime}$.

In this paper we follow the same approach, but also modify IncrementalSparsify so that the output graph is a union of a copy of $T$ and the off-tree samples picked by Sample. To emphasize this, we will denote the edge set of the output graph by $E_{T}\cup{\cal L}$. The details are given in the following algorithm.

Let $G$ be a graph with $n$ vertices and $m$ edges and $T$ be a spanning tree of $G$. Then for $\xi\in\Omega(1/n)$, $\textsc{IncrementalSparsify}(G,E_{T},\kappa,\xi)$ computes with probability at least $1-2\xi$ a graph $H=(V,E_{T}\cup{\cal L})$ such that

$|{\cal L}|\leq 2\hat{t}C_{S}\log t\log(1/\xi)$

We now bound the number $|{\cal L}|$ of off-tree samples drawn by Sample. For the number $t$ used in Sample we have $t=\hat{t}+n-1$ and $q=C_{s}t\log t\log(1/\xi)$ is the number samples drawn by Sample. Let $X_{i}$ be a random variable which is $1$ if the $i^{th}$ sample picked by Sample is a non-tree edge and otherwise. The total number of non-tree samples is the random variable $X=\sum_{i=1}^{q}X_{i}$, and its expected value can be calculated using the fact $Pr(X_{i}=1)=\hat{t}/t$:

Step 12 assures that $H$ does not contain more than $2E[X]$ edges so the claim about the number of off-tree samples is automatically satisfied. A standard form of Chernoff’s inequality is:

Letting $\delta=1$, and since $\hat{t}>1,C_{S}>2$ we get $Pr[X>2E[X]]<(exp({-2}{E[X]})<1/n^{2}$. So, the probability that the algorithm returns a FAIL is at most $1/n^{2}$. It follows that the probability that an output of Sample satisfies inequality 3.1 and doesn’t get rejected by IncrementalSparsify is at least $1-\xi-1/n^{2}$.

We now concentrate on the edges of $T$. Any fixed edge $e\in E_{T}$ is sampled with probability $1/t$ in Sample. Let $X_{e}$ denote the random variable equal to number of times $e$ is sampled. Since there are $q=C_{s}t\log t\log(1/\xi)$ iterations of sampling, we have $E[X_{e}]=q/t\geq C_{s}\log{n}$. By the Chernoff inequalities above, setting $\delta=1/2$ we get that

Overall, the probability that the output $H$ of IncrementalSparsify satisfies the claim about the condition number is at least $1-\xi-2/n^{2}\geq 1-2/\xi$.

Since the weights of the tree-edges $E_{T}$ in $H$ are different than those in $G$, we will use $T_{H}$ to denote the spanning tree of $H$ whose edge-set is $E_{T}$. We now show a key property of IncrementalSparsify.

(Uniform Sample Stretch) Let $H=(V,E_{T}\cup{\cal L},w):=\textsc{IncrementalSparsify}(G,E_{T},\kappa,\xi)$, and $C_{S},t$ as defined in Theorem 3.2. For all $l\in{\cal L}$, we have

Proof Let $T^{\prime}=\kappa T$. Consider an arbitrary non-tree edge $e$ of $G^{\prime}$ defined in Step 5 of IncrementalSparsify. The probability of it being sampled is:

where $R_{T^{\prime}}(e)$ is the effective resistance of $e$ in $T^{\prime}$ and $t=n-1+s_{T^{\prime}}(G^{\prime})=n-1+stretch_{T}(G)/\kappa$ is the total stretch of all $G^{\prime}$ edges by $T^{\prime}$. If $e$ is picked, the corresponding sample $l$ has weight $w_{e}$ scaled up by a factor of $1/p^{\prime}_{e}$, but then divided by $q$ at the end. This gives

So the stretch of $l$ with respect to $T^{\prime}$ is independent from $w_{e}$ and equal to

Finally note that $T_{H}=3T^{\prime}$. This proves the claim. $\blacksquare$

Solving using Incremental Sparsifiers

We follow the framework of the solvers in [ST06] and [KMP10a] which consist of two phases. The preconditioning phase builds a chain of graphs ${\cal C}=\{G_{1},H_{1},G_{2},\ldots,H_{d}\}$ starting with $G_{1}=G$, along with a corresponding list of positive numbers ${\cal K}=\{\kappa_{1},\ldots,\kappa_{d-1}\}$ where $\kappa_{i}$ is an upper bound on the condition number of the pair $(G_{i},H_{i})$. The process for building ${\cal C}$ alternates between calls to a sparsification routine (in our case IncrementalSparsify) which constructs $H_{i}$ from $G_{i}$ and a routine GreedyElimination which constructs $G_{i+1}$ from $B_{i}$, by applying a greedy elimination of degree $1$ and $2$ nodes. The preconditioning phase is independent from the $b$-side of the system $L_{A}x=b$. The solve phase passes $\cal C$, $b$ and a number of iterations $t$ (depending on a desired error $\epsilon$) to the recursive preconditioning algorithm R-P-Chebyshev, described in [ST06] or in the appendix of [KMP10a].

We first give pseudocode for GreedyElimination, which deviates slightly from the standard presentation where the input and output are the two graphs $G$ and $\hat{G}$, to include a spanning tree of the graphs.

Of course we still need to prove that the output $\hat{T}$ is indeed a spanning tree. We prove the claim in the following Lemma that also examines the effect of GreedyElimination to the total stretch of the off-tree edges.

Let $(\hat{G},\hat{T}):=\textsc{GreedyElimination}(G,T)$. The output $\hat{T}$ is a spanning tree of $\hat{G}$, and

Proof We prove the claim inductively by showing that it holds for all the pairs $(\hat{G}_{i},\hat{T}_{i})$ throughout the loop, where $(\hat{G}_{i},\hat{T}_{i})$ denotes the pair $(\hat{G},\hat{T})$ after the $i^{th}$ elimination during the course of the algorithm. The base of the induction is the input pair $(G,T)$ and so the claim holds for it.

When a degree-$1$ node gets eliminated the corresponding edge is necessarily in $E_{\hat{T}}$ by the inductive hypothesis. Its elimination doesn’t affect the stretch of any off-tree edge. So, it is clear that if $(\hat{G}_{i},\hat{T}_{i})$ satisfy the claim then after the elimination of a degree-$1$ node $(\hat{G}_{i+1},\hat{T}_{i+1})$ will also satisfy the claim.

By the inductive hypothesis about $\hat{T}_{i}$ if $(v,u_{1}),(v,u_{2})$ are eliminated then at least one of the two edges must be in ${\hat{T}_{i}}$. We first consider the case where one of the two (say $(v,u_{2})$) is not in $\hat{T}_{i}$. Both $u_{1}$ and $u_{2}$ must be connected to the rest of $\hat{G}_{i}$ through edges of $\hat{T}_{i}$ different than $(u_{1},v)$ and $(v,u_{2})$. Hence $\hat{T}_{i+1}$ is a spanning tree of $\hat{G}_{i+1}$. Observe that we eliminate at most two non-tree edges from $\hat{G_{i}}$: $(v,u_{2})$ and $(u_{1},u_{2})$ with corresponding weights $w(v,u_{2})$ and $w^{\prime\prime}$ respectively. Let $\hat{T}[e]$ denote the unique tree-path between the endpoints of $e$ in $\hat{T}$. The contribution of the two eliminated edges to the total stretch is equal to

The two eliminated edges get replaced by the edge $(u_{1},u_{2})$ with weight $w^{\prime}+w^{\prime\prime}$. The contribution of the new edge to the total stretch in $\hat{G}_{i+1}$ is equal to

We have $R_{\hat{T}_{i+1}}((u_{1},u_{2}))=R_{\hat{T}_{i}}((u_{1},u_{2}))<R_{\hat{T}_{i}}((v,u_{2}))$ since all the edges in the tree-path of $(u_{1},u_{2})$ are not affected by the elimination. We also have $w(v,u_{2})>w^{\prime}$, hence $s_{1}>s_{2}$. The claim follows from the fact that no other edges are affected by the elimination, so

We now consider the case where both edges eliminated in Steps 5-13 are in $\hat{T}_{i}$. It is clear that $\hat{T}_{i+1}$ is a spanning tree of $\hat{G}_{i+1}$. Consider any off-tree edge $e$ not in $\hat{T}_{i+1}$. One of its two endpoints must be different than either $u_{1}$ or $u_{2}$, so its endpoints and weight $w_{e}$ are the same in $\hat{T}_{i}$. However the elimination of $v$ may affect the stretch of $e$ if $\hat{T}_{i}[e]$ goes through $v$. Let

Since individual edge stretches only decrease, the total stretch also decreases and the claim follows. $\blacksquare$

A preconditioning chain of graphs must certain properties in order to be useful with R-P-Chebyshev.

[Good Preconditioning Chain] Let ${\cal C}=\{G=G_{1},H_{1},G_{2},\ldots,G_{d}\}$ be a chain of graphs and ${\cal K}=\{\kappa_{1},\kappa_{2},\ldots,\kappa_{d-1}\}$ a list of numbers. We say that $\{{\cal C,K}\}$ is a good preconditioning chain for $G$, if there exist a list of numbers $\mathcal{U}=\{\mu_{1},\mu_{2},\ldots\mu_{d}\}$ such that:

$G_{i}\preceq H_{i}\preceq\kappa_{i}G_{i}$.

$G_{i+1}=\textsc{GreedyElimination}(H_{i})$.

$\mu_{i}$ is at least the number of edges in $G_{i}$.

$\mu_{1},\mu_{2}\leq m$, where $m$ is the number of edges in $G=G_{1}$.

$\mu_{i}/\mu_{{i+1}}\geq\lceil c_{r}\sqrt{\kappa_{i}}\rceil$ for all $i>1$ where $c_{r}$ is an explicitly known constant.

$\mu_{d}$ is a smaller than a fixed constant.

Spielman and Teng [ST06] analyzed the recursive preconditioned Chebyshev iteration R-P-Chebyshev that can be found in the appendix of [KMP10a] and showed that the solution of an arbitrary SDD system can be reduced to the computation of a good preconditioning chain. This is captured more concretely by the following Lemma which is adapted from Theorem 5.5 in [ST06].

Let $A$ be an SDD matrix with $A=L_{G}+D$ where $D$ is a diagonal matrix with non-negative elements, and $L_{G}$ is the Laplacian of a graph $G$. Given a good preconditioning chain $\{{\cal C,K}\}$ for $G$, a vector ${x}$ such that $||{x}-A^{+}b||_{A}<\epsilon||A^{+}b||_{A}$ can be computed in time ${O}(m\sqrt{\kappa_{1}}+m\sqrt{\kappa_{1}\kappa_{2}})\log(1/\epsilon))$.

Before we proceed to the algorithm for building the chain we will need a modified version of a result by Abraham, Bartal, and Neiman [ABN08], which we prove in Section 5.

There is an algorithm LowStretchTree that, given a graph $G=(V,E,w)$, outputs a spanning tree $T$ of $G$ such that

The algorithm runs in $O(m\log{n}+n\log{n}\log\log{n})$ time.

Algorithm BuildChain generates the chain of graphs.

It remains to show that our algorithm indeed generates a good preconditioning chain.

Proof Let $l_{1}$ denote the number of edges in $G$ and $l_{i}=|{\cal L}_{i}|$ the number of off-tree samples for $i>1$. We prove by induction on $i$ that:

$stretch_{T_{i+1}}(G_{i+1})\leq l_{i}/(C_{S}\log t_{i}\log(1/(p\xi)))=\kappa_{c}\hat{t}_{i}$, where $C_{S},\hat{t}_{i}$ and $t_{i}$ are as defined in Theorem 3.2 for the graph $G_{i}$.

We now exhibit the list of numbers $\mathcal{U}=\{\mu_{1},\mu_{2}\ldots\mu_{d}\}$ required by Definition 4.2. A key property of GreedyElimination is that if $G$ is a graph with $n-1+j$ edges, the output $\hat{G}$ of GreedyElimination$(G)$ has at most $2j-2$ vertices and $3j-3$ edges [ST06]. Hence the graph $G_{i+1}$ returned by $\textsc{GreedyElimination}(H_{i})$ has at most $6l_{i}/\kappa_{c}$ edges. Therefore setting $\mu_{i}=6l_{i}/\kappa_{c}$ gives an upper bound on the number of edges in $G_{i+1}$ and:

At the same time we have $G_{i}\preceq H_{i}\preceq 54\kappa_{c}G_{i}$. By picking $\kappa_{c}$ to be large enough we can satisfy all the requirements for the preconditioning chain.

The probability that $H_{i}$ has the above properties is by construction at least $1-p/(2\log n)$. Since there are at most $2\log n$ levels in the chain, the probability that the requirements hold for all $i$ is then at least

Combining Lemmas 4.3 and 4.5 proves our main Theorem.

Speeding Up Low Stretch Spanning Tree Construction

We improve the running time of the algorithm for finding a low stretch spanning tree given in [EEST05, ABN08] by a factor of $\log{n}$, while retaining the $O(m\log{n}\log\log^{3}{n})$ bound on total stretch given in [ABN08]. Specifically, we claim the following Theorem.

There is an algorithm LowStretchTree that given a graph $G=(V,E,w)$, outputs a spanning tree $T$ of $G$ in $O(m\log{n}+n\log{n}\log\log{n})$ time such that

We first show that if the graph only has $k$ distinct edge weights, Dijkstra’s algorithm can be modified to run in $O(m+n\log{k})$ time. Our approach is identical to the algorithm described in [OMSW10]. However, we obtain a slight improvement in running time over the $O(m\log{\frac{nk}{m}})$ bound given in [OMSW10].

The low stretch spanning tree algorithm in [EEST05, ABN08] makes use of Dijkstra’s, as well as intermediate stages of it in the routines BallCut and ConeCut. We first improve the underlying data structure used by these routines.

There is a data structure that given a list of non-negative values $L=\{l_{1}\dots l_{k}\}$ (the distinct edge lengths), maintains a set of keys (distances) starting with $\{0\}$ under the following operations:

$\textsc{FindMin}()$: returns the element with minimum key.

$\textsc{DeleteMin}()$: delete the element with minimum key.

$\textsc{Insert}(j)$: insert the minimum key plus $l_{j}$ into the set of keys.

$\textsc{DecreaseKey}(v,j)$: decrease the key of $v$ to the minimum key plus $l_{j}$.

Insert and DecreaseKey have $O(1)$ amortized cost and DeleteMin has $O(\log{k})$ amortized cost.

Proof We maintain $k$ queues $Q_{1}\dots Q_{k}$ containing the keys with the invariant that the keys stored in them are in non-decreasing order. We also maintain a Fibonacci heap as described in [FT87] containing the first element of all non-empty queues. Since the number of elements in this heap is at most $k$, we can perform Insert and DecreaseKey in $O(1)$ and DeleteMin in $O(\log{k})$ amortized time on these elements. The invariant then allows us to support FindMin in $O(1)$ time.

Since $l_{k}\geq 0$, the new key introduced by Insert or DecreaseKey is always at least the minimum key. Therefore the minimum key is non-decreasing throughout the operations. So if we only append keys generated by adding $l_{j}$ to the minimum key to the end of $Q_{j}$, the invariant that the queues are monotonically non-decreasing is maintained. Specifically, $\textsc{Insert}(j)$ can be performed by appending a new entry to the tail of $Q_{j}$.

For $\textsc{DecreaseKey}(v,j)$, suppose $v$ is currently stored in queue $Q_{i}$. We consider two cases:

$v$ has a predecessor in $Q_{i}$. Then the key of $v$ is not the key of $Q_{i}$ in the Fibonacci heap and we can remove $v$ from $Q_{i}$ in $O(1)$ time while keeping the invariant. Then we can insert $v$ with its new key at the end of $Q_{j}$ using one Insert operation.

$v$ is currently at the head of $Q_{i}$. Then simply decreasing the key of $v$ would not violate the invariant of all keys in the queues being monotonic. As the new key will be present in the heap containing the first elements of the queues, a decrease key needs to be performed on the Fibonacci heap containing those elements.

DeleteMin can be done by doing a delete min in the Fibonacci heap, and removing the element from the queue containing it. If the queue is still not empty, it can be reinserted into the Fibonacci heap with key equaling to that of its new first element. The amortized cost of this is $O(\log{k})+O(1)=O(\log{k})$. $\blacksquare$

The running times of Dijkstra’s algorithm, BallCut and ConeCut then follows.

Let $G$ be a connected weighted graph and $x_{0}$ be some vertex. If there are $k$ distinct values of $d(u,v)$, Dijkstra’s algorithm can compute $d(x_{0},u)$ for all vertices $u$ in $O(m+n\log{k})$ time.

Proof Same as the proof of Dijkstra’s algorithm with Fibonacci heap, except the cost of a DeleteMin is $O(\log{k})$. $\blacksquare$

(Corollary 4.3 of [EEST05]) If there are at most $k$ distinct distances in the graph, then BallCut returns ball $X_{0}$ such that

in $O(vol(X_{0})+|V(X_{0})|\log{k})$ time.

(Lemma 4.2 of [EEST05]) If there are at most $k$ distinct values in the cone distance $\rho$, then

For any two values $0\leq r_{min}<r_{max}^{\prime}$, ConeCut finds a real $r\in[r_{min},r_{max})$ such that

in $O(vol(B_{\rho}(r,x_{0}))+|V(B_{\rho}(r,x_{0}))|\log{k})$ time, where $B_{\rho}(r,x_{0})$ is the set of all vertices $v$ within distance $r$ from $x_{0}$ in cone length $\rho$.

Proof The existence such a $L_{r}$ follows from Lemma 4.2 of [EEST05] and the running time follows from the bounds given in Lemma 5.2. $\blacksquare$

We now proceed to show a faster algorithm for constructing low stretch spanning trees by using the data structure from Lemma 5.2. Our presentation is based on the algorithm described in [ABN08], which consists of HierarchicalStarPartition at the top level that makes repeated calls to StarPartition. StarPartition then in turn obtains a desired partition via. calls to BallCut and ImpConeDecomp which uses ConeCut. Due to space limitations we refer to these routines without stating their parameters and guarantees.

Given a graph $X$ that has $k$ distinct edge lengths, The version of StarPartition that uses ImpConeDecomp as stated in Corollary 6 of [ABN08] runs in time $O(vol(|X|)+|V(X)|\log{k})$.

Proof Finding radius and calling BallCut takes $O(vol(|X|)+|V(X)|\log{k})$ time. Since the $X_{i}$s form a partition of the vertices and ImpConeDecomp never reduce the size of a cone, the total cost of all calls to ImpConeDecomp is

We now need to ensure that all calls to StarPartition are made with a small value of $k$. This can be done by rounding the edge lengths so that at any iteration of HierarchicalStarPartition, the graph has $O(\log{n})$ distinct edge weights.

Let $T$ be any spanning tree of $(V,E)$, and $u,v$ any pair of vertices, we have

Proof Summing the bound on a single edge over all edges on the tree path suffices. $\blacksquare$

Combining these two gives the following Corollary.

For any pair of vertices $u,v$ such that $uv\in E$,

Discussion

The output of IncrementalSparsify is a graph of samples with a remarkable property as a direct consequence of Lemma 3.3; its further incremental sparsification can be performed by a mere uniform sampling of its off-tree multi-edges.

This leads naturally to the definition of a smooth sequence of (multi)-graphs on a common set of vertices, with the following properties: (i) it is of logarithmic size, (ii) the first graph is spine-heavy, (iii) every two subsequent graphs have a constant condition number, and (iv) the last graph is a tree. The sequence can be obtained by applying one round of IncrementalSparsify to the spine-heavy graph, and then $O(\log n)$ rounds of uniform sampling.

Smooth sequences of graphs can be useful in an alternative way for building a chain of preconditioners, which separates sparsification from greedy elimination. More concretely, the alternative algorithm first builds a smooth sequence of graphs, starting from the spine-heavy version of the input graph. Then, somewhat roughly speaking, the final chain is obtained by applying a slightly less aggressive version of GreedyElimination to each graph in the sequence; this version eliminates degree-one nodes as usually, but restricts itself to degree-two nodes whose both adjacent edges are in the low-stretch tree. The simplicity of this approach is particularly highlighted in the case of low-diameter unweighted graphs. Solving such graphs has now been essentially reduced to the computation of a BFS tree followed by a number of rounds of uniform sampling.

We believe that smooth sequences of graphs is a notion of independent interest that may found other applications.

References