Find a generalized path cover of a square graph

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

• What happened with your early explorations of simple cases like $2x2$ or $3x3$? – Lee Mosher Feb 25 '18 at 17:14
• $|P|$ = 2 for 2x2 graph, $|P|$ = 4 for 3x3 graph. But I have no idea to generalize it. – Moshe Feb 25 '18 at 17:19
• If you've made progress on small examples, that is the sort of thing that should go in a question rather than just "Here is problem statement solve it for me." – Misha Lavrov Feb 25 '18 at 18:10
• For a $2n-1 \times 2n-1$ grid, there is a lower bound of $n^2$: let $u_1, \dots, u_n$ be the vertices within $n-1$ steps of $s$, and $v_1, \dots, v_n$ be the vertices within $n-1$ steps of $t$. Then any pair $(u_i, v_j)$ must be contained in a path, and no path can contain more than one such pair. – Misha Lavrov Feb 25 '18 at 22:13
• @MishaLavrov Thank you, but we only get a lower bound. It is possible that this lower bound is far away from the solution. Can we guarantee how far the lower bound from the optimal solution? Do u think this problem is Np-hard? – Moshe Feb 25 '18 at 22:15

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:

• paths that go $k$ steps right, $n-1$ steps down, and $n-1-k$ more steps right for $k=1,\dots,n-1$, and
• paths that go $k$ steps down, $n-1$ steps right, and $n-1-k$ more steps down for $k=1, \dots, n-1$.

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:

• Insert a step down and a step right at the beginning.
• Insert a step down and a step right in the very middle.
• Insert a step down and a step right at the end.

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.

• Hi, it is not the path cover in Dilworth theorem. Here I need to cover all vertices and pair of reachable vertices. Dilworth theorem only give me a lower bound. – Moshe Feb 25 '18 at 21:31
• I have written a new answer that actually solves the correct problem this time. – Misha Lavrov Feb 26 '18 at 5:39
• Many thanks for your great effort. However, I think the lower bound is not correct. We don't need to cover for all pairs of vertices, only for those are reachable. In particular, $u=(i,j)$ and $v=(k,l)$ are reachable iff $i\leq k, j\leq l$ or $i\geq k, j\geq l$. For example, take $n=5$, hence $k=3, u_0 = (0,3), v_0 = (4,1)$ but we don't need to cover $(u_0,v_0)$. Do you think this problem is NP-hard for a directed acyclic graph? – Moshe Feb 26 '18 at 9:21
• @Moshe ...yes, that's the problem I'm solving? I'm not saying that all pairs $(u_i, v_j)$ in my lower bound are reachable; I'm saying that there are $\left\lceil \frac{n(n+1)}{3}\right\rceil$ reachable pairs among them. (This is roughly $\frac34$ of the total number of pairs, which $k^2 \sim \frac49n^2$.) – Misha Lavrov Feb 26 '18 at 14:39
• Many thanks. I want to generalize this to a directed acyclic graph (DAG) but it is impossible because the solution depends on the structure of the square graph. Do you think we can have a solution for a DAG? – Moshe Feb 26 '18 at 15:11