On variants of Vertex Geography on undirected graphs

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 the UVG-game which we believe is of independent interest. We provide some preliminary results and conclude with many open problems.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2018, 251, pp.268-275. 〈10.1016/j.dam.2018.05.044〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01965197
Contributeur : Marie-France Sagot <>
Soumis le : mardi 25 décembre 2018 - 08:47:32
Dernière modification le : jeudi 7 février 2019 - 14:52:38

Identifiants

Collections

Citation

Angelo Monti, Blerina Sinaimeri. On variants of Vertex Geography on undirected graphs. Discrete Applied Mathematics, Elsevier, 2018, 251, pp.268-275. 〈10.1016/j.dam.2018.05.044〉. 〈hal-01965197〉

Partager

Métriques

Consultations de la notice

28