5 Search Results for "Cohen, Nathann"


Document
Invariants for One-Counter Automata with Disequality Tests

Authors: Dmitry Chistikov, Jérôme Leroux, Henry Sinclair-Banks, and Nicolas Waldburger

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)


Abstract
We study the reachability problem for one-counter automata in which transitions can carry disequality tests. A disequality test is a guard that prohibits a specified counter value. This reachability problem has been known to be NP-hard and in PSPACE, and characterising its computational complexity has been left as a challenging open question by Almagor, Cohen, Pérez, Shirmohammadi, and Worrell (2020). We reduce the complexity gap, placing the problem into the second level of the polynomial hierarchy, namely into the class coNP^NP. In the presence of both equality and disequality tests, our upper bound is at the third level, P^NP^NP. To prove this result, we show that non-reachability can be witnessed by a pair of invariants (forward and backward). These invariants are almost inductive. They aim to over-approximate only a "core" of the reachability set instead of the entire set. The invariants are also leaky: it is possible to escape the set. We complement this with separate checks as the leaks can only occur in a controlled way.

Cite as

Dmitry Chistikov, Jérôme Leroux, Henry Sinclair-Banks, and Nicolas Waldburger. Invariants for One-Counter Automata with Disequality Tests. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chistikov_et_al:LIPIcs.CONCUR.2024.17,
  author =	{Chistikov, Dmitry and Leroux, J\'{e}r\^{o}me and Sinclair-Banks, Henry and Waldburger, Nicolas},
  title =	{{Invariants for One-Counter Automata with Disequality Tests}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.17},
  URN =		{urn:nbn:de:0030-drops-207898},
  doi =		{10.4230/LIPIcs.CONCUR.2024.17},
  annote =	{Keywords: Inductive invariant, Vector addition system, One-counter automaton}
}
Document
On the Complexity of Community-Aware Network Sparsification

Authors: Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

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


Abstract
In the NP-hard Π-Network Sparsification problem, we are given an edge-weighted graph G, a collection 𝒞 of c subsets of V(G), called communities, and two numbers 𝓁 and b, and the question is whether there exists a spanning subgraph G' of G with at most 𝓁 edges of total weight at most b such that G'[C] fulfills Π for each community C ∈ 𝒞. We study the fine-grained and parameterized complexity of two special cases of this problem: Connectivity NWS where Π is the connectivity property and Stars NWS, where Π is the property of having a spanning star. First, we provide a tight 2^Ω(n²+c)-time running time lower bound based on the ETH for both problems, where n is the number of vertices in G even if all communities have size at most 4, G is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with G being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number t of the solution graph G'. For Stars NWS, we present an XP-algorithm for t answering an open question by Korach and Stern [Discret. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for t = 0. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for t = 0 [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended to larger values of t by showing NP-hardness for t = 1.

Cite as

Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. On the Complexity of Community-Aware Network Sparsification. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{herrendorf_et_al:LIPIcs.MFCS.2024.60,
  author =	{Herrendorf, Emanuel and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{On the Complexity of Community-Aware Network Sparsification}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{60:1--60:18},
  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.60},
  URN =		{urn:nbn:de:0030-drops-206169},
  doi =		{10.4230/LIPIcs.MFCS.2024.60},
  annote =	{Keywords: parameterized complexity, hypergraph support, above guarantee parameterization, exponential-time-hypothesis}
}
Document
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
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
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}
}
  • Refine by Author
  • 3 Cohen, Nathann
  • 2 Nisse, Nicolas
  • 2 Pérennes, Stéphane
  • 1 Almagor, Shaull
  • 1 Chistikov, Dmitry
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Models of computation
  • 1 Mathematics of computing → Hypergraphs
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Graph algorithms
  • 1 Inductive invariant
  • 1 Linear Programming
  • 1 One-counter automaton
  • 1 Reachability
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2024
  • 1 2016
  • 1 2017
  • 1 2020

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