Search

Your search keyword '"scoring game"' showing total 15 results
Start Over Descriptor "scoring game"
15 results on '"scoring game"'

1. The Complexity of Two Colouring Games.

Author

Andres, Stephan Dominique, Dross, François, Huggan, Melissa A., Mc Inerney, Fionn, and Nowakowski, Richard J.

Subjects
*POINT set theory, *GAMES
Abstract

We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the normal play variant, the first player unable to move loses. In the scoring variant, each player aims to maximise their score, which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with partial colourings, both the normal play and the scoring variant of the game are PSPACE-complete. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and v σ (v) ∈ E (G) for any non-fixed point v ∈ V (G) . Andres et al. (Theor Comput Sci 795:312–325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

2. Incidence, a scoring positional game on graphs.

Author

Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, and Parreau, Aline

Subjects
*HYPERGRAPHS, *POLYNOMIAL time algorithms, *UNDIRECTED graphs, *GAMES, *TEST scoring
Abstract

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence , a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE -complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

3. On a vertex-capturing game.

Author

Bensmail, Julien and Mc Inerney, Fionn

Subjects
*BIPARTITE graphs, *TREE graphs, *GAMES, *COMPLETE graphs, *PATHS & cycles in graph theory
Abstract

In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins. Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

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

Author

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

Subjects
*GAMES, *GENERALIZATION
Abstract

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. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

5. Incidence, a scoring positional game on graphs

Author

Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, Parreau, Aline, Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, and Parreau, Aline

Abstract

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on INCIDENCE, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of INCIDENCE is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.

Published
2023
Full Text
View/download PDF

6. Bipartite instances of INFLUENCE.

Author

Duchêne, Eric, Oijid, Nacim, and Parreau, Aline

Subjects
*BIPARTITE graphs, *COMPUTATIONAL complexity, *HYPERCUBES
Abstract

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. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

7. The orthogonal colouring game.

Author

Andres, Stephan Dominique, Huggan, Melissa, Mc Inerney, Fionn, and Nowakowski, Richard J.

Subjects
*MAGIC squares, *POINT set theory, *NONCOOPERATIVE games (Mathematics), *GAMES
Abstract

We introduce the orthogonal colouring game , in which two players alternately colour vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximise her score , which is the number of coloured vertices in the copy of the graph she owns. The main result of this paper is that the second player has a strategy to force a draw in this game for any m ∈ N for graphs that admit a strictly matched involution. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and any non-fixed point v ∈ V (G) is connected with its image σ (v) by an edge. We give a structural characterisation of graphs admitting a strictly matched involution and bounds for the number of such graphs. Examples of such graphs are the graphs associated with Latin squares and sudoku squares. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

8. On a vertex-capturing game

Author

Julien Bensmail, Fionn Mc Inerney, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and Helmholtz Center for Information Security [Saarbrücken] (CISPA)

Subjects
combinatorial game, Computer Science::Computer Science and Game Theory, General Computer Science, ComputingMilieux_PERSONALCOMPUTING, Quantum Physics, 2-player game, graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], scoring game, MathematicsofComputing_DISCRETEMATHEMATICS, Computer Science::Cryptography and Security, Theoretical Computer Science
Abstract

International audience; In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins.Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs.

Published
2022
Full Text
View/download PDF

9. Corrigendum to "The orthogonal colouring game" [Theor. Comput. Sci. 795 (2019) 312–325].

Author

Andres, Stephan Dominique, Huggan, Melissa, Mc Inerney, Fionn, and Nowakowski, Richard J.

Subjects
*GAMES, *MAGIC squares, *ISOMORPHISM (Mathematics)
Abstract

The lower bound for the number of isomorphism classes of graphs admitting a strictly matched involution given in Theorem 15 of our paper on the orthogonal colouring game [1] is incorrect. Here, we prove a weaker lower bound. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

10. Smash and Grab: the 0.6 Scoring Game on Graphs

Author

