Minimum shortest path cover of $n$ vertices in $R^m$

Question

Informally, we define minimum shortest path cover to be the smallest number of shortest paths that cover all vertices of a graph. In other words, every vertex should belong to at least one of those shortest paths (there is no problem if one vertex belongs to more than one paths). Formally, we define the problem as follows. Assume the directed graph $G=(V,E)$ with vertices $V=\{v_1, ..., v_n\}$, with non-negative edge weights $w(v_i,v_j) \ge 0$. We have following definitions respectively:

• weight of a path: if $P=u_1, ...,u_{|P|}$ then $w(P) = \sum w(u_i,u_{i+1})$
• set of all path covers of $G$: $PC(G)=\{\{P_1, ..., P_k\} |\forall i \exists j: v_i \in P_j\}$.
• Size of a path cover: if $PC=\{P_1, ..., P_k\}$ then $Size(PC)= k$
• set of all paths of $G$ starting from $v$ and ending in $u$: $P(G, v, u)=\{v, v_{i_1},...,v_{i_l}, u | \forall j: v_{i_j}, u, v \in V, (v_{i_j},v_{i_{j+1}}), (v,v_{i_1}), (v_{i_{|P|}},u)\in E\}$
• set of all shortest paths of $G$ by $SP(G) = \{P = v_{i_1}, ..., v_{i_{|P|}} | \forall Q \in P(G,v_{i_1},v_{i_{|P|}}), w(P) \le w(Q)\}$.
• Set of shortest path covers of $G$: $SPC(G)=\{PC=\{P_1, ..., P_k\} | PC \in PC(G), \forall i: P_i \in SP(G)\}$
• Minimum shortest path cover of G: if $PC \in SPC(G)$ and $\forall Q \in SPC(G): Size(P) \le Size(Q)$ then $MSPC(G) = PC$

To give a concrete example, suppose graph $G=(V,E)$, with vertices $ V=\{1,2,3,4\}$, and edges $E=\{1\rightarrow 2,1\rightarrow 5, 2\rightarrow 3,4\rightarrow 5\}$. It is clear that $G$ could be covered by two paths. The minimal set would be $MSPC(G)=\{1\rightarrow 2 \rightarrow 3,\ 4\rightarrow 5 \}$.

Now we informally construct the graph $G$ as follows. Its set of vertices ${v_1, v_2, ..., v_n}$ are points in $R^m$. Then we put the $k$ nearest vertices to $v_i$ (euclidean distance) in its adjacency list $Adj(n_i)$. Noting that $n_i \in Adj(n_j)$ does not imply $n_j \in Adj(n_i)$, the formed graph is directed and not necessarily symmetric. We can hold $k$ to be constant or $k \ll n$, in a way that the graph would become sparse.More formally we have following definitions:

• vertices: $V={v_1, v_2, ..., v_n}, \forall i: v_i \in R^m$
• distances: $d(u,v)$ denotes euclidean distance between $d(u,v)=||u-v||_2$
• k-nearest neighbours: $N_k(u)=\{u_1, ..., u_k\}$ in that $\forall u_1 \in N_k(u), u_2 \notin N_k(u)$ implies $d(u,u_1) \le d(u,u_2)$.
• edges: $E=\{(u,v) | u,v \in V, v \in N_k(u)\}$. Alternatively, $Adj(u)=N_k(u)$.
• weights: if $(u,v) \in E$ then $w(u,v) = d(u,v)$.
• Graph: $G=(V,E)$.

UPDATE: Some additional notes:

• Shortest paths are unique.
• k is chosen large enough to keep $G$ connected
• A special case of interest is when nodes are dense $n \rightarrow \infty$ in a limited space (say unit hypercube $(0,1)^m$), and they follow a specific distribution (namely uniform).

Using the above definitions, the question is what is the asymptotic value of $Size(MSPC(G))$ or $E\{Size(MSPC(G))\}$ in the case of stochastic points? My intuition is that it is of the form $O(n^\frac{m-1}{m})$, which comes from the number of necessary paths to cover a $m$-dimensional regular grid in $R^m$. Suppose we have $l^m$ vertices $(a_1, ..., a_m), a_i \in \{1, ..., l\}$. You could cover this grid by $l^{m-1}$ paths like this: $Path-Cover = \{\{(1, P), (2, P), ..., (l, P)\}| P \in \{1,...,l\}^{m-1}\}$. Substituting $l^m$ by $n$ the $O(n^\frac{m-1}{m})$ bound could be achieved.

Answer 1

Without further assumptions about the point set, the answer can be anywhere between $1$ and $n/(k+1)$.

• Lower bound: Consider the 1-dimensional point set in which $v_i = 2^i$. For every index $i > 1$, the nearest neighbor of $v_i$ is $v_{i-1}$. So the directed $1$-nearest-neighbor graph can be covered by a single shortest path $v_n \to v_{n-1} \to\cdots \to v_1$.

• Upper bound: Consider the 1-dimensional point set where $$v_i = n^2 \lfloor i/(k+1) \rfloor + (i\bmod (k+1)).$$ This point set consists of $n/(k+1)$ tight clusters of $k+1$ points, with large gaps between the clusters. The $k$ nearest neighbors of any point $v_i$ are in the same cluster as $v_i$. Thus, the $k$-nearest-neighbor graph has $n/(k+1)$ components. It follows that we need at least $n/(k+1)$ shortest paths to cover the graph.