Convexity Games in Directed Graphs

• Samuel Nascimento de Araújo UFC / IFCE
• João Marcos Brito UFC
• Rudini Menezes Sampaio UFC

DOI: https://doi.org/10.5753/etc.2024.2023

Abstract

In 2023, Araújo et al. introduced hull game and closed hull game concepts on undirected graphs for various graph convexities, such as geodesic convexity and P₃ convexity. They demonstrated that determining the winner of these games in geodesic convexity is polynomial-time solvable in trees but is PSPACE-hard in general graphs. With the existence of convexity on directed graphs, a pertinent question arises: does the problem’s complexity change with the introduction of edge orientations? In this paper, we introduce and explore convexity games on directed graphs. We establish that determining the player with a winning strategy is PSPACE-complete for both hull game and closed hull game in P₃-convexity.

References

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.