Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch)

Question

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!

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.