Collaborative graph exploration algorithm

Question

Given a minimum spanning tree in an unweighted graph of (10 .. 500) vertices and (vertice_count .. 1000) edges. Each vertex can have up to 6 edges.

Given K agents/bots/processes/etc.., all starting from the root of the spanning tree.

What would be the best way to distribute the "work" to explore the graph (eg. visit all the vertices) in as little time as possible?

Any ideas/strategies/algorithms that can allocate the exploration to the agents and deal with the ones that have reached a leaf but might help contribute to the exploration later?

Let's see an example. Here's a graph, the orange node is the starting point, the grey nodes are the leaves and the number inside the nodes are the number of paths going through that node to one of the leaves.

Obviously, if K=8, then each agent is affected one "path" (or leaf) and once everyone has done their job, they will have explored the whole graph is as little time as possible.

Now my problem is how to organize the exploration when K<8? How to best re-affect the free agents?

Answer 1

Initial answer to the initial question

Important remark: the question was significantly edited. The original question only mentioned the need to explore all the nodes of the graph without mentioning MST. Despite it is now obsolete, I leave the first paragraph, because it linked to parallel algorithms solving the problem.

Your question is very broad. First let's give a name to your problem aiming at exploring all the edges: you want to build a minimum spanning tree of your graph. And when you say collaboratively, I undestand with concurrent processes. For this there are knwon parallel algorithms that are proven to work.

General approach when parallelizing graph exploration

More generally, you may apply the following advices for parallelizing graph exploration and traversal problems:

• Many graph algorithms use a queue or a stack, to store partial paths to be extended further. Some version of DFS hide the stack in the call stack.
  If there is a queue based version of the algorithm use it: Without queue, it's more difficult to share work, and you need to find other ways to apply the following tricks.

• The trick for easy parallelization is to distribute queued elements for being processed by available processing nodes. So instead of extending the explored path one edge at a time, you'd extend N nodes in the same time in parrallel. Using queues to distribute work is the easiest way to parllelize work: one process manages the queue, and N worker-processes dequeue the elements, process them and enqueue the results.

  

• Most graph traversal algorithms are inherently sequential. Parallelizing them means that you might aggressively process elements in the queue that would never be processed in the sequential version. So there is a tradeoff to find between adding more workers (with the risk of doing unnecessary work) and having less workers (but going back to sequential like performance).

So be prepared to make measurements and validate your approach.
A long time ago, I had for example to parallelize A* on a limited set of geographical data. Measurements showed that adding up to 4 worker-nodes increased performance, but beyond 4, the performance decreased again, just because of the additional communication overhead and the unnecessary extension of unpromising partial paths.

Edit: considering that all the edges are same-weighted, the risk of processing suboptimal nodes in the queue are significantly reduced if you use DFS. So if you can modify BFS in a way to make sure that it ends the search if and only if all the nodes were explored, go for it;

Example based on your new graph example.

Your visual reasoning about branches of the MST is not valid for solving your problem:

• First, building your MST already requires you to explore every node
• Second, graph exploration algorithms have to unfold node by node and edge by edge.
  When you start at the orange node, you don't know how many branches there will be in the MST nor which part of the graph to assign to which worker.
  

With the approach proposed above, you'd enqueue the first node (orange 8). A free worker dequeues it, prolonges the path and enqueue the single result (O8->8). As we are in a "corridor", the same must happen again (O8->8->8) before we have more choices and more parallelism. Then a free worker-process dequeues the only path in the queue, extends it: we have 2 alternatives that will be enqueued: O8->8->8->6 and 08->8->8->2. Now a first worker will take the first path in the queue (...->6), another free worker will take the second path (...->2), and both workers extend in parallel their nodes. If both workers have the same speed, we now have 5 paths in the queue and up to 5 workers busy, and so on.

Of course, you'll notice that O8->8->8->6->bottom2 and O8->8->8->2 arrive at the same point. In your exploration you must avoid such duplicates. This can be done by marking visited nodes to avoid double visit. This cannot be done safely in the workers because of synchronisation issues. So you may implement this when you enqueue the results and discard any path that arrives at an already visited node.

With this approach, everytime there's a branch, you'll use more pralelism until you reach the maximum number of workers. However in your simple graph, I think that you'll never have more than 5 workers active at the same time, that's 6 parallel processes if you add the queue manager.

The worst case is when you graph is a long chain of nodes, each one linked only with a successor. It will run with 2 active processes only: worse than sequential because of the overhead of work distribution.

Other variants

There are other parallelization of task possible, without adding workers, for example parrallelizing the sorting of the queue, the filtering of doubled targets, etc...

If your graph topology is a bottleneck for parallization, you may introduce some randomness. Take K random nodes and start exploration from there; when enqueuing in the global queue, any path with nodes in common would be merged. As soon as one of the processor gets iddle, pick a new random unvisited node and add it to the queue.

This variant adds a small inefficiency: some nodes might get visited twice, once from each connection. It's those that lead to a path merger. But it keeps all the processors as busy as possible. In your example, most of the time 8 processors will work instead of a maximum of 5 before.

And this is why in my original answer, I adviced to carefully measure performance, to find the most suitable parallelization strategy (which might also depend on the graph topology).

Answer 2

Thanks a lot @Christophe for all your time and hard work answering my poorly asked question. You definitely deserve the bounty 👏

However, I've dug into the research papers and found that what I want to do is not "easily" solvable...

What I want to do is exactly this - Fast collaborative graph exploration

We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. We ask how many time steps are required to complete exploration, i.e., to make sure that every vertex has been visited by some agent.

Or similarly explained in Graph Explorations with Mobile Agents

Collective exploration requires a team of k agents that start from the same location, to explore together all the nodes of the graph, such that each node is visited by at least one of the agents. The agents are assumed to have distinct identifiers such that each agent can be assigned a distinct path to explore. Assuming that all agents move with the same speed (i.e. they are synchronized), the main objective is to minimize the time needed for exploration.

When the graph is known in advance, it is possible to devise a strategy to divide the task among the agents such that each agent travels on a distinct tour and they together span the nodes of the graph. We call this an offline strategy for exploration; finding the optimal offline strategy that minimizes the maximum tour length of any agent for a given graph G and team size k is known to be an NP-hard problem even for trees.

And more specifically this - Collective tree exploration

In the offline model, when the graph is known in advance, the problem of establishing an optimal sequence of moves for k agents in a [graph] is shown to be NP-hard.

So, as it turns out, this is a well-researched problem and is NP-hard. I guess I'm gonna have to find heuristics then.