9
$\begingroup$

This is just a little interesting problem I came up with today and I have know idea how to solve it, so that's why I'm posting it here.


Let $G$ be some finite, undirected, connected graph. We give every node a unique identifier, say a positive integer. An ant is placed on some random node. The ant can only 'see' the identifier of the node it's on and the identifiers of the neighbours of the node it's on. Now, every second the ant moves to a neighbour of the node it's currently on. The ant's goal is to detect whether or not $G$ is in fact a tree.

The thing is that the ant only has a finite amount of (rewritable) memory; it can only remember a certain amount of the nodes it has visited. Let $\alpha(G)$ be the minimum amount of memory the ant needs in order to be able to succesfully determine whether or not $G$ is in fact a tree.

Question 1: How do we determine $\alpha(G)$?

Question 2: Given $n\in\mathbb{N}$, can we specicify all graphs $G$ with $\alpha(G)=n$?

Bonus Question: Is there an algorithm the ant can always use?


What I've found so far:
What I've found so far is that if $G$ is a cycle, we have $\alpha(G)\le 3$. When the ant starts, it saves the identifiers of the node it's on and of it's two neighbours into memory. Then it randomly moves to one of its neighbours. After this, it simply substitutes the identifier of the neighbour it has in memory with the identifier of the other neighbour and moves to the node with the saved identifier. As soon as all neighbourrs' identifiers are in memory, the ant knows it must've travelled in a cycle and therefore $G$ could not have been a tree.

Also, if $G$ is an 'eight' (two cycles with some consecutive common nodes), we have $\alpha(G)\le 4$. We use the same algorihm as with cycles, but if we get to a point where the node the ant is on has three neighbours, two of which with their idenitfier not in memory, we choose to ignore one and move on with our algorithm. The only thing we do, is saving the identifier of that third neighbour in memory, the first time and the second time (when all memory is used), we do nothing. Travelling along one of the cycles, we will unavoidably end up next to one of these 'permanently marked' nodes and hence, we'll be able to decide it's not a tree.

If $G$ is a complete graph with more than two vertices, we can take $\alpha(G)\le 2$. When the ant starts off, it puts the identifier of the node it's on and the identifier of one of its neighbours into memory, after which it moves to one of the neighbours whose identifier is not stored in memory. If it now has two neighbours with their identifiers in memory (it has), the graph must contain a triangle and therefore can't be a tree.

$\endgroup$
  • $\begingroup$ I'm not sure if asking $\alpha(G)$ for a specific graph $G$ makes sense: $G$ is either a tree or not, so one of the zero-memory algorithms "say $G$ is a tree" or "say $G$ is not a tree" is valid. It makes sense to take a class $\mathcal G$ of graphs, containing both trees and non-trees, and compute $\alpha(\mathcal G)$: the memory needed for an ant placed on a graph from this class to tell if the graph is a tree or not. $\endgroup$ – Misha Lavrov Oct 25 '17 at 0:15
2
$\begingroup$

We can test any graph for being a tree with $n=4$ if the ant is allowed a small "trick": being able to sort vertex identifiers (the ones it can see or remember) by size. This makes sense if the vertex identifiers are integers, not so much if the vertices are given unique colors or something.

If we can do this, then we can take a tour of the graph $G$ by using the following rule (called the tour rule): whenever you enter a node $v$ from node $w$, the next node you go to should be either:

  • The neighbor of $v$ which has the smallest label greater than $w$, or
  • When there is no such neighbor ($w$ had the largest label among neighbors of $v$) the neighbor of $v$ which has the smallest label.

Just implementing this rule requires one memory cell, used to remember the label on $w$.

If the graph $G$ is a tree, we end up walking around the perimeter of a planar embedding of $G$, traversing each edge once in each direction. If $G$ is not a tree, we might traverse all edges or just a subset. What distinguishes trees from non-trees is the following characterization:

$G$ is a tree if and only if this tour has the following property (called the backtrack property): whenever we leave a node $v$ to go to $x$, the next time we see $v$ it is by coming back from $x$.

(The backtrack property is forced for any tour of a tree, because there are no cycles. The converse is trickier to see, but can be proved by induction on the size of $G$: essentially, a tour with the backtrack property can only "turn around" at a vertex of degree $1$, and omitting this vertex gives a tour with the backtrack property on a smaller graph.)

So we can check if $G$ is a tree by checking the backtrack property for each edge of the tour. More precisely, we use the following algorithm.

Memory cells used:

  • START: the node we started on.
  • SOURCE, TARGET: the two endpoints of the edge of the tour we're checking to see if the backtrack property is satisfied.
  • LAST-VISITED: the vertex we were at in the previous step (needed to implement the tour rule).

Algorithm:

  1. Initialize START. Set SOURCE to START, and set TARGET to the neighbor of START with the lowest label.
  2. Begin the tour by going to that neighbor, updating LAST-VISITED to START as we leave it.
  3. Keep following the tour rule, updating LAST-VISITED appropriately (I'll assume we do this without mention from now on).
  4. When we next arrive at SOURCE: if LAST-VISITED is not TARGET, then the backtrack property is not satisfied, so $G$ is not a tree.
  5. Otherwise, we restart the tour from the point when we were going from SOURCE to TARGET. That is, we set SOURCE to the value of TARGET, and take a step to TARGET.
  6. On the next step (which the ant may identify, if it is very forgetful, by the property that SOURCE is equal to TARGET) we set TARGET equal to the next destination along the tour, and go back to step 3.
  7. When we find ourselves with SOURCE equal to START and setting TARGET equal to the neighbor of START with the lowest label, we know that we're checking that edge for the second time, so we've checked all the edges and know that $G$ is a tree.

(Over the course of this algorithm, SOURCE and TARGET inch their way along the tour, while the ant traces over parts of the tour many times over.)

$\endgroup$

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.