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

<blockquote>
  <p>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.</p>
</blockquote>

<p>Here is a rough proof to the above claim:</p>

<p>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$.</p>

<p>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)$.</p>

<p>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.</p>

<p>A corollary of the above claim is:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2012-11-25T21:37:32.660Z
Very helpful! One thing: how do we get the O(n+m) time?
Bush
CC BY-SA 3.0
2012-11-25T19:41:56.980Z
2012-11-25T19:41:56.980Z
Rachit
<p>I'm trying to understand a specific part from an article of Agarwal and co.</p>
<p>It is about Distance Oracles but there is a specific explanation of <strong>How to convert from average-degree graph to maximum-degree bounded graph</strong> with linear complexity.</p>
<p>I can't understand it so I need a simple language explanation...</p>
<p>This is the link to the article: <a href="http://arxiv.org/pdf/1201.2703.pdf" rel="nofollow noreferrer">http://arxiv.org/pdf/1201.2703.pdf</a> and the specific explanation is in section 5.</p>
<p>From the article: (I don't understand the reduction)</p>
<blockquote>
<p>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.</p>
<p><strong>The Reduction:</strong> 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.</p>
<p>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.</p>
</blockquote>
<p>Thanks!</p>

CC BY-SA 3.0
2012-11-25T13:41:29.757Z
Can you ask a more direct question? What, more specifically, do you not understand?
Tyson Williams
CC BY-SA 3.0
2012-11-25T17:11:16.980Z
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.
Bush
CC BY-SA 3.0
2012-11-25T17:22:39.773Z
If it is really short, then include it here.  This will make for a better question and is more likely to be answered.
Tyson Williams
CC BY-SA 3.0
2012-11-25T18:18:55.573Z
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.
Kaveh
CC BY-SA 3.0
2012-11-25T18:24:16.347Z
You right. I added the text.
Bush
<cc.complexity-theory><graph-theory><graph-algorithms>
Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch)
Bush
# Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch)

(Asked by: username_0 on 2012-11-25)

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.

Thanks!

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Can you ask a more direct question? What, more specifically, do you not understand?  
> **username_0**: 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.  
> **username_1**: If it is really short, then include it here.  This will make for a better question and is more likely to be answered.  
> **username_2**: 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.  
> **username_0**: You right. I added the text.  

---

## 1 answers

### Answer by username_3 on 2012-11-25. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: Very helpful! One thing: how do we get the O(n+m) time?  

---

