# Decremental reachability in a grid graph

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?

"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.

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.
• Are you assuming that the intersections of the lines in my diagram are the nodes (which is what I intended) or the square spaces?
– Simd
Commented Sep 10, 2014 at 12:51
• @Lembik Yes, that is what I am assuming. The elements in the union-find data structure, however, are the square spaces and not the nodes of the graph. Commented Sep 10, 2014 at 12:54
• @Biliska I agree that your edit makes the post easier to understand. Thanks for that. Commented Sep 10, 2014 at 13:52
• The union-find solution really solves the incremental connectivity problem on not-necessarily-planar graphs, which allows multiple sources / sinks (using a super-source/super-sink). The decremental top-left to bottom-right problem is then reduced to an incremental problem on the dual graph, using the top-most + right-most edges as sources and bottom-most + left-most edges as sinks. Commented Dec 28, 2020 at 20:34

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:

• How long are the updates taking in this solution?
– Simd
Commented Sep 9, 2014 at 9:31
• Consider the graph as a grid on a surface. A native method is to check all the previous deleted edges $O(k^2)$ if the number of updates is $k$. I am not sure, but there must be some logarithmic method using geometrical methods and sorting the nodes based on their ordinates. Commented Sep 9, 2014 at 9:47
• I can't understand this answer or how you get $O(1)$ time. I don't understand the figure, either. There are exponentially many possible cuts (red lines); you can't keep track of all of them.
– D.W.
Commented Sep 9, 2014 at 18:17
• @D.W. Suppose you have a list of edges that are being removed, then you find the connected ones, and see if they connect any disconnecting side pairs. By "connected ones" I mean having the same square, or endpoint; Once you see if they connect disconnecting pairs, you can determine whether there still is a path from source to sink or not. Commented Sep 10, 2014 at 0:09
• @D.W. We don't keep track of red lines, as we store the connected edges, we just see if they hit any of those four pairs of sides. Commented Sep 10, 2014 at 0:26