Explore each node in a graph.

Question

I am assigned a connected graph with N nodes (numbered from 1..N) and M bidirectional edges consisting of a pair (A, B). The edges are not weighted.

I have K people starting with node 1, and I want to learn each node of the graph. I take one unit of time so that a person travels from one node to one of his neighbors.

How long does it take to learn all the node? I am looking for an efficient algorithm to calculate the minimum transit time, but I am afraid that this is an NP-complete problem. (The limits on the number of ribs and the number of people are small, though).

Answer 1

Suppose that K is 1. Then the minimization problem comes down to finding a path of minimum length that affects each node at least once.

If we construct a new weighted graph G 'with the same nodes and with edges between every two nodes whose weight is the minimum distance between these nodes in the original graph, then the path of minimum length through all nodes in G is the minimum length of the Hamiltonian trajectory through G', a traveling seller problem that is well known as NP-complete.

So, for at least one value of K, the problem is NP-complete. However, for large values ​​of K (say, & ge; N), we can get the minimum solution in much less time, since we can simply build the minimum spanning tree and find the distance from the farthest element. I doubt if there is such a simplified solution for small K values, but I would definitely use MST as a heuristic to find a reasonable solution.