Romeo and Juliet Meeting in Forest Like Regions
Joint work with Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami ⸱ To Appear at FSTTCS 2022 ⸱ Preprint available from ArXiV
The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k agents. While the initial positions of Facilitator’s agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with k agents. In this work, we prove that this problem is hard even when the graph is very close to a forest.
