Undirected Vertex Geography (UVG) is an impartial two-person game played on a (undirected) graph G with a specified vertex u. Players, Alice and Bob, alternately choose a vertex that has not been chosen before and that is adjacent to the last chosen vertex. Alice plays first, choosing an adjacent vertex of u. The first player who is unable to choose a vertex loses. Determining whether Alice has a winning strategy in this game (the UVG problem) is known to be solvable in polynomial time. In this paper we study the complexity of the short version of this game (the short-UVG problem) in which it is asked whether Alice has a winning strategy that requires at most k moves, with k part of the input. We show that the short-UVG problem is PSPACE-complete even for bipartite graphs whereas a polynomial algorithm can be designed for trees. Finally, we introduce a partizan version of theUVG-game which we believe is of independent interest. We provide some preliminary results and conclude with many open problems.

On variants of Vertex Geography on undirected graphs / Monti, A.; Sinaimeri, B.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 251:(2018), pp. 268-275. [10.1016/j.dam.2018.05.044]

On variants of Vertex Geography on undirected graphs

Sinaimeri B.
2018

Abstract

Undirected Vertex Geography (UVG) is an impartial two-person game played on a (undirected) graph G with a specified vertex u. Players, Alice and Bob, alternately choose a vertex that has not been chosen before and that is adjacent to the last chosen vertex. Alice plays first, choosing an adjacent vertex of u. The first player who is unable to choose a vertex loses. Determining whether Alice has a winning strategy in this game (the UVG problem) is known to be solvable in polynomial time. In this paper we study the complexity of the short version of this game (the short-UVG problem) in which it is asked whether Alice has a winning strategy that requires at most k moves, with k part of the input. We show that the short-UVG problem is PSPACE-complete even for bipartite graphs whereas a polynomial algorithm can be designed for trees. Finally, we introduce a partizan version of theUVG-game which we believe is of independent interest. We provide some preliminary results and conclude with many open problems.
Algorithmic combinatorial game theory; Computational complexity; Short winning strategy problems; Undirected vertex geography
On variants of Vertex Geography on undirected graphs / Monti, A.; Sinaimeri, B.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 251:(2018), pp. 268-275. [10.1016/j.dam.2018.05.044]
File in questo prodotto:
File Dimensione Formato  
short-UVG_disc_app_math.pdf

Solo gestori archivio

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 237.09 kB
Formato Adobe PDF
237.09 kB Adobe PDF   Visualizza/Apri
1-s2.0-S0166218X18303056-main.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 312.76 kB
Formato Adobe PDF
312.76 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/202501
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact