Séminaire

Date : 28 septembre 2023 13:30 - Salle :Salle A102 Romeo and Juliet Meeting in Forest Like Regions Prafullkumar TALE - IISER Pune, Inde

Séminaire annulé

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 the same vertex and Divider's goal to prevent it. We prove that Rendezvous is co-NP-hard even for graphs of constant treewidth. Further, we show that the problem is co-W[1]-hard when parameterized by the feedback vertex set number and the number of agents, and is unlikely to admit a polynomial kernel when parameterized by the vertex cover number and the number of agents.

The talk will be in English. It is given by Prafullkumar Tale, who is a guest from Florent Foucaud these days. He will speak about a game called "rendezvous" (what a nice name!) for which he will show a nice result that he had. You can find the corresponding paper with a description of the game (and the result) here: https://drops.dagstuhl.de/opus/volltexte/2022/17419/