<p>Aside: &quot;diameter&quot; usually refers to the maximum <strong>finite</strong> distance between any two nodes in the graph, and ignores non-reachable pairs.</p>
<p>Your question is a variant of the path-shortcutting problem: given an <span class="math-container">$n$</span>-node directed path, add a small number of additional edges to the path to minimize its diameter.  What you are asking for is a little too strong to exist.  If you have max out-degree <span class="math-container">$C$</span>, then in <span class="math-container">$C$</span> hops any node can reach at most <span class="math-container">$C^C \ll n$</span> others. <em>[Edit: I misread the post and this is not what OP asked for, the original object apparently does exist.]</em></p>
<p>However, you can come close: for example, you can add <span class="math-container">$O(n \log n)$</span> shortcut edges to the path to reduce its diameter to 2 (see Lemma 1.1 in <a href="https://www.cse.psu.edu/%7Esxr48/pubs/spanners-survey.pdf" rel="nofollow noreferrer">this survey</a>).  It wouldn't be possible to tweak this construction to have, say, max out-degree <span class="math-container">$O(\log n)$</span> for the same reason as before: you would only be able to reach <span class="math-container">$O(\log^C n) \ll n$</span> nodes in <span class="math-container">$C$</span> hops.  But it might be possible to achieve something like <span class="math-container">$O(\log n)$</span> max out-degree and <span class="math-container">$O(\log n)$</span> diameter.</p>
<p><a href="https://arxiv.org/pdf/2111.13240.pdf" rel="nofollow noreferrer">This recent paper</a> has a good discussion of the shortcutting problem in general.</p>

CC BY-SA 4.0
2022-03-22T19:27:59.280Z
If the out-degree is a constant $d$ and we allow $C=O(\log n)$ then $d^C = O(n)$, so I don’t see why what I am asking for is inherently impossible.
user6584
CC BY-SA 4.0
2022-03-22T20:11:09.963Z
Oops, you're right!  I misread your post as out-degree and diameter both constants, apologies.
GMB
CC BY-SA 4.0
2022-03-22T21:05:30.433Z
The pointers you gave are excellent — thank you!
user6584
CC BY-SA 4.0
2022-03-22T16:37:31.977Z
2022-03-23T13:41:58.483Z
2022-03-23T13:41:58.483Z
GMB
<p>Thanks to the references provided, I was able to find a positive answer to my question in Chan et al., “Dynamic Tree Shortcut with Constant Degree,” COCOON 2015.</p>

CC BY-SA 4.0
2022-03-24T00:36:20.450Z
https://doi.org/10.1007/978-3-319-21398-9_34
Neal Young
CC BY-SA 4.0
2022-03-24T02:03:42.410Z
But are you sure the results in that paper (and the results cited there) apply to *directed* graphs? As stated they seem to be about undirected graphs?  For the record, maybe you could explain in your answer in more detail how the results in that paper answer your question?
Neal Young
CC BY-SA 4.0
2022-03-24T15:42:59.143Z
@NealYoung *The problem of adding a set of shortcut edges $S$ to a tree $T(V,E)$ to reduce the* hop-diameter *of the resulting graph $G(V,E\cup S)$ [...] We call a simple path $P$ from node $u$ to $v$ in $G$* straight *if the sequence of nodes in $P$ is a sub-sequence of the unique path from $u$ to $v$ in $T$. The hop-diameter of the graph is the maximum number of edges in the shortest straight path between any two nodes in the graph.* So, if $T$ is just a line as in the OP, a straight path is the same as a *directed* path, where the added edges are directed consistently with the line.
Emil Jeřábek
CC BY-SA 4.0
2022-03-24T16:25:12.040Z
@EmilJeřábek, thanks.
Neal Young
CC BY-SA 4.0
2022-03-23T23:31:38.477Z
2022-03-23T23:31:38.477Z
user6584
<p>Fix an ordering <span class="math-container">$v_1,\ldots, v_n$</span> of the vertices <span class="math-container">$V$</span> of a directed acyclic graph (DAG), so if there is a directed edge from <span class="math-container">$v_i$</span> to <span class="math-container">$v_j$</span> then <span class="math-container">$i &lt; j$</span>. Define the diameter of the graph to be the maximum, over all <span class="math-container">$i &lt; j$</span>, of the length of the shortest path from <span class="math-container">$v_i$</span> to <span class="math-container">$v_j$</span>. (If there is a more-standard term than diameter here, let me know.) Note that if we restrict attention to DAGs with finite diameter then there must be an edge from <span class="math-container">$v_i$</span> to <span class="math-container">$v_{i+1}$</span> for all <span class="math-container">$i&lt;n$</span> and so the topological ordering is unique.</p>
<p>Is it possible to construct DAGs on <span class="math-container">$n$</span> vertices with constant out-degree and diameter <span class="math-container">$O(\log n)$</span>? It seems this problem should be well-studied, but I was unable to find any references.</p>

