Decremental reachability in a grid graph

Question

Consider an $n$ by $n$ grid graph. For example, the following.

You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of edges deleted at each step.

What is the time complexity of determining whether you can still reach the top left corner from the bottom right after edge deletions?

---

Further clarification.

Queries. There is exactly one type of query which gives a Boolean output. That is whether there is a path from the top left corner to the bottom right.

Updates. An update can delete an arbitrary number of edges greater than $0$.

Complexity. Each update is followed by a query. The complexity I am interested in is the amortized time over all updates and queries. The best this could possibly be would be proportional to the number of deleted edges I assume.

---

I found these lecture notes which say you can get $O(\log{n})$ time for planar graphs per individual edge deletion (the Eppstein et al. reference). However this paper supports many more operations than I need, my graph is a special case of a planar graph and my updates are in batches in a sense. The most important difference may just be that I am only interested in the decremental version. I haven't found anything specialized for batched, decremental connectivity in a grid graph.

Is there anything simpler than the Eppstein et al. paper for my special case or alternatively faster than $O(\log{n})$ time per edge deletion?

Answer 1

"Optimal decremental connectivity in planar graphs", by Jakub Łącki, Piotr Sankowski demonstrates an algorithm that uses $O(1)$ amortized time per update and $O(1)$ time per query.

Answer 2

By improving on @emab's idea, you can achieve $\Theta(\alpha(n^2))$ amortized time per deletion and query, where $\alpha$ is the inverse Ackermann function, i.e. almost constant.

• Initialize a union-find data structure with an enry for each square of the grid graph and two entries each for the two pairs of outside faces top+right and bottom+left. For an example of $n=3$, the faces $1,2,3,\ldots,9,A,B$ in the diagram below are initialized. Where $A,B$ are the outside faces split by the dashed lines.
• When removing an edge call union() on the two squares (or the sqare and $A$ or $B$) separated by that edge.
• To check connectivity, call find() on the faces $A$ and $B$. If the results differ, return true, else return false.

Answer 3

Let's call the top-left node as $s$ and the bottom-right node as $t$.

In the square drawing of this graph, there are four sides (left, right, top, bottom).

Let's call two edges connected, iff they share a square or an endpoint (we can determine if two edges are connected or not in $O(1)$).

As you remove the edges from the graph, you maintain a few lists of those edges. that are connected, and see if any of them connect one of the four side pairs:

• top to bottom
• top to left
• left to right
• bottom to right

In the following figure, by dashed red lines, I tried to demonstrate a series of edge removals (if the red dashed line crosses an edge, it means that the edge is removed at some point).

(Algorithm is below figure)

Algorithm

Component = []
/* Initialize Hit_Sides by 0 */
Hit_Left = []; Hit_Right = []; Hit_Top = []; Hit_Bottom = []; 
while ( input >> e; /* there is an edge e to be removed */)
    L = L + {e};
    Component[e] = e;
    if (e hits any side s) then
        Hit_s[e] = 1;
    For each e' in L
        if (e' is connected to e)
            Component[e] = Component[e']
        if (e hits any side s)
            Hit_s[Component[e] = 1;
    For each component c in Component
        if (it hits one of the four disconnecting pairs)
            Output << There is no path from s to t

BTW, the following explanation is clear and precise. However, if you use geometrical techniques, you may be able to get some logarithmic algorithm out of it.

---

If you maintain a list of edges that are being removed, you can consider the list of connected ones, and see whether they hit any disconnecting sides (top-bottom, top-left, left-right, bottom-right) and answer to that reachability query in $O(1)$.

In the following figure, red lines illustrate the disconnecting sides: