Given a directed $n\times n$ square graph as shown in the figure with $n^2$ nodes. Find a set of directed paths $\mathcal P$ from $s$ to $t$ with the minimum cardinality (i.e, minimum number of paths in $\mathcal P$) such that any pair of reachable vertices is contained in at least one path in $\mathcal P$. Two vertices is reachable if there exists an directed path between them. For example, if node $v$ is below and on the right node $u$, then $u$ and $v$ is reachable (see figure).
I have solved this problem for small $n$ by trial and error but I have no idea to generalize it. Can anyone give me some hints? or tell me if this problem is NP-hard? Many thanks
The minimum number of paths needed in an $n$ by $n$ grid (that is, a grid with $n^2$ vertices) is $\left\lceil \frac{n(n+1)}{3}\right\rceil$: sequence A007980 in the OEIS.
To prove that at least this many paths are needed, let $k = \lfloor \frac{2n-1}{3}\rfloor$, define $u_0, u_1, \dots, u_k$ by $u_i = (i,k-i)$, and define $v_0, v_1, \dots, v_k$ by $(n-1-i,n-1-(k-i))$ (as coordinates with $(0,0)$ the top left corner of the grid). Not all pairs of points $(u_i, v_j)$ can have a path going through both, but there turn out to be exactly $\left\lceil \frac{n(n+1)}{3}\right\rceil$ that do (to check this, do the computation for each case of $n \bmod 3$ separately). Any path can only go through one point $u_i$ and one point $v_j$, so there must be at least $\left\lceil \frac{n(n+1)}{3}\right\rceil$ paths to account for all these pairs.
To prove that $\left\lceil \frac{n(n+1)}{3}\right\rceil$ pairs suffice, we give a recursive construction which fills an $n \times n$ grid with $2(n-1)$ more paths than an $(n-3) \times (n-3)$ grid. (The sequence $\left\lceil \frac{n(n+1)}{3}\right\rceil$ turns out to satisfy this recurrence.)
Begin by taking the following $2(n-1)$ paths in the $n \times n$ grid:
These are enough to cover all pairs of vertices that are in the same row or column, as well as all pairs of vertices that include a vertex along one of the borders of the grid.
To deal with pairs of vertices that aren't along a border of the grid, take the construction for the $(n-3) \times (n-3)$ grid, and modify each path as follows:
Let $u_1$ and $u_2$ be two vertices in the grid with coordinates $(x_1,y_1)$ and $(x_2,y_2)$, such that $1 < x_1 < x_2 < n-1$ and $1 < y_1 < y_2 < n-1$. To show that there's a modified path covering $u_1$ and $u_2$ simultaneously, define $$ u_i' = \begin{cases} (x_i-1, y_i-1), & \text{if } x_i + y_i < n-1, \\ (x_i-1, y_i-2) \text{ or } (x_i-2,y_i-1), & \text{if } x_i + y_i = n-1, \\ (x_i-2, y_i-2), & \text{if } x_i + y_i > n-1. \end{cases} $$ Here is a visualization of this not-quite-bijective correspondence between points in the interior of the $n \times n$ grid, and points in the $(n-3) \times (n-3)$ grid. Each red region (mostly including one point, some including more) corresponds to a point in the smaller grid. Points in the overlap of two red regions could go either way, it doesn't matter.
The path in the $(n-3) \times (n-3)$ grid covering $u_1'$ and $u_2'$ simultaneously becomes a path in the $n \times n$ grid covering $u_1$ and $u_2$ simultaneously when modified. This completes the proof that the construction works.