Accordingly to Duchet (1987), the first paper of convexity on general graphs, in english, is the 1981 paper “Convexity in graphs”. One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which were investigated in a sequence of five papers that ended in 2003. In this paper, we continue this research line, extend these games to other graph convexities, and obtain winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries in graphs. We also obtain the first PSPACE-hardness results on convexity games, by proving that the normal play and the misère play of the hull game on the geodesic and the monophonic convexities are PSPACE-complete.

The Gangal-Ranade algorithm presents the best approximation ratio for the classic scheduling problem with unit execution time and precedence constrained jobs, on a variable number of identical parallel machines, to minimize the makespan. This work presents results about the optimality of the algorithm when the acyclic directed graph (DAG) that represents the precedence constraints are arborescences (directed trees, in-tree and out-tree), reinforcing that these types of DAGs provide optimal substructures for the problem. Understanding the behavior of this algorithm for classes of arborescences can lead to optimality or better approximations for classes of larger DAGs, which is our ongoing research work. Furthermore, the search for optimal cases for algorithms such as Gangal-Ranade can provide intuition to obtain partial answers to problems that remain open, such as the famous Open 8 in the list presented in the classical Garey and Johnson book.