patternMinor
Decremental reachability in a grid graph
Viewed 0 times
decrementalgridgraphreachability
Problem
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?
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?
Solution
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.
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.
- 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.
Context
StackExchange Computer Science Q#29775, answer score: 3
Revisions (0)
No revisions yet.