On variants of Vertex Geography on undirected graphs

Autor: Blerina Sinaimeri, Angelo Monti
Přispěvatelé: Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA)
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Vertex (graph theory)
Computer Science::Computer Science and Game Theory
Computational complexity theory
Algorithmic combinatorial game theory
Short winning strategy problems
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Polynomial algorithm
Combinatorics
Undirected vertex geography
Alice and Bob
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
0202 electrical engineering
electronic engineering
information engineering
Discrete Mathematics and Combinatorics
[INFO]Computer Science [cs]
Undirected graph
Time complexity
Mathematics
Computational complexity
Applied Mathematics
16. Peace & justice
Graph
010201 computation theory & mathematics
Bipartite graph
020201 artificial intelligence & image processing
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2018, 251, pp.268-275. ⟨10.1016/j.dam.2018.05.044⟩
Discrete Applied Mathematics, 2018, 251, pp.268-275. ⟨10.1016/j.dam.2018.05.044⟩
ISSN: 0166-218X
DOI: 10.1016/j.dam.2018.05.044⟩
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: