4
$\begingroup$

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

Grid graph

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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. enter image description here
  • 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.
$\endgroup$
  • $\begingroup$ Are you assuming that the intersections of the lines in my diagram are the nodes (which is what I intended) or the square spaces? $\endgroup$ – Lembik Sep 10 '14 at 12:51
  • $\begingroup$ @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. $\endgroup$ – FrankW Sep 10 '14 at 12:54
  • $\begingroup$ @Biliska I agree that your edit makes the post easier to understand. Thanks for that. $\endgroup$ – FrankW Sep 10 '14 at 13:52
-3
$\begingroup$

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)

Red dashed lines illustrate 4 disconnecting sides (top-bottom, top-left, left-right, bottom-right)

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:

Red dashed lines illustrate 4 disconnecting sides (top-bottom, top-left, left-right, bottom-right)

$\endgroup$
  • $\begingroup$ How long are the updates taking in this solution? $\endgroup$ – Lembik Sep 9 '14 at 9:31
  • $\begingroup$ 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. $\endgroup$ – orezvani Sep 9 '14 at 9:47
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 9 '14 at 18:17
  • $\begingroup$ @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. $\endgroup$ – orezvani Sep 10 '14 at 0:09
  • $\begingroup$ @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. $\endgroup$ – orezvani Sep 10 '14 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.