1 Search Results for "Viramgami, Gaurav"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.27
Romeo and Juliet Meeting in Forest like Regions

Authors: Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
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 ≥ 1 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. Fomin, Golovach, and Thilikos [WG, 2021] introduced this game and proved that it is PSPACE-hard and co-W[2]-hard parameterized by the number of agents. This hardness naturally motivates the structural parameterization of the problem. The authors proved that it admits an FPT algorithm when parameterized by the modular width and the number of allowed rounds. However, they left open the complexity of the problem from the perspective of other structural parameters. In particular, they explicitly asked whether the problem admits an FPT or XP-algorithm with respect to the treewidth of the input graph. We answer this question in the negative and show 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. Complementing these hardness results, we show that the Rendezvous is FPT when parameterized by both the vertex cover number and the solution size. Finally, for graphs of treewidth at most two and girds, we show that the problem can be solved in polynomial time.
Cite as

Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami. Romeo and Juliet Meeting in Forest like Regions. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.FSTTCS.2022.27,
  author =	{Misra, Neeldhara and Mulpuri, Manas and Tale, Prafullkumar and Viramgami, Gaurav},
  title =	{{Romeo and Juliet Meeting in Forest like Regions}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{27:1--27:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.27},
  URN =		{urn:nbn:de:0030-drops-174194},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.27},
  annote =	{Keywords: Games on Graphs, Dynamic Separators, W\lbrack1\rbrack-hardness, Structural Parametersization, Treewidth}
}
  • Refine by Author
  • 1 Misra, Neeldhara
  • 1 Mulpuri, Manas
  • 1 Tale, Prafullkumar
  • 1 Viramgami, Gaurav

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Dynamic Separators
  • 1 Games on Graphs
  • 1 Structural Parametersization
  • 1 Treewidth
  • 1 W[1]-hardness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact