8
$\begingroup$

Given positive integers $n$ and $m$. We choose any partial grid $G$ that is a subgraph of $n \times m$ grid. We choose some vertex $v$ of $G$ and run breadth first search (BFS) algorithm from this vertex. Layer of BFS tree is a set of vertices with the same distance (in edges) to $v$. The question is the following:

What is the maximum size of layer of BFS tree over all choices of $G$ and $v$ for given $n$ and $m$?

Particularly, is it true that size of each layer is $O(n + m)$? Or can it be $\Omega(nm)$?

Background of this question is the following. I want to challenge student's solution for a problem that requires BFS on partial grid. The problem in his implementation is that he uses array instead of queue and deletes the first element shifting all others. Therefore time complexity of his implementation is $\Omega(\ell_0^2 + \ell_1^2 + \cdots + \ell_d^2)$, where $\ell_i$ is number of vertices with distance $i$ to vertex $v$ and $d$ is the maximum distance to $v$. This is obviously quadratically bad time for general case, however it would be acceptable by judge system subject to existing constraints on $n$ and $m$ (up to $300$) if there is no test case with layer size of $\omega(n + m)$.

$\endgroup$

2 Answers 2

9
$\begingroup$

I'm not sure if the following construction is the maximum possible, but it beats $O(m+n)$:

grid graph

In a $n \times n$ grid with $n = 2^{k+1}-1$, we take the union of all paths from the center that take:

  • $2^{k-1}$ steps in one direction;
  • $2^{k-2}$ steps in a direction different from the previous;
  • $2^{k-3}$ steps in a direction different from the previous (but possibly equal to the first direction);
  • And so on, until we take a single step in some direction.

This is a tree with $\Theta(3^k) = \Theta(n^{\log_2 3})$ leaves, which is definitely $\omega(n)$ and more than halfway to the desired $\Omega(n^2)$.

$\endgroup$
2
  • $\begingroup$ Shame on me, I had this construction in my mind, but didn't evaluate it for some reason. Thank you! $\endgroup$
    – Smylic
    Commented Apr 5, 2017 at 22:47
  • $\begingroup$ There is a lot of empty space inside, you can make a special elongated path with lots of turns to create leaves there too (in a same fractal manner to what you already did. $\endgroup$
    – dtldarek
    Commented Apr 6, 2017 at 6:09
7
$\begingroup$

Here is a different example that has a leaf within each $2\times 2$ area:

grid tree

I hope this helps $\ddot\smile$

$\endgroup$
10
  • $\begingroup$ This is very nice construction! Maybe it is even the best possible for $m = n = 2^k - 1$. However it is still not enough in my case... $\endgroup$
    – Smylic
    Commented Apr 6, 2017 at 10:18
  • $\begingroup$ @Smylic What do you mean? It has $\Theta(n^2)$ leaves, as you wished. What else do you need for your tests? $\endgroup$
    – dtldarek
    Commented Apr 6, 2017 at 12:52
  • $\begingroup$ I mean that I have already tried your idea and that solution has more than twice more time to run. That wasn't surprising due to a small constant under $\Theta$, that even squares further. $\endgroup$
    – Smylic
    Commented Apr 6, 2017 at 13:27
  • $\begingroup$ @Smylic Well, $n,m \leq 300$ are really small constants for these kind of tasks. BTW, just to be sure, are your time-limits adjusted (say, by timing the official solution) to the machine your are testing it on (like lab computer or a virtual machine on your own computer)? $\endgroup$
    – dtldarek
    Commented Apr 6, 2017 at 14:37
  • 1
    $\begingroup$ @Smylic Now, that I am assured you know all these tricks, I can sleep soundly $\ddot\smile$ $\endgroup$
    – dtldarek
    Commented Apr 6, 2017 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .