8
$\begingroup$

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<n$ 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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ If you found the answer yourself, please do not edit it into the question, but post it as an actual answer. $\endgroup$
    – Emil Jeřábek
    Mar 23, 2022 at 10:38

2 Answers 2

Reset to default
5
$\begingroup$

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). 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 has a good discussion of the shortcutting problem in general.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – user6584
    Mar 22, 2022 at 19:27
  • $\begingroup$ Oops, you're right! I misread your post as out-degree and diameter both constants, apologies. $\endgroup$
    – GMB
    Mar 22, 2022 at 20:11
  • 1
    $\begingroup$ The pointers you gave are excellent — thank you! $\endgroup$
    – user6584
    Mar 22, 2022 at 21:05
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ doi.org/10.1007/978-3-319-21398-9_34 $\endgroup$
    – Neal Young
    Mar 24, 2022 at 0:36
  • 2
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Mar 24, 2022 at 2:03
  • 1
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Mar 24, 2022 at 15:42
  • $\begingroup$ @EmilJeřábek, thanks. $\endgroup$
    – Neal Young
    Mar 24, 2022 at 16:25

Your Answer

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

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