Communications of the ACM
Last byte
Find Me Quickly
In this cooperative game, two players want to meet each other in a graph as quickly as possible. Meeting each other means both players are at the same node at the same time or traverse an edge in opposite directions in some minute. Each player moves or stays put each minute. A move takes one player from one node across an edge to a neighboring node in the undirected graph.
Warm-up: Suppose the two players are in a graph consisting of a cycle of n nodes (see Figure 1). The nodes are numbered, and each player knows both the topology and the number of the node where he or she is placed. If both players move, say, clockwise, they may never meet. If player A does not move (the "stay-put" strategy) and player B moves in one direction, player B will find player A in n-1 minutes in the worst case. Alternatively, if both agree to move as quickly as possible to some node, say, node 4, and stay there, then the latter of the two will arrive at node 4 in n/2 minutes at most. Is there any other strategy that has a worst-case time complexity of n/2 minutes but also a better average-case time complexity than the go-to-a-common-node strategy?
Solution to warm up. Player A can always move clockwise (given a map of the graph for which clockwise makes sense), and player B can always move counterclockwise. They will meet each other in at most n/2 minutes in the worst case, with an expected value less than the go-to-a-common-node strategy.
A graph consisting of a single cycle is, of course, a special case. For an arbitrary graph of size n, where each player knows his or her own position and the topology of the graph and where every node has a unique identifier, is there a solution that will take no more than n/2 minutes in the worst case?
Solution. Go to the centroid of the graph, or the node to which the maximum distance from any other node is minimized. If there are several such nodes, go to the one with the lexicographically minimum node id. Note that such a centroid cannot have a distance greater than n/2 to any other node.
We are just getting started. Now consider situations in which each player knows the topology but not where he or she is placed and the nodes have no identifiers.
Start by considering a graph consisting of a single path. If player A stays put and player B moves in one direction and bounces back from the end if player B does not find A, the worst-case time could be 2n-3 minutes. Is there a strategy that takes no more than n minutes in the worst case?
Solution. Yes, each player goes in some direction, and when that player hits an end, he or she bounces back. In the worst case, this strategy takes n-1 minutes, with an expected value of approximately 3n/4.
Now for the upstarts:
Upstart 1. Better than staying put. When both players do not know where they are placed, nodes are unlabeled and the graph has at least one cycle, find a strategy that is better in the worst case than the one-player-stays-put strategy.
Upstart 2. Also better than staying put. In the same setting as Upstart 1, say we allow both players to leave notes (see Figure 2) on nodes they have visited. Is there an approach that takes n/2 minutes for the two players to meet up in the worst case? If not, is there an approach that takes 3n/2 minutes in the worst case? Please specify whichever approach you come up with.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
Figures
Figure 1. The goal is for two players who know the topology of a graph to find one another as quickly as possible.
Figure 2. Suppose each player ("Alice" in this case) could leave a small number of notes identifying herself along with any other information she might want to include.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2016 ACM, Inc.
No entries found