Search Results

Documents authored by Valla, Tomáš

Document
DOI: 10.4230/LIPIcs.MFCS.2024.54
Romeo and Juliet Is EXPTIME-Complete

Authors: Harmender Gahlawat, Jan Matyáš Křišťan, and Tomáš Valla

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Romeo and Juliet is a two player Rendezvous game played on graphs where one player controls two agents, Romeo (ℛ) and Juliet (𝒥) who aim to meet at a vertex against k adversaries, called dividers, controlled by the other player. The optimization in this game lies at deciding the minimum number of dividers sufficient to restrict ℛ and 𝒥 from meeting in a graph, called the dynamic separation number. We establish that Romeo and Juliet is EXPTIME-complete, settling a conjecture of Fomin, Golovach, and Thilikos [Inf. and Comp., 2023] positively. We also consider the game for directed graphs and establish that although the game is EXPTIME-complete for general directed graphs, it is PSPACE-complete and co-W[2]-hard for directed acyclic graphs.
Cite as

Harmender Gahlawat, Jan Matyáš Křišťan, and Tomáš Valla. Romeo and Juliet Is EXPTIME-Complete. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.MFCS.2024.54,
  author =	{Gahlawat, Harmender and K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Valla, Tom\'{a}\v{s}},
  title =	{{Romeo and Juliet Is EXPTIME-Complete}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.54},
  URN =		{urn:nbn:de:0030-drops-206106},
  doi =		{10.4230/LIPIcs.MFCS.2024.54},
  annote =	{Keywords: Rendezvous Games on graphs, EXPTIME-completeness, Dynamic Separators}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.22
On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Authors: Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.
Cite as

Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ESA.2022.22,
  author =	{Bla\v{z}ej, V\'{a}clav and Choudhary, Pratibha and Knop, Du\v{s}an and Schierreich, \v{S}imon and Such\'{y}, Ond\v{r}ej and Valla, Tom\'{a}\v{s}},
  title =	{{On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.22},
  URN =		{urn:nbn:de:0030-drops-169600},
  doi =		{10.4230/LIPIcs.ESA.2022.22},
  annote =	{Keywords: Traveling Salesperson, Subset TSP, Waypoint Routing, Kernelization}
}
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 About DROPS Imprint Privacy Contact