7
$\begingroup$

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). enter image description here

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

$\endgroup$
  • $\begingroup$ What happened with your early explorations of simple cases like $2x2$ or $3x3$? $\endgroup$ – Lee Mosher Feb 25 '18 at 17:14
  • $\begingroup$ $|P|$ = 2 for 2x2 graph, $|P|$ = 4 for 3x3 graph. But I have no idea to generalize it. $\endgroup$ – Moshe Feb 25 '18 at 17:19
  • $\begingroup$ 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." $\endgroup$ – Misha Lavrov Feb 25 '18 at 18:10
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Feb 25 '18 at 22:13
  • $\begingroup$ @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? $\endgroup$ – Moshe Feb 25 '18 at 22:15
2
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Moshe Feb 25 '18 at 21:31
  • $\begingroup$ I have written a new answer that actually solves the correct problem this time. $\endgroup$ – Misha Lavrov Feb 26 '18 at 5:39
  • $\begingroup$ 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? $\endgroup$ – Moshe Feb 26 '18 at 9:21
  • $\begingroup$ @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$.) $\endgroup$ – Misha Lavrov Feb 26 '18 at 14:39
  • $\begingroup$ 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? $\endgroup$ – Moshe Feb 26 '18 at 15:11

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.