DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.8

Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception

Authors: Jean-Claude Bermond, Michel Cosnard, Frédéric Havet, Takako Kodate, and Stéphane Pérennes

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

We introduce and study the directed grabbing game, a directed variation of the graph grabbing game played by two players Alice and Bob on a weighted acyclic digraph D. Alice plays first and then they play alternately. At a given odd (resp. even) move, Alice (resp. Bob) chooses a sink, that is a vertex of out-degree 0, grabs the weight (olives) on it and then removes the vertex. The aim of each player is to grab a maximum weight, i.e. a maximum number of olives. This game is inspired by the behaviour that guests are expected to adopt during a reception or cocktail party. We first consider the case where hors d'oeuvre are arranged on slightly spaced parallel lines, such that politeness allows one to take the first hors d'oeuvre from each line. This corresponds to the directed grabbing game on a union of disjoint directed paths. We give an algorithm that, given a weighted digraph D of order n which is the union of q disjoint directed paths, computes an optimal play in O(nlog q) time. Then we consider the "pissaladière case" where the digraph D is a directed (p× q)-grid. We show that, depending on the parity of pq, one player, called Content, has a strategic advantage. Specifically, Content is Alice when pq is odd and Bob when pq is even. We present some strategies that enable Content to remove some large sets of vertices (of order pq/2) in directed grids. We then derive that Content can remove any given vertex that is not in the border of the grid. Finally, in the case where each vertex contains either zero or one olive, we prove that Content can secure the grabbing of around one third of the olives.

Cite as

Jean-Claude Bermond, Michel Cosnard, Frédéric Havet, Takako Kodate, and Stéphane Pérennes. Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2026.8,
  author =	{Bermond, Jean-Claude and Cosnard, Michel and Havet, Fr\'{e}d\'{e}ric and Kodate, Takako and P\'{e}rennes, St\'{e}phane},
  title =	{{Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.8},
  URN =		{urn:nbn:de:0030-drops-257273},
  doi =		{10.4230/LIPIcs.FUN.2026.8},
  annote =	{Keywords: grabbing games, paths, directed grids}
}

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}
}

Document

DOI: 10.4230/LIPIcs.STACS.2014.75

Weighted Coloring in Trees

Authors: Julio Araujo, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.

Cite as

Julio Araujo, Nicolas Nisse, and Stéphane Pérennes. Weighted Coloring in Trees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 75-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.STACS.2014.75,
  author =	{Araujo, Julio and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Weighted Coloring in Trees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{75--86},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.75},
  URN =		{urn:nbn:de:0030-drops-44484},
  doi =		{10.4230/LIPIcs.STACS.2014.75},
  annote =	{Keywords: Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3-SAT}
}

Search Results

Documents authored by Pérennes, Stéphane

Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception

Abstract

Cite as

Study of a Combinatorial Game in Graphs Through Linear Programming

Abstract

Cite as

Spy-Game on Graphs

Abstract

Cite as

Weighted Coloring in Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message