Author name cluster

Aline Parreau

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

TCS Journal 2024 Journal Article

Bipartite instances of INFLUENCE

Eric Duchêne
Nacim Oijid
Aline Parreau

The game Influence is a scoring combinatorial game that has been introduced in 2021 by Duchêne et al. [5]. It is a good representative of Milnor's universe of scoring games, i. e. games where it is never interesting for a player to miss their turn. New general results are first given for this universe, by transposing the notions of mean and temperature derived from non-scoring combinatorial games. Such results are then applied to Influence to refine the case of unions of segments started by Duchêne et al. [5]. The computational complexity of the score of the game is also solved and proved to be PSPACE-complete. We finally focus on some specific cases of Influence when the graph is bipartite, by giving explicit strategies and bounds on the optimal score on structures like grids, hypercubes or tori.

Details DOI

TCS Journal 2024 Journal Article

Smash and grab: The 0 ⋅ 6 scoring game on graphs

Éric Duchêne
Valentin Gledel
Sylvain Gravier
Fionn Mc Inerney
Mehdi Mhalla
Aline Parreau

In this paper, we introduce and study a new scoring game on graphs called smash and grab. In this game, two players, called Left and Right, take turns removing a vertex of the graph as well as all of its neighbours that become isolated by this removal. For each player and each of their turns, they score the number of vertices that were removed on their turn. The game ends when there are no more vertices remaining, and the player with the highest final score wins. We denote by L s ( G ) the difference between Left and Right's final scores in G when Left starts and both players play optimally (they both aim to maximise their scores). We mainly study this parameter for different graph classes. We notably prove that L s ( F ) ≥ 0 for any forest F (i. e. , the first player cannot lose). We then use this result to compute the exact value of L s ( G ) for particular forests such as unions of paths and subdivided stars. The result in paths then solves the case of a unique cycle. Finally, we prove that, for a generalisation of the game, computing the score is PSPACE-complete.

Details DOI

TCS Journal 2021 Journal Article

influence: A partizan scoring game on graphs

Eric Duchêne
Stéphane Gonzalez
Aline Parreau
Eric Rémila
Philippe Solal

We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor's universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.

Details DOI

TCS Journal 2018 Journal Article

Octal games on graphs: The game 0.33 on subdivided stars and bistars

Laurent Beaudou
Pierre Coupechoux
Antoine Dailly
Sylvain Gravier
Julien Moncel
Aline Parreau
Éric Sopena

Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, playing an octal game on a path P n is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0. 33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.

Details DOI

TCS Journal 2018 Journal Article

The switch operators and push-the-button games: A sequential compound over rulesets

Eric Duchêne
Marc Heinrich
Urban Larsson
Aline Parreau

We study operators that combine combinatorial games. This field was initiated by Sprague–Grundy (1930s), Milnor (1950s) and Berlekamp–Conway–Guy (1970–80s) via the now classical disjunctive sum operator on (abstract) games. The new class consists in operators for rulesets, dubbed the switch-operators. The ordered pair of rulesets ( R 1, R 2 ) is compatible if, given any position in R 1, there is a description of how to move in R 2. Given compatible ( R 1, R 2 ), we build the push-the-button game R 1 ⊚ R 2, where players start by playing according to the rules R 1, but at some point during play, one of the players must switch the rules to R 2, by pushing the button ‘⊚’. Thus, the game ends according to the terminal condition of ruleset R 2. We study the pairwise combinations of the classical rulesets Nim, Wythoff and Euclid. In addition, we prove that standard periodicity results for Subtraction games transfer to this setting, and we give partial results for a variation of Domineering, where R 1 is the game where the players put the domino tiles horizontally and R 2 the game where they play vertically (thus generalizing the octal game 0. 07).

Details DOI

I&C Journal 2017 Journal Article

Deciding game invariance

Eric Duchêne
Aline Parreau
Michel Rigo

In a previous paper, Duchêne and Rigo introduced the notion of invariance for take-away games on heaps. Roughly speaking, these are games whose rulesets do not depend on the position. Given a sequence S of positive tuples of integers, the question of whether there exists an invariant game having S as set of P -positions is relevant. In particular, it was recently proved by Larsson et al. that if S is a pair of complementary Beatty sequences, then the answer to this question is always positive. In this paper, we show that for a fairly large set of sequences (expressed by infinite words), the answer to this question is decidable.

Details DOI

TCS Journal 2017 Journal Article

Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds

Florent Foucaud
George B. Mertzios
Reza Naserasr
Aline Parreau
Petru Valicov

We consider the problems of finding optimal identifying codes, (open) locating–dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to find a subset of vertices, normally called a solution set, using which all vertices of the graph are distinguished. The identification can be done by considering the neighborhood within the solution set, or by employing the distances to the solution vertices. Normally the goal is to minimize the size of the solution set then. Here we study the case of interval graphs, unit interval graphs, (bipartite) permutation graphs and cographs. For these classes of graphs we give tight lower bounds for the size of such solution sets depending on the order of the input graph. While such lower bounds for the general class of graphs are in logarithmic order, the improved bounds in these special classes are of the order of either quadratic root or linear in terms of number of vertices. Moreover, the results for cographs lead to linear-time algorithms to solve the considered problems on inputs that are cographs.

Details DOI