Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915630121222144 |
|---|---|
| author | Burke, Kyle Dailly, Antoine Oijid, Nacim |
| author_facet | Burke, Kyle Dailly, Antoine Oijid, Nacim |
| contents | Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left, the winner being the player who played the last move. Introduced in 1978, its computational complexity is still open. More recently, subtraction games, where the players cannot disconnect the graph while removing vertices, were introduced. In particular, Arc-Kayles admits a non-disconnecting variant that is a subtraction game. We study the computational complexity of subtraction games on graphs, proving that they are PSPACE-complete even on very structured graph classes (split, bipartite of any even girth). We give a quadratic kernel for Non-Disconnecting Arc-Kayles when parameterized by the feedback edge number, as well as polynomial-time algorithms for clique trees and a subclass of threshold graphs. We also show that a sufficient condition for a second player-win on Arc-Kayles is equivalent to the graph isomorphism problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10390 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles Burke, Kyle Dailly, Antoine Oijid, Nacim Combinatorics Discrete Mathematics Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left, the winner being the player who played the last move. Introduced in 1978, its computational complexity is still open. More recently, subtraction games, where the players cannot disconnect the graph while removing vertices, were introduced. In particular, Arc-Kayles admits a non-disconnecting variant that is a subtraction game. We study the computational complexity of subtraction games on graphs, proving that they are PSPACE-complete even on very structured graph classes (split, bipartite of any even girth). We give a quadratic kernel for Non-Disconnecting Arc-Kayles when parameterized by the feedback edge number, as well as polynomial-time algorithms for clique trees and a subclass of threshold graphs. We also show that a sufficient condition for a second player-win on Arc-Kayles is equivalent to the graph isomorphism problem. |
| title | Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2404.10390 |