Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

Romeo and Juliet Meeting in Forest Like Regions

Published

Sep 20, 2022

Abstract

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.


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×