[Solved]: Decremental reachability in a grid graph

Problem Detail: 

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?

Asked By : Lembik

Answered By : jbapple

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29775