I'm trying to understand a specific part from an article of Agarwal and co.

It is about Distance Oracles but there is a specific explanation of How to convert from average-degree graph to maximum-degree bounded graph with linear complexity.

I can't understand it so I need a simple language explanation...

This is the link to the article: http://arxiv.org/pdf/1201.2703.pdf and the specific explanation is in section 5.

From the article: (I don't understand the reduction)

Let G = (V, E) be a connected graph with average degree ∆. Given G, we will first create a ∆-degree bounded graph G∆ = (V∆ , E∆ ). Then, we show how can be used on G∆ to return stretch-s paths on G.

The Reduction: For each node v ∈ V , create α v = ⌈deg(v)/∆⌉ nodes v1 , v2 , . . . , vαv in V∆ . For each edge e = (u, v) ∈ E, if deg(u) ≤ ∆ and deg(v) ≤ ∆, create an edge e = (u1 , v1 ) in E∆ . For each node v ∈ V , we arbitrarily distribute N (v) in G to the nodes corresponding to v in G∆ such that for i = 1, 2, . . . , (α v − 1), |N (v) ∩ N (vi )| = ∆ and |N (v) ∩ N (vαv )| = (deg(v) − (α v − 1) · ∆). Finally, for each pair vi , vi+1 , we create an edge in E∆ of weight 0.

In order to answer an approximate distance query for any pair of nodes u, v ∈ V , we use D to answer approximate distance queries between u1 , v1 ∈ V∆ in G∆ and let the length of the path returned by the data structure be δ′ . We output the distance δ′ as an approximate distance for the pair of nodes in G.


  • 1
    $\begingroup$ Can you ask a more direct question? What, more specifically, do you not understand? $\endgroup$ Nov 25, 2012 at 13:41
  • $\begingroup$ If you'll open the article (I mentioned the related section - 5 it's really short) you'll see that my question is very specific.. and it is bold above: How to convert from average-degree graph to maximum-degree bounded graph. thanks. $\endgroup$
    – Bush
    Nov 25, 2012 at 17:11
  • 1
    $\begingroup$ If it is really short, then include it here. This will make for a better question and is more likely to be answered. $\endgroup$ Nov 25, 2012 at 17:22
  • 1
    $\begingroup$ The questions should be self-contained as much as possible so readers do not need to go to other place to understand the question. Please make your question self contained. $\endgroup$
    – Kaveh
    Nov 25, 2012 at 18:18
  • $\begingroup$ You right. I added the text. $\endgroup$
    – Bush
    Nov 25, 2012 at 18:24

1 Answer 1


Here is, perhaps a more understandable, proof. Let me start with the following claim:

Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices and $m$ edges. For any integer $k \geq 3$, one can convert $G$ into a graph $H$ with maximum degree $k$ with $m' = (1+2/(k-2))m$ edges and $n' = n + 2m/(k-2)$ vertices. Furthermore, for any two vertices $u$ and $v$ in $G$, the distance between any copy of $u$ to any copy of $v$ in $H$ is equal to the distance of $u$ and $v$ in $G$. This conversion can be done in $O(n + m)$ time.

Here is a rough proof to the above claim:

We start with a copy $H$ of $G$. We scan the vertices of $H$ one by one. If a vertex $v \in V(H)$ has degree $\leq k$ then we leave it as it is. Otherwise, consider $v$ and the edges coming out of it. We replace $v$ by a list of $\lceil \deg(v)/(k-2) \rceil$ vertices, all of them connected by a new path of edges having weight $0$. Each of these new vertices is assigned at most $k-2$ edges that were adjacent to $v$ (these reassigned edges keep their original weight). We repeat this process till the degrees in the new graph are bounded by $k$.

The number of new vertices created during this process to replace a single vertex $v$ is $ \lceil \deg(v) /(k-2) \rceil$. The number of new edges created for $v$ is $ \lceil \deg(v) /(k-2) \rceil - 1$. Clearly, the new graph has $\sum_{v \in V(G)} \lceil \deg(v)/(k-2) \rceil \leq n + \sum_{v \in V(G)} \deg(v) /(k-2) \leq n + 2m/(k-2)$ vertices. The number of new edges added because of $v$ is at most $2m/(k-2)$.

In the new graph, we replace every vertex by a path (with all its edges having weight $0$), and kept the original edges. As such, the distance between two vertices in the modified graph is the same as the distance between the corresponding vertices in the original graph.

A corollary of the above claim is:

Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices, $m$ edges, and average degree $\mu = 2m/n$. Then one construct an equivalent graph with maximum degree $k = \lceil {\mu +2} \rceil$, such that the new graph has $2n$ vertices, $m+n$ edges, and has the same distances between any pair of vertices as the distance in the original graph between the corresponding vertices. The new graph can be computed in $O(n + m)$ time.

The above implies that given a graph with average degree $\mu$, we can replace it with a graph with maximum degree $\mu + 2$, and build the distance oracle on this new graph instead of the original graph.

  • $\begingroup$ Very helpful! One thing: how do we get the O(n+m) time? $\endgroup$
    – Bush
    Nov 25, 2012 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.