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

<ul>
<li><p><strong>Lower bound:</strong> Consider the 1-dimensional point set in which $v_i = 2^i$.  For every  index $i &gt; 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$.</p></li>
<li><p><strong>Upper bound:</strong>  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.</p></li>
</ul>

CC BY-SA 3.0
2013-05-20T16:22:29.033Z
Thank you. Your examples prove that there are some special cases I'm not interested in. I'm actually interested in dense point sets with namely uniform or Poissonian distribution. In this case I expect something asymptotically lower than $O(n)$. For example, n $m=1$ case I expect the number of sufficient paths to be $O(1)$. I should change the question to only consider acceptable sets.
AmeerJ
CC BY-SA 3.0
2013-05-20T15:57:18.183Z
2013-05-20T16:43:26.843Z
2013-05-20T16:43:26.843Z
Jeffε
<p>Informally, we define <em>minimum shortest path cover</em> 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: </p>

<ul>
<li>weight of a path: if $P=u_1, ...,u_{|P|}$ then $w(P) = \sum w(u_i,u_{i+1})$</li>
<li>set of all path covers of $G$: $PC(G)=\{\{P_1, ..., P_k\} |\forall i \exists j: v_i \in P_j\}$.</li>
<li>Size of a path cover: if $PC=\{P_1, ..., P_k\}$ then $Size(PC)= k$</li>
<li>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\}$</li>
<li>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)\}$.</li>
<li>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)\}$</li>
<li>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$</li>
</ul>

<p>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 \}$.</p>

<p>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:</p>

<ul>
<li>vertices: $V={v_1, v_2, ..., v_n}, \forall i: v_i \in R^m$ </li>
<li>distances: $d(u,v)$ denotes <em>euclidean distance</em> between $d(u,v)=||u-v||_2$ </li>
<li>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)$.</li>
<li>edges: $E=\{(u,v) | u,v \in V, v \in N_k(u)\}$. Alternatively, $Adj(u)=N_k(u)$.</li>
<li>weights: if $(u,v) \in E$ then $w(u,v) = d(u,v)$.</li>
<li>Graph: $G=(V,E)$.</li>
</ul>

<p><strong>UPDATE</strong>: Some additional notes: </p>

<ul>
<li>Shortest paths are unique.</li>
<li>k is chosen large enough to keep $G$ connected</li>
<li>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). </li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2013-05-20T13:58:10.117Z
I think you need some more conditions to guarantee that there always exists a lowest-cost-path cover.  In particular, you need to deal with negative weights.
András Salamon
CC BY-SA 3.0
2013-05-20T14:36:51.657Z
Thanks for the point. I forgot to say (it's updated now) that edge weights are non-negative (as the case with euclidean distances).
AmeerJ
CC BY-SA 3.0
2013-05-20T15:42:14.757Z
Are you assuming all pairwise distances are distinct?  Otherwise, your graph isn't well defined.  For example, suppose $n-1$ points lie on a circle centered at the $n$th point.
Jeffε
CC BY-SA 3.0
2013-05-20T16:07:27.503Z
Thank you. Yes shortest paths are distinct (because points are noisy real numbers). I'll add it to the question.
AmeerJ
CC BY-SA 3.0
2013-05-20T16:41:51.150Z
What's a "noisy real number"?
Jeffε
CC BY-SA 3.0
2013-05-20T17:18:01.443Z
The data points are stochastic which makes it very difficult for the graph to form two paths with same length between $u, v$.
AmeerJ
CC BY-SA 3.0
2013-05-21T05:28:25.960Z
What's a "stochastic data point"? If you mean random (as in your special case of uniformly distributed points in the hypercube), just say random.  If you _don't_ mean random, what precisely do you mean?
Jeffε
<graph-theory><cg.comp-geom>
Minimum shortest path cover of $n$ vertices in $R^m$
AmeerJ
# Minimum shortest path cover of $n$ vertices in $R^m$

(Asked by: username_0 on 2013-05-20)

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.

**Tags:** graph-theory, cg.comp-geom
> **Comments:**
> **username_1**: I think you need some more conditions to guarantee that there always exists a lowest-cost-path cover.  In particular, you need to deal with negative weights.  
> **username_0**: Thanks for the point. I forgot to say (it's updated now) that edge weights are non-negative (as the case with euclidean distances).  
> **username_2**: Are you assuming all pairwise distances are distinct?  Otherwise, your graph isn't well defined.  For example, suppose $n-1$ points lie on a circle centered at the $n$th point.  
> **username_0**: Thank you. Yes shortest paths are distinct (because points are noisy real numbers). I'll add it to the question.  
> **username_2**: What's a "noisy real number"?  
> **username_0**: The data points are stochastic which makes it very difficult for the graph to form two paths with same length between $u, v$.  
> **username_2**: What's a "stochastic data point"? If you mean random (as in your special case of uniformly distributed points in the hypercube), just say random.  If you _don't_ mean random, what precisely do you mean?  

---

## 1 answers

### Answer by username_2 on 2013-05-20. Score: 5

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.

> **Comments:**
> **username_0**: Thank you. Your examples prove that there are some special cases I'm not interested in. I'm actually interested in dense point sets with namely uniform or Poissonian distribution. In this case I expect something asymptotically lower than $O(n)$. For example, n $m=1$ case I expect the number of sufficient paths to be $O(1)$. I should change the question to only consider acceptable sets.  

---