Duchêne, Éric, Gledel, Valentin, Gravier, Sylvain, Mc Inerney, Fionn, Mhalla, Mehdi, Parreau, Aline, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Graphes, AlgOrithmes et AppLications (GOAL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Helmholtz Center for Information Security [Saarbrücken] (CISPA), Laboratoire d'Informatique de Grenoble (LIG), and Mc Inerney, Fionn

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Scoring game, Games on graphs, Combinatorial game theory, ComputingMilieux_PERSONALCOMPUTING, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], PSPACE-complete
Abstract

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 $Ls(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 $Ls(F) ≥ 0$ for any forest $F$ (i.e., the first player cannot lose). We then use this result to compute the exact value of $Ls(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.

Published
2021

11. The orthogonal colouring game

Author

Stephan Dominique Andres, Fionn Mc Inerney, Melissa A. Huggan, Richard J. Nowakowski, FernUniversität in Hagen, Dalhousie University [Halifax], Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Computer Science::Computer Science and Game Theory, mutually orthogonal Latin squares, General Computer Science, games on graphs, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Fixed point, scoring game, 01 natural sciences, 2008 MSC, 05C57, 05C15, 05B15, 91A46, 91A4, Graph, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, strictly matched involution, Orthogonal Colouring Game, [INFO]Computer Science [cs], 0101 mathematics, Graph isomorphism, orthogonal graph colouring, Mathematics
Abstract

International audience; We introduce the Orthogonal Colouring Game, in which two players alternately colour vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximise her score, which is the number of coloured vertices in the copy of the graph she owns. The main result of this paper is that the second player has a strategy to force a draw in this game for any m ∈ N for graphs that admit a strictly matched involution. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and any non-fixed point v ∈ V (G) is connected with its image σ(v) by an edge. We give a structural characterisation of graphs admitting a strictly matched involution and bounds for the number of such graphs. Examples of such graphs are the graphs associated with Latin squares and sudoku squares.

Published
2019
Full Text
View/download PDF

12. The Complexity of two Colouring Games

Author

Andres, Stephan Dominique, Dross, François, Huggan, Melissa, Mc Inerney, Fionn, Nowakowski, Richard, University of Greifswald, Université de Bordeaux (UB), Department of Mathematics and Computer Science [Mount Allison University], Mount Allison University, Helmholtz Center for Information Security [Saarbrücken] (CISPA), Dalhousie University [Halifax], and CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Subjects
combinatorial game, Computer Science::Computer Science and Game Theory, orthogonal colouring game, strictly matched involution, 2008 MSC: 68Q17, 05C57, 05C15, 91A46, 68R10, 91A43, [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], orthogonal graph colouring, scoring game, PSPACE-complete, NP-complete
Abstract

We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of $m\in \mathbb{N}$ colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the normal play variant, the first player unable to move loses. In the scoring variant, each player aims to maximise their score, which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with a partial colouring, both the normal play and the scoring variant of the game are PSPACE-complete. An involution $\sigma$ of a graph G is strictly matched if its fixed point set induces a clique and $v\sigma(v)\in E(G)$ for any non-fixed point $v\in V(G)$. Andres, Huggan, Mc Inerney, and Nowakowski (The orthogonal colouring game. Theor. Comput. Sci., 795:312-325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete.

Published
2021

13. The Vertex-Capturing Game

Author

Bensmail, Julien, Mc Inerney, Fionn, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Helmholtz Center for Information Security [Saarbrücken] (CISPA), Université Côte d'Azur, and CISPA Helmholtz Center for Information Security

Subjects
combinatorial game, Computer Science::Computer Science and Game Theory, ComputingMilieux_PERSONALCOMPUTING, 2-player game, graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], scoring game, MathematicsofComputing_DISCRETEMATHEMATICS, Computer Science::Cryptography and Security
Abstract

Inspired by the board game Kahuna, we introduce and study a new 2-player scoring game played on graphs called the vertex-capturing game. The game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins. Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs.

Published
2021

14. On the Complexity of Orthogonal Colouring Games and the NP-Completeness of Recognising Graphs Admitting a Strictly Matched Involution

Author

Andres, Stephan Dominique, Dross, François, Huggan, Melissa, Mc Inerney, Fionn, Nowakowski, Richard, FernUniversität in Hagen, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Dalhousie University [Halifax], and Inria - Sophia Antipolis

Subjects
combinatorial game, Computer Science::Computer Science and Game Theory, strictly matched involution, 2008 MSC: 68Q17, 05C57, 05C15, 91A46, 68R10, 91A43, Orthogonal Colouring Game, [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], orthogonal graph colouring, scoring game, NP-completeness, PSPACE-completeness
Abstract

We consider two variants of orthogonal colouring games on graphs. In these games, two players alternate colouring vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. In the normal play variant, the player who is unable to move loses. In the scoring variant, each player aims to maximize her score which is the number of coloured vertices in the copy of the graph she owns. It is proven that, given an instance with a partial colouring, both the normal play and the scoring variant of the game are PSPACE-complete. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and vσ(v) is an edge for any non-fixed point v ∈ V (G). Andres, Huggan, Mc Inerney, and Nowakowski (The orthogonal colouring game. Submitted) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete.

Published
2019

15. Two-Player Tower of Hanoi

Author

Urban Larsson, Akihiro Matsuura, Jonathan Chappelon, Institut Montpelliérain Alexander Grothendieck (IMAG), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Statistics [Canada], Dalhousie University [Halifax], School of Science and Engineering [TDU], and Tokyo Denki University

Subjects
Statistics and Probability, FOS: Computer and information sciences, Economics and Econometrics, Discrete Mathematics (cs.DM), Combinatorial game theory, MSC2010 : 91A05, 91A46, 68R99, 0102 computer and information sciences, Characterization (mathematics), Type (model theory), winning strategy, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, scoring game, normal play, Two-player game, Mathematics (miscellaneous), Computer Science - Computer Science and Game Theory, 0101 mathematics, [MATH]Mathematics [math], Real number, Mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 010102 general mathematics, ComputingMilieux_PERSONALCOMPUTING, Tower (mathematics), Recreational mathematics, Tower of Hanoi, weighed Tower of Hanoi, 010201 computation theory & mathematics, Statistics, Probability and Uncertainty, Mathematical economics, Algorithm, Social Sciences (miscellaneous), Computer Science - Discrete Mathematics, Computer Science and Game Theory (cs.GT)
Abstract

The Tower of Hanoi game is a classical puzzle in recreational mathematics (Lucas 1883) which also has a strong record in pure mathematics. In a borderland between these two areas we find the characterization of the minimal number of moves, which is $2^n-1$, to transfer a tower of $n$ disks. But there are also other variations to the game, involving for example real number weights on the moves of the disks. This gives rise to a similar type of problem, but where the final score seeks to be optimized. We study extensions of the one-player setting to two players, invoking classical winning conditions in combinatorial game theory such as the player who moves last wins, or the highest score wins. Here we solve both these winning conditions on three heaps., Comment: 16 pages, 6 figures, 1 table

Published
2018
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results