2026-09-24T17:33:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25723 2026-09-23T23:48:33Z ddc:004 open_access

The Closed Hull Game and the Closed Interval Game Araújo, Samuel N. Benevides, Fabrício Martins, Nicolas Nisse, Nicolas Sampaio, Rudini Combinatorial games in graphs graph convexity PSPACE Given a set S of vertices in a graph G, its geodesic interval is the set I(S) containing S and all vertices on a shortest path between vertices of S. A set S is convex if I(S) = S. Moreover, the convex hull ℋ(S) of S is the smallest convex set containing S. In 1984, Harary introduced convexity games where two players, Alice and Bob, alternately select vertices of a graph G = (V,E) such that, if the set of already selected vertices is S, the next player can only select a vertex in V ⧵ I(S) (closed interval game) or in V ⧵ ℋ(S) (closed hull game). Normal and misère versions of these games have been studied and here, we introduced the optimization variants of them. Formally, given a graph G and k ∈ ℕ, Alice wins if the game ends after at most k vertices have been selected and Bob wins otherwise. The corresponding problem consists of determining which player has a winning strategy. We prove that the closed interval optimization game is PSPACE-complete in graphs with diameter 4 and that the closed hull optimization game is NP-hard in bipartite graphs and in split graphs. On the positive side, we prove that both games can be solved in polynomial time in trees and that the closed hull optimization game can be solved in polynomial time in cobipartite graphs. We conjecture that the closed interval optimization game is NP-hard in cobipartite graphs and that the closed hull optimization game is PSPACE-complete in general graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samuel N. Araújo and Fabrício Benevides and Nicolas Martins and Nicolas Nisse and Rudini Sampaio 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.4 urn:nbn:de:0030-drops-257232 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode