Detecting Connected Components on an Infinite Graph after Modification

Question

This puzzle was inspired by thinking about how to implement a system like Factorio's power grid.

Start with an infinite connected undirected acyclic graph.

• Graph = A set of nodes (called "vertices") with connections (called "edges") between them.
  • Alternatively: A set of power poles connected by wires.
• Undirected = Edges are bidirectional; if vertex 1 connects to vertex 2, then vertex 2 also connects to vertex 1 by the same edge.
• Infinite = The graph has an infinite number of vertices
• Connected = A path (consisting of 1 or more edges) exists from any vertex to any other vertex
• Acyclic = No path (consisting of 1 or more edges) exists from any vertex back to itself.

You know the structure of this graph. Even if you can't fit the whole graph in your head at the same time (because it's infinite), given any vertex, you can know what other vertices it is connected to.

After that, an outside entity makes a finite number of modifications to the edges of the graph (e.g. removing or adding edges). Adding edges might make the graph stop being acyclic, removing edges might make the graph stop being connected. You can observe these changes (you know what edges were added or removed), but you cannot influence them or modify the graph yourself.

Design an algorithm such that after any number of modifications is made, you can tell whether or not any pair of vertices remain connected.

The algorithm must complete in finite time in all cases.

Answer 1

The original graph

is a tree.

Suppose we want to know whether vertices A and B (after finitely many known additions and removals of edges) are connected. Then:

let S consist of A, B, and all vertices that are part of added or removed edges. Search outward from the vertices in S, breadth-first, in the original tree, until you have a single subtree T containing all those vertices. (If d is the maximum distance-in-the-tree between any two of the finitely many vertices in S, then after you have explored to distance d everything you've found will be connected. You don't know ahead of time what d is, but you do know it exists.)

Now

any two vertices in modified-T are connected in the (whole) modified graph if, and only if, they are connected in modified-T. Proof: "if" is trivial; suppose "only if" fails, and let x,y be vertices in modified-T that are connected in the whole modified graph but not in modified-T, chosen so that the distance from x to y is as short as possible. Then the shortest path joining x and y lies entirely outside modified-T, which means it is a path in the original tree. But in the original tree there is exactly one path joining x and y, and it lies entirely inside T: contradiction.

So

we can now test whether A and B are connected by searching only within modified-T, which is finite.

Answer 2

It turns out that we can mostly ignore finiteness or lack thereof since the relevant feature, the unique connecting path between any two vertices, is always finite.

Let's look at removals of edges first:

Let us call two vertices sub-connected if their original (unique, finite) connecting path does not contain any of the removed edges. This is clearly an equivalence relation. The equivalence classes are the connected components of the reduced graph and they are all trees. Further, the endpoints of removed edges form a full set of (not necessarily unique) representative vertices.

For any added edge

we can now simply check whether their endpoints reside in different connected components and if so merge those components.

To make this step more concrete: 1. retrieve the original connecting path. 2. check if any of it was removed. 3. if so take the first vertex of the first removed edge and the second vertex of the last removed edge and merge (i.e. mark as merged) the trees they represent.

The final test for connectedness of two arbitrary vertices is similar:

1. retrieve their original connecting path. 2. check whether any of it was removed. If not return yes. 3. check whether the connected components represented by the first vertex of the first removed edge and the second vertex of the last removed edge were marked as merged. If so return yes, if not return no.

Answer 3

Original Solution

Here is the algorithm I had in mind when I posted the question.

During the modification phase, we need to keep track of

Connected components and cycles.
For cycles, we track each as an ordered list of vertices for each cycle which does not include other cycles. A cycle is said to include another cycle if every vertex from the smaller cycle is in the larger cycle.
For connected components, we will consider one vertex as the "canonical" member of the component. As long as every component contains exactly one canonical vertex, we can flood-fill from any vertex and will reach that component's canonical vertex in finite time.

To begin with:

The list of cycles is empty.
All vertices are part of the same component, so there is only a single canonical vertex.

Whenever an edge is added:

If each end is in a different component, combine the components by un-marking the canonical vertex of one of the two components.
If both ends are currently part of the same cycle, split that cycle into two smaller cycles.
Otherwise, add a cycle to the list containing the shortest path from one end to the other that does not include the newly added edge.

Whenever an edge is removed:

If it is part of exactly one cycle, remove that cycle.
If it is part of exactly two cycles, combine those cycles into one larger cycle.
I do not believe it is possible for a single edge to be part of more than two minimal cycles.
If it is not part of a cycle, then it must be creating a new connected component. Flood fill from each end until we find a canonical vertex. Mark the vertex which did not find a canonical vertex as a new connected component.

Whenever a query is issued:

Flood fill from both ends until either both ends find different canonical vertices (disconnected), or the two searches cross eachother (connected).

---

Commentary

The original problem, as mentioned in the question, is tracking "what's plugged in to what" in a game like Factorio - the player is adding and removing wires, and every time a wire is created or removed, we need to immediately update the network - maybe one of the sub-grids needs to shut down for lack of power, etc.

While examining this problem, I noticed an interesting property:

Every time an edge is added, either the number of minimal cycles increases by 1, or the number of disjoint components decreases by one.
Every time an edge is removed, the reverse happens.

This property is likely well known in graph theory and I'm re-inventing the wheel. I'm sure I could look it up if I knew the proper mathematical name for what I'm calling a "minimal cycle." It would likely be phrased as something like:

Count of vertices = Count of edges + Count of disjoint components - Count of minimal cycles

I wanted to pose a puzzle that would lead people to this property.

Unfortunately, there's a very obvious brute force algorithm (flood filling the entire graph every time a modification occurs) which does not utilize this property. In translating from "programming" to "pure math," I attempted to rewrite the problem so that "too slow" would become "infinitely slow," but I didn't account for ways to reduce the space to finite, nor that it was possible to ignore cycles entirely by processing all additions after all removals.