DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2020.38

Coverability in 1-VASS with Disequality Tests

Authors: Shaull Almagor, Nathann Cohen, Guillermo A. Pérez, Mahsa Shirmohammadi, and James Worrell

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

Abstract

We study a class of reachability problems in weighted graphs with constraints on the accumulated weight of paths. The problems we study can equivalently be formulated in the model of vector addition systems with states (VASS). We consider a version of the vertex-to-vertex reachability problem in which the accumulated weight of a path is required always to be non-negative. This is equivalent to the so-called control-state reachability problem (also called the coverability problem) for 1-dimensional VASS. We show that this problem lies in NC: the class of problems solvable in polylogarithmic parallel time. In our main result we generalise the problem to allow disequality constraints on edges (i.e., we allow edges to be disabled if the accumulated weight is equal to a specific value). We show that in this case the vertex-to-vertex reachability problem is solvable in polynomial time even though a shortest path may have exponential length. In the language of VASS this means that control-state reachability is in polynomial time for 1-dimensional VASS with disequality tests.

Cite as

Shaull Almagor, Nathann Cohen, Guillermo A. Pérez, Mahsa Shirmohammadi, and James Worrell. Coverability in 1-VASS with Disequality Tests. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{almagor_et_al:LIPIcs.CONCUR.2020.38,
  author =	{Almagor, Shaull and Cohen, Nathann and P\'{e}rez, Guillermo A. and Shirmohammadi, Mahsa and Worrell, James},
  title =	{{Coverability in 1-VASS with Disequality Tests}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.38},
  URN =		{urn:nbn:de:0030-drops-128501},
  doi =		{10.4230/LIPIcs.CONCUR.2020.38},
  annote =	{Keywords: Reachability, Vector addition systems with states, Weighted graphs}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.22

Study of a Combinatorial Game in Graphs Through Linear Programming

Authors: Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

In the Spy Game played on a graph G, a single spy travels the ertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guardnumber of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.

Cite as

Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes. Study of a Combinatorial Game in Graphs Through Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ISAAC.2017.22,
  author =	{Cohen, Nathann and Mc Inerney, Fionn and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Study of a Combinatorial Game in Graphs Through Linear Programming}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.22},
  URN =		{urn:nbn:de:0030-drops-82254},
  doi =		{10.4230/LIPIcs.ISAAC.2017.22},
  annote =	{Keywords: Turn-by-turn games in graphs, Graph algorithms, Linear Programming}
}

Document

DOI: 10.4230/LIPIcs.FUN.2016.10

Spy-Game on Graphs

Authors: Nathann Cohen, Mathieu Hilaire, Nícolas A. Martins, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract

We define and study the following two-player game on a graph G. Let k in N^*. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s in N^* is his speed. Then, each guard may move along one edge. The spy and the guards may occupy same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than d in N (a predefined distance) from every guard. Can the spy win against k guards? Similarly, what is the minimum distance d such that k guards may ensure that at least one of them remains at distance at most d from the spy? This game generalizes two well-studied games: Cops and robber games (when s=1) and Eternal Dominating Set (when s is unbounded). We consider the computational complexity of the problem, showing that it is NP-hard and that it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards and the required distance d when G is a path or a cycle. Our main result is that there exists beta>0 such that Omega(n^{1+beta}) guards are required to win in any n*n grid.

Cite as

Nathann Cohen, Mathieu Hilaire, Nícolas A. Martins, Nicolas Nisse, and Stéphane Pérennes. Spy-Game on Graphs. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.FUN.2016.10,
  author =	{Cohen, Nathann and Hilaire, Mathieu and Martins, N{\'\i}colas A. and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Spy-Game on Graphs}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.10},
  URN =		{urn:nbn:de:0030-drops-58782},
  doi =		{10.4230/LIPIcs.FUN.2016.10},
  annote =	{Keywords: graph, two-player games, cops and robber games, complexity}
}

Search Results

Documents authored by Cohen, Nathann

Coverability in 1-VASS with Disequality Tests

Abstract

Cite as

Study of a Combinatorial Game in Graphs Through Linear Programming

Abstract

Cite as

Spy-Game on Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message