Jogos de Convexidade em Grafos Direcionados
Resumo
Em 2023, Araújo et al. introduziram os conceitos de jogo de envoltória e jogo fechado de envoltória em grafos não direcionados, abordando várias convexidades de grafos, como geodésica e P3. Eles mostraram que decidir o vencedor desses jogos na convexidade geodésica é polinomial em árvores, mas é PSPACE-completo em grafos gerais. Com a existência de convexidades em grafos direcionados, surge a questão: a complexidade do problema é afetada pelas orientações das arestas? Neste artigo, introduzimos e investigamos jogos de convexidade em grafos direcionados, estabelecendo que determinar o jogador com uma estratégia vencedora é PSPACE-completo tanto para o jogo de envoltória quanto para o jogo fechado de envoltória na convexidade P3.
Referências
Araújo, S. N., Folz, R., de Freitas, R., and Sampaio, R. (2023). Complexity and winning strategies of graph convexity games (brief announcement). Procedia Computer Science, 223:394–396.
Arora, S. and Barak, B. (2009). Computational complexity. Cambridge University Press, Cambridge, England.
Barbosa, R. M., Coelho, E. M., Dourado, M. C., Rautenbach, D., and Szwarcfiter, J. L. (2012). On the Carathéodory number for the convexity of paths of order three. SIAM Journal on Discrete Mathematics, 26(3):929–939.
Buckley, F. and Harary, F. (1985a). Closed geodetic games for graphs. Congressus Numerantium, 47:131–138. Proceedings of the 16th Southeastern Conference on Combinatorics, Graph Theory and Computing.
Buckley, F. and Harary, F. (1985b). Geodetic games for graphs. Quaestiones Mathematicae, 8:321–334.
Dourado, M. C., Protti, F., and Szwarcfiter, J. L. (2010). Complexity results related to monophonic convexity. Discrete Applied Mathematics, 158(12):1268–1274.
Duchet, P. (1988). Convex sets in graphs, II. Minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307–316.
Erdős, P., Fried, E., Hajnal, A., and Milner, E. (1972). Some remarks on simple tournaments. Algebra universalis, 2:238–245.
Everett, M. G. and Seidman, S. B. (1985). The hull number of a graph. Discrete Mathematics, 57(3):217–223.
Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, 7(3):433–444.
Farber, M. and Jamison, R. E. (1987). On local convexity in graphs. Discrete Mathematics, 66(3):231–247.
Harary, F. (1984). Convexity in graphs: Achievement and avoidance games. In Annals of Discrete Mathematics (20), volume 87, page 323. North-Holland.
Haynes, T., Henning, M., and Tiller, C. (2003). Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae, 26:389–397.
Hearn, R. and Demaine, E. (2009). Games, Puzzles and Computation. A. K. Peters Ltd.
Nečásková, M. (1988). A note on the achievement geodetic games. Quaestiones Mathematicae, 12:115–119.
Schaefer, T. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225.
Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. 5th Int. Congress of Mathematicians, pages 501–504.
Arora, S. and Barak, B. (2009). Computational complexity. Cambridge University Press, Cambridge, England.
Barbosa, R. M., Coelho, E. M., Dourado, M. C., Rautenbach, D., and Szwarcfiter, J. L. (2012). On the Carathéodory number for the convexity of paths of order three. SIAM Journal on Discrete Mathematics, 26(3):929–939.
Buckley, F. and Harary, F. (1985a). Closed geodetic games for graphs. Congressus Numerantium, 47:131–138. Proceedings of the 16th Southeastern Conference on Combinatorics, Graph Theory and Computing.
Buckley, F. and Harary, F. (1985b). Geodetic games for graphs. Quaestiones Mathematicae, 8:321–334.
Dourado, M. C., Protti, F., and Szwarcfiter, J. L. (2010). Complexity results related to monophonic convexity. Discrete Applied Mathematics, 158(12):1268–1274.
Duchet, P. (1988). Convex sets in graphs, II. Minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307–316.
Erdős, P., Fried, E., Hajnal, A., and Milner, E. (1972). Some remarks on simple tournaments. Algebra universalis, 2:238–245.
Everett, M. G. and Seidman, S. B. (1985). The hull number of a graph. Discrete Mathematics, 57(3):217–223.
Farber, M. and Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, 7(3):433–444.
Farber, M. and Jamison, R. E. (1987). On local convexity in graphs. Discrete Mathematics, 66(3):231–247.
Harary, F. (1984). Convexity in graphs: Achievement and avoidance games. In Annals of Discrete Mathematics (20), volume 87, page 323. North-Holland.
Haynes, T., Henning, M., and Tiller, C. (2003). Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae, 26:389–397.
Hearn, R. and Demaine, E. (2009). Games, Puzzles and Computation. A. K. Peters Ltd.
Nečásková, M. (1988). A note on the achievement geodetic games. Quaestiones Mathematicae, 12:115–119.
Schaefer, T. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225.
Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. 5th Int. Congress of Mathematicians, pages 501–504.
Publicado
21/07/2024
Como Citar
ARAÚJO, Samuel Nascimento de; BRITO, João Marcos; SAMPAIO, Rudini Menezes.
Jogos de Convexidade em Grafos Direcionados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 1-5.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2023.
