11 papers
The disjoint separators problem in graphs
Thomas Delépine, Florian Galliot, Yannick Mogge +2
We study the disjoint separators problem in graphs, an analogue of the famous disjoint paths problem. Given a graph and four pairwise disjoint subsets of vertices , ,…
A two-player version of the assignment problem
Florian Galliot, Nacim Oijid, Jonas Sénizergues
We introduce the competitive assignment problem, a two-player version of the well-known assignment problem. Given a set of tasks and a set of agents with different efficiencies for…
Token positional games
Guillaume Bagan, Quentin Deschamps, Florian Galliot +2
The classical Maker-Breaker positional game is played on a board which is a hypergraph , with two players, Maker and Breaker, alternately claiming vertices of $\mathca…
4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
Florian Galliot
We study two positional games played on hypergraphs, whose edges may be interpreted as winning sets. Two players take turns picking a previously unpicked vertex of the hypergraph.…
Maker-Maker games of rank 4 are PSPACE-complete
Florian Galliot, Jonas Sénizergues
The Maker-Maker convention of positional games is played on a hypergraph whose edges are interpreted as winning sets. Two players take turns picking a previously unpicked vertex, a…
The Avoider-Enforcer game on hypergraphs of rank 3
Florian Galliot, Valentin Gledel, Aline Parreau
In the Avoider-Enforcer convention of positional games, two players, Avoider and Enforcer, take turns selecting vertices from a hypergraph H. Enforcer wins if, by the time all vert…
A unified convention for achievement positional games
Florian Galliot, Jonas Sénizergues
We introduce achievement positional games, a convention for positional games which encompasses the Maker-Maker and Maker-Breaker conventions. We consider two hypergraphs, one red a…
Poset Positional Games
Guillaume Bagan, Eric Duchêne, Florian Galliot +5
We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset…
An update on the coin-moving game on the square grid
Florian Galliot, Sylvain Gravier, Isabelle Sivignon
This paper extends the work started in 2002 by Demaine, Demaine and Verill (DDV) on coin-moving puzzles. These puzzles have a long history in the recreational literature, but were…
(k-2)-linear connected components in hypergraphs of rank k
Florian Galliot, Sylvain Gravier, Isabelle Sivignon
We define a -linear path in a hypergraph as a sequence of edges of such that and if $|…
Maker-Breaker is solved in polynomial time on hypergraphs of rank 3
Florian Galliot, Sylvain Gravier, Isabelle Sivignon
In the Maker-Breaker positional game, Maker and Breaker take turns picking vertices of a hypergraph , and Maker wins if and only if she possesses all the vertices of some edge o…