2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon May 20 '13 at 13:58
  • $\begingroup$ Thanks for the point. I forgot to say (it's updated now) that edge weights are non-negative (as the case with euclidean distances). $\endgroup$ – AmeerJ May 20 '13 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffε May 20 '13 at 15:42
  • $\begingroup$ Thank you. Yes shortest paths are distinct (because points are noisy real numbers). I'll add it to the question. $\endgroup$ – AmeerJ May 20 '13 at 16:07
  • $\begingroup$ What's a "noisy real number"? $\endgroup$ – Jeffε May 20 '13 at 16:41
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – AmeerJ May 20 '13 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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