Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a SHORTER path. But what we should expect for nodes $P(i), P(i+k)$ for $k<d$ ? How typically they can be connected by a path shorter than $k$ ? (depending on d, length(P), G, .. )
Definition: Let us say path $P$ is "unshortable" in graph $G$ with diameter $d$, if for any nodes $P(i), P(i+k), k<= d$ the subpath $P(i)-P(i+k)$ is the shortest path between $P(i)$, $P(i+k)$.
Clearly any shortest path between two nodes $A$,$B$ is unshortable (it is shorter than $d+1$), but there can be longer paths which are still unshortable. On the other had extremely long path - containing almost all nodes in say random graph - typically cannnot unshortable - since you can connect some nearby nodes in a shorter. So estimating length of maximal unshortable path seems to be an interesting question.
Question 0: any references discussing such kind of questions ? May be there is another standard name instead of "unshortable" ?
Question 1: How long can be the "unshortable" path in given $G,d$ ? Is there any bound on the length $N$ of the unshortable path in terms of diameter, something like - for any $G$: $N < 10d$ or $N < exp(d)$ ? Computing $N$ for given $G$ is NP-hard ?
Question 2 Is there any information on the percent of unshortable paths of given length $M$ among all paths in given finite graph $G$ ? The percent short decrease with $M$ growing. How it might decrease - power-low , exponentially ? In the the words sampling a random path of length $M$ what are the chances for it to be "unshortable" ? Intuitively chances are quite big at least for Cayley graphs $G$ of random permutation groups.
Relaxing definition: Let $K<d$ be some positive integer number, let us call path $P$ is $K$-unshortable if any subpath of length $l\le K$ is the shortest path in the graph.
Question 4: Same questions above for $K$-unshortable paths.
Motivation: The context is computational - computing shortest paths for some (very) big graphs. Assume we are interested in the task to find shortest path between nodes $A,B$ in some graph $G$. Moreover, assume we are given a hint: some non-shortest path $P$ between $A,B$ and we want to "shorten" that path. The trivial strategy - just take pairs of nodes $P(i),P(i+u)$ and try to shorten such segments. Of course, if $u>d$ it is possible - but that can me computationally very hard. It is computationally easy to check subpaths $P(i), P(i+\text{small number})$ .
But the question is - how big are the chances to find such kind of "shortcut" ? Depending on path length, diameter and G ? Any references on that ?
Somewhat related figure by colleague from Kaggle:
https://www.kaggle.com/competitions/santa-2023/discussion/470799#2622617 :
Computational experiment not sure I am interpreting the outcomes correctly - but it seems that for some Cayley graphs for Rubik's cube like group, if the paths are $10 * d$ (i.e. 10 times longer than diameter) the paths can be shortened by some not-so-hard greedy algorithms, not sure that it means that $ 10 * d$ are unshortable, but at least not contradict to it. (See https://www.kaggle.com/competitions/santa-2023/overview)
