Find a path whose length can be divided by 3

Question

Given an undirected graph (not weighted) and two vertices u and v, how can I find a path between u and v whose length is divisible by 3?

Note that the path need not necessarily be a simple path.

I thought about a variation of DFS and a stack that stores the path (and for backtracking), but cannot fully understand how to keep track of non-simple paths as well.

The time complexity should be O(V+E), so I expect it must be a variant of BFS or DFS.

Answer 1

One way to do this is to compute a modified version of the graph and do a BFS or DFS on that graph.

Imagine stacking the graph on top of itself three times. Each node now appears three times. Annotate the first copy as "mod 0," the second copy as "mod 1," and the third copy as "mod 2." Then, change the edges so that any edge from a node u to a node v always goes from the node u to the node v in the next layer of the graph. Thus if there was an edge from u to v, there is now an edge from u mod 0 to v mod 1, u mod 1 to v mod 2, and u mod 2 to v mod 0. If you do a BFS or DFS over this graph and find a path from u mod 0 to any node v mod 0, you necessarily have a path whose length must be a multiple of three.

You can explicitly construct this graph in time O(m + n) by copying the graph two times and rewiring the edges appropriately, and from there a BFS or DFS will take time O(m + n). This uses memory Θ(m + n), though.

An alternative solution would be to simulate doing this without actually building the new graph. Do a BFS, and store for each node three distances - a mod 0 distance, a mod 1 distance, and a mod 2 distance. Whenever you dequeue a node from the queue, enqueue its successors, but tag them as being at the next mod layer (e.g. if you dequeued a node at level mod 0, enqueue its successors at mod 1, etc.) You can independently track whether you have reached a node at distances mod 0, mod 1, and mod 2, and should not enqueue a node at a given mod level multiple times. This also takes time O(m + n), but doesn't explicitly construct the second graph and thus only requires O(n) storage space.

Hope this helps!

Answer 2

A cheating way:

Just DFS/BFS from A to B; if the length L % 3 == 0, finish; L % 3 == 1, walk to a neighbour and back; else, walk to a neighbour and back and there and back again.

---

If that does not meet your constraints, then:

You could do this using a modified BFS. While doing the search, try to mark all the cycles you encounter; you can get all the simple cycles along with the lengths.

After that, if the path from A to B has length L % 3 == 0, then you found it.

If not, then in the case where all the cycle has lengths Lk % 3 == 0, there's no solution;

If there are some cycles with length K % 3 != 0, you could first go from A to this cycle, cycle one or two times then go back to A then to B. You are guaranteed to find a length 3 path this way.