CC BY-SA 4.0
2022-03-23T10:38:38.663Z
If you found the answer yourself, please do not edit it into the question, but post it as an actual answer.
Emil Jeřábek
<graph-theory>
Directed acyclic graphs with logarithmic diameter
user6584
# Directed acyclic graphs with logarithmic diameter

(Asked by: username_0 on 2022-03-22)

Fix an ordering $v\_1,\ldots, v\_n$ of the vertices $V$ of a directed acyclic graph (DAG), so if there is a directed edge from $v\_i$ to $v\_j$ then $i < j$. Define the diameter of the graph to be the maximum, over all $i < j$, of the length of the shortest path from $v\_i$ to $v\_j$. (If there is a more-standard term than diameter here, let me know.) Note that if we restrict attention to DAGs with finite diameter then there must be an edge from $v\_i$ to $v\_{i+1}$ for all $i and so the topological ordering is unique.

Is it possible to construct DAGs on $n$ vertices with constant out-degree and diameter $O(\log n)$? It seems this problem should be well-studied, but I was unable to find any references.

**Tags:** graph-theory
> **Comments:**
> **username_1**: If you found the answer yourself, please do not edit it into the question, but post it as an actual answer.  

---

## 2 answers

### Answer by username_2 on 2022-03-22. Score: 5

Aside: "diameter" usually refers to the maximum **finite** distance between any two nodes in the graph, and ignores non-reachable pairs.

Your question is a variant of the path-shortcutting problem: given an $n$-node directed path, add a small number of additional edges to the path to minimize its diameter. What you are asking for is a little too strong to exist. If you have max out-degree $C$, then in $C$ hops any node can reach at most $C^C \ll n$ others. *[Edit: I misread the post and this is not what OP asked for, the original object apparently does exist.]*

However, you can come close: for example, you can add $O(n \log n)$ shortcut edges to the path to reduce its diameter to 2 (see Lemma 1.1 in [this survey](https://www.cse.psu.edu/%7Esxr48/pubs/spanners-survey.pdf)). It wouldn't be possible to tweak this construction to have, say, max out-degree $O(\log n)$ for the same reason as before: you would only be able to reach $O(\log^C n) \ll n$ nodes in $C$ hops. But it might be possible to achieve something like $O(\log n)$ max out-degree and $O(\log n)$ diameter.

[This recent paper](https://arxiv.org/pdf/2111.13240.pdf) has a good discussion of the shortcutting problem in general.

> **Comments:**
> **username_0**: If the out-degree is a constant $d$ and we allow $C=O(\log n)$ then $d^C = O(n)$, so I don’t see why what I am asking for is inherently impossible.  
> **username_2**: Oops, you're right!  I misread your post as out-degree and diameter both constants, apologies.  
> **username_0**: The pointers you gave are excellent — thank you!  

---

### Answer by username_0 on 2022-03-23. Score: 3

Thanks to the references provided, I was able to find a positive answer to my question in Chan et al., “Dynamic Tree Shortcut with Constant Degree,” COCOON 2015.

> **Comments:**
> **username_3**: https://doi.org/10.1007/978-3-319-21398-9_34  
> **username_3**: But are you sure the results in that paper (and the results cited there) apply to *directed* graphs? As stated they seem to be about undirected graphs?  For the record, maybe you could explain in your answer in more detail how the results in that paper answer your question?  
> **username_1**: @NealYoung *The problem of adding a set of shortcut edges $S$ to a tree $T(V,E)$ to reduce the* hop-diameter *of the resulting graph $G(V,E\cup S)$ [...] We call a simple path $P$ from node $u$ to $v$ in $G$* straight *if the sequence of nodes in $P$ is a sub-sequence of the unique path from $u$ to $v$ in $T$. The hop-diameter of the graph is the maximum number of edges in the shortest straight path between any two nodes in the graph.* So, if $T$ is just a line as in the OP, a straight path is the same as a *directed* path, where the added edges are directed consistently with the line.  
> **username_3**: @EmilJeřábek, thanks.  

---

