# The Closed Hull Game and the Closed Interval Game

Samuel N Araújo, Fabrício Benevides, Nicolas Martins, Nicolas Nisse, Rudini Sampaio

► To cite this version:

Samuel N Araújo, Fabrício Benevides, Nicolas Martins, Nicolas Nisse, Rudini Sampaio. The Closed Hull Game and the Closed Interval Game. Inria & Université Cote d'Azur, Sophia Antipolis, France. 2025. [hal-05376270](https://hal-05376270)

HAL Id: hal-05376270

https://inria.hal.science/hal-05376270v1

Submitted on 21 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Closed Hull Game and the Closed Interval Game

Samuel N. Araújo<sup>1,2,3</sup>, Fabrício Benevides<sup>2</sup>, Nicolas Martins<sup>4</sup>, Nicolas Nisse<sup>1</sup>, and Rudini Sampaio<sup>2</sup>

<sup>1</sup>Université Côte d'Azur, Inria, CNRS, I3S, France.

<sup>2</sup>PARGO Research Group, Universidade Federal do Ceará, Brazil.

<sup>3</sup>Inst. Fed. Educação, Ciência e Tecnologia do Ceará, IFCE, Crato, Brazil

<sup>4</sup>Inst. de Eng. e Desenvolvimento Sustentável, UNILAB, Brazil.

## Abstract

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 $\mathcal{H}(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 \setminus I(S)$ (closed interval game) or in $V \setminus \mathcal{H}(S)$ (closed hull game). Normal and misère version of these games have been studied and here, we introduced the optimization variants of them. Formally, given a graph $G$ and $k \in N$, 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.

# 1 Introduction

Convexity has long been a topic of significant interest in mathematics. Its application to graph theory, however, is relatively recent, dating back to approximately 50 years ago. One of the earliest contributions in this direction
is the 1972 paper by Erdős et al. [21], which studied convexity in the context of tournaments. According to Duchet [20], the first English-language publication on convexity in graphs was the 1981 paper “Convexity in Graphs” by Harary and Nieminen [24].

The main investigated convexity is the geodesic convexity. Let $G$ be a graph and $S \subseteq V(G)$ a subset of vertices of $G$. The interval $I(S)$ of $S$ is the set $S$ together with every vertex outside $S$ that belongs to a shortest path between two vertices of $S$. We say that $S$ is convex if $I(S) = S$. The convex hull, $\mathcal{H}(S)$, of $S$ is the minimum convex set that contains $S$. We say that $S$ is an interval set if $I(S) = V(G)$ and that $S$ is a hull set if $\mathcal{H}(S) = V(G)$. Typical questions are to compute a smallest hull set [22] or a smallest interval set [25] or a largest proper convex set [14] of a given graph.

In 1984, Frank Harary introduced the first graph convexity games in his abstract “Convexity in Graphs: Achievement and Avoidance Games” [23]. This line of research on graph convexity games continued until 2003, with the articles [11, 12, 26, 27] investigating Harary’s games in simple graph classes. Such games are two-player (Alice and Bob) impartial combinatorial games. The decision problem associated with them is to determine if Alice has a winning strategy.

Among Harary’s 1984 games, the following stand out: the CLOSED HULL GAME (CHG) and the CLOSED INTERVAL GAME (CIG). In both, it is given a graph $G$ and, during the game, some vertices are selected by the players (forming the set $S$ of selected vertices) and other vertices are considered covered (according to specific rules of the game). Every selected vertex is a covered vertex, but not every covered vertex is a selected vertex. Alice and Bob play by alternately selecting uncovered vertices. In the game CHG, a vertex $v$ is covered if $v \in \mathcal{H}(S)$. In the game CIG, a vertex $v$ is covered if $v \in I(S)$. Each game ends when all vertices are covered. That is, CHG ends when $S$ is a hull set and CIG ends when $S$ is an interval set. In the normal (resp. misère) variant, the last person to select a vertex wins (resp. loses).

In 2024, Araújo et al. [3] revived the research on graph convexity games by using the Sprague-Grundy Theory to obtain a polynomial time algorithm for the games CHG-normal and CIG-normal in trees. They also proved that the games CHG-normal and CHG-misère are PSPACE-complete. Other results on similar topics have been obtained in [5, 16]. The PSPACE-hardness of CIG-normal and CIG-misère are still open problems. For the investigation of partizan convexity games, we refer the reader to [4].

Another variant that has been extensively researched in the literature of games on graphs, in addition to the normal and misère variants, is the optimization variant. Here, roughly speaking, Alice wants to minimize some parameter of the game while Bob wants to maximize the same parameter or vice-versa. As an example, the game KAYLES [6, 7] of obtaining an independent set of a graph was proved PSPACE-hard in the normal variant
[28] in 1978, in the misère variant [13] in 2024 and in the optimization variant in [10] in 2025. Also the DOMINATION GAME of obtaining a dominating set was proved PSPACE-hard in the optimization variant [8] in 2016 and in the normal and misère variants [9] in 2025.

In this paper, we focus on the optimization variant of CHG and CIG, denoted by CHG-opt and CIG-opt, in which it is also given an integer $k$ and Alice wins if the size of the set $S$ of selected vertices is at most $k$, no matter who plays last. We often think of the total number of selected vertices as the *time* (or duration) of the game, measured in the total number of *turns* that have been played.

We prove that CHG-opt and CIG-opt are polynomial time solvable in trees and that CHG-opt is polynomial time solvable in cobipartite graphs. We also prove that CIG-opt is PSPACE-complete in graphs with diameter 4 and that CHG-opt is NP-hard in bipartite graphs and in split graphs. Unfortunately, we were unable to prove the PSPACE-hardness of CHG-opt, which is still an open problem.

For simplicity, in the remainder of this paper, CIG and CHG refer to the optimization variants, CIG-opt and CHG-opt.

## 2 Preliminaries

Given a graph $G$, an integer $k$ and $C \subseteq V(G)$, let the closed game hull number $cghn(G, C)$ (resp., $cghn^B(G, C)$) be the smallest integer $k$ such that Alice wins CHG on $G$ and at most $k$ vertices are selected during the game, assuming that the vertices in $C$ were already selected prior to the beginning of the game (i.e., $|C|$ does not count in the number of selected vertices during the game), when Alice (resp. Bob) starts. We define the closed game interval numbers $cgin(G, C)$ and $cgin^B(G, C)$ analogously to the game CIG. Let $cghn(G) = cghn(G, \emptyset)$ and $cgin(G) = cgin(G, \emptyset)$. The parameters closed game hull number $cghn(G)$ and closed game interval number $cgin(G)$ were introduced in [3].

In both games, a *strategy* for a player on a graph $G = (V, E)$ is a function $f: 2^V \to V$ such that $f(S)$ is the vertex to be selected by the player when the set of (currently) selected vertices is $S$. A *k-strategy* for Alice (resp. Bob) is a strategy that ensures that the end of the game takes at most (resp. more than) $k$ steps regardless of how Bob (resp. Alice) plays. A strategy for Alice (resp. Bob) in a graph $G$ is *optimal* if it is a *k-strategy* with minimum (resp. maximum) $k$.

The next lemma presents some properties of the game CHG. In its proof, we need to define strategies that are built from a given strategy but “ignore a certain set $X$”. Given a CHG strategy $f_A$ of Alice in a graph $G = (V, E)$, a convex set $S$ and a convex set $S \cup X$, we say that Alice plays $f_A$ ignoring $X$ when $S \cup X$ is the set of covered vertices if she selects $v = f_A(S)$ in her
next turn in the case that $v \notin X$, otherwise she selects an arbitrary vertex $v \notin S \cup X$. Moreover, if $w \in V \setminus \mathcal{H}(S \cup X \cup \{v\})$ is the vertex selected by Bob after Alice has selected $v$, then Alice continues by playing $f_A$ ignoring $\mathcal{H}(S \cup X \cup \{v, w\}) \setminus \mathcal{H}(S \cup \{v, w\})$.

Note that the set of covered vertices when Alice follows $f_A$ ignoring $X$ starting from $S \cup X$ is always a superset of the covered vertices when Alice follows $f_A$ starting from $S$. Hence, the maximum number of turns used by Alice when playing $f_A$ ignoring $X$ starting from $S \cup X$ is not greater than the maximum number of turns used by Alice when playing $f_A$ starting from $S$, whatever Bob does.

**Lemma 1.** Let $G = (V, E)$ be a graph and $C \subseteq C' \subseteq V$ where $C$ and $C'$ are convex sets. Then,

(a) $\mathrm{cghn}(G, C') \le \mathrm{cghn}(G, C)$ and $\mathrm{cghn}^B(G, C') \le \mathrm{cghn}^B(G, C)$,

(b) $\mathrm{cghn}(G, C) - 1 \le \mathrm{cghn}^B(G, C) \le \mathrm{cghn}(G, C) + 1$ and both bounds are tight.

*Proof.* Given that $C$ and $C'$ are both convex sets, consider the scenario in which Alice executes her strategy ignoring the vertices in $C' \setminus C$. In this case, the set of vertices covered by Alice's strategy will either remain the same or form a superset of the set of vertices covered when the strategy is executed starting from $C$. Consequently, the maximum number of turns required to cover the vertices starting from $C'$ ignoring $C' \setminus C$, is no greater than the maximum number of turns required when starting from $C$. Since this is valid for when Alice starts or when Bob starts, we conclude that $\mathrm{cghn}(G, C') \le \mathrm{cghn}(G, C)$ and $\mathrm{cghn}^B(G, C') \le \mathrm{cghn}^B(G, C)$.

To show that $\mathrm{cghn}(G, C) \le \mathrm{cghn}^B(G, C) + 1$, it suffices to show a strategy for Alice where she starts and the game finishes in at most $\mathrm{cghn}^B(G, C) + 1$ turns. Suppose Alice chooses any $v \in V(G) \setminus C$. After her move, the new convex set becomes $\mathcal{H}(C \cup \{v\})$, and by the Property (a), $\mathrm{cghn}^B(G, \mathcal{H}(C \cup \{v\})) \le \mathrm{cghn}^B(G, C)$. Thus, starting with the convex set $C$, Alice's strategy requires at most one turn for her to choose any vertex and $\mathrm{cghn}^B(G, \mathcal{H}(C \cup \{v\}))$ turns thereafter. Since $\mathrm{cghn}^B(G, \mathcal{H}(C \cup \{v\})) \le \mathrm{cghn}^B(G, C)$, we conclude that

$$ \mathrm{cghn}(G, C) \le \mathrm{cghn}^B(G, \mathcal{H}(C \cup \{v\})) + 1 \le \mathrm{cghn}^B(G, C) + 1. $$

Similarly, to show that $\mathrm{cghn}^B(G, C) \le \mathrm{cghn}(G, C) + 1$, it suffices to provide a strategy for Alice where Bob starts and the game finishes in at most $\mathrm{cghn}(G, C) + 1$ turns. Analogously, suppose Bob chooses any $v \in V(G) \setminus C$. After his move, the new convex set is $\mathcal{H}(C \cup \{v\})$, and by the Property (a), $\mathrm{cghn}(G, \mathcal{H}(C \cup \{v\})) \le \mathrm{cghn}(G, C)$. Thus, starting with the convex set $C$, Bob's strategy requires at most one turn for his move and $\mathrm{cghn}(G, \mathcal{H}(C \cup \{v\})) \le \mathrm{cghn}(G, C) + 1$.
$(v))$ turns thereafter. Since cghn$(G, \mathcal{H}(C \cup \{v\})) \leq cghn(G, C)$, we conclude that

$$cghn^B(G, C) \leq cghn(G, \mathcal{H}(C \cup \{v\})) + 1 \leq cghn(G, C) + 1.$$

To show that bounds are tight, see that $cghn^B(C_4, \emptyset) = 2 < cghn(C_4, \emptyset) = 3$ and $cghn^B(K, \emptyset) = 4 > cghn(K, \emptyset) = 3$ where $C_4$ is the cycle with 4 vertices and $K$ is any clique with at least 4 vertices and minus one edge. $\square$

**Lemma 2.** Let $G$ be a connected graph. If there exists a $k$-strategy for Bob in the game CHG, then there exists one such strategy $f$ such that $f(C)$ is a neighbor of $C$ in $G$, for every convex set $C \subseteq V(G)$.

*Proof.* Let $f_0$ be a $k$-strategy for Bob in the game CHG. Suppose that $C \subseteq V(G)$ is a convex set with $f_0(C) = v \notin N_G(C)$ and define $\mathcal{H}(C \cup \{v\}) = C'$. Since $v \notin N_G(C)$ and $G$ is connected, there exists $w \in C' \cap N_G(C)$ that lies on a shortest path from $v$ to some vertex in $C$. By Lemma 1, since $\mathcal{H}(C \cup \{w\}) = C \cup \{w\} \subseteq C'$, we have $cghn(G, C') \leq cghn(G, C \cup \{w\})$. This inequality guarantees that if Bob selects $w$ instead of $v$, Alice (in her turn) will not be able to make the game finish in a shorter time (if Bob plays optimally). That is, there is a strategy $f_1$ for Bob in which $f_1(C) = w$ that is not worse than $f_0$. Such $f_1$ is a $k$-strategy for Bob. Repeating this argument, over the course of any game, one can see that Bob can always decide to play at a neighbor of the set of currently covered vertices. Therefore, there exists a strategy $f$ as desired. $\square$

Note that, if the graph is not connected, we can prove similarly that, in the game CHG, either Bob plays a neighbor of a covered vertex or the first selected vertex of a component.

## 3 CIG and CIG* are PSPACE-hard

In the following, we prove the PSPACE-hardness of the Closed Interval Game CIG (optimization variant), whose instance is $(G, k)$, where $G$ is a graph and $k$ is an integer, and its decision problem is to decide if Alice has a winning strategy in $G$ with at most $k$ selected vertices at the end of the game.

We first prove in Section 3.1 that an extension of CIG, the game CIG*, is PSPACE-complete. Later, we use this result to prove in Section 3.2 that CIG is PSPACE-complete.

Let CIG* be the game whose instance is $(G, k, C)$, where $G$ is a graph, $k$ is an integer and $C \subseteq V(G)$. The game proceeds like in CIG with instance $(G, k)$ with the difference that the vertices of $C$ are already selected at the beginning of the game and they do not count on $k$. Therefore, CIG with instance $(G, k)$ is equivalent to CIG* with instance $(G, k, \emptyset)$.
## 3.1 CIG* is PSPACE-complete

Our reduction is from a variant of the game KAYLES-MAX, which is the optimization version of the classical KAYLES game. In KAYLES-MAX, the instance is a graph $G$ and an integer $k$ and two players, Max and Min (starting with Max), alternate turns selecting vertices of $G$ in such a way that the set of selected vertices must always induce an independent set. Max wins if the number of selected vertices is at least $k$ at the end of the game. Otherwise, Min wins.

KAYLES-MAX was proved PSPACE-complete by Brosse et al. [10] in 2025. One can easily check that the instances constructed in the reduction of [10] have the important property of *pass-stability*. We say that an instance of a game is *pass-stable* if the player with a winning strategy also wins if the players are allowed to pass moves. Note that the notion of pass-stability is defined according to a player that has a winning strategy. Hence, the winning player will never pass and so the game is still finite and well defined even if the opponent is allowed to pass. In some games, every instance is pass-stable, such as the POSCNF game. Other games have instances that are not pass-stable, such as the Graph Coloring Game, which was also proved PSPACE-complete even for pass-stable instances [15].

We first prove in the theorem below that the variant KAYLES-MIN, in which Min is the first to play, is also PSPACE-complete even for pass-stable instances.

**Theorem 1.** KAYLES-MIN is PSPACE-complete even restricted to pass-stable instances with graphs of even order.

*Proof.* As KAYLES-MAX, it is easy to check that KAYLES-MIN is in PSPACE, since it is a game with polynomially bounded length. We prove PSPACE-hardness through a reduction from KAYLES-MAX on pass-stable instances [10].

Let $H$ be a graph and $k$ be an integer such that $1 \le k \le n = |V(H)|$ and that $(H, k)$ is a pass-stable instance of KAYLES-MAX. Let the graph $G$ and the integer $\ell$ described below be the constructed pass-stable instance of KAYLES-MIN. Let $\ell = k + 1$ and let $G$ be obtained from $H$ by including a star $K_{1,n+1}$ with center $c$ and leaves $f_1, \dots, f_{n+1}$.

In the game KAYLES-MIN, if Min does not play in $c$ in the first move, then Max selects any leaf $f_i$ in his first move, prohibiting $c$ from being selected during the game and ensuring that all leaves $f_1, \dots, f_{n+1}$ will eventually be selected, with victory for Max since $n+1 \ge k+1 = \ell$. Then we may assume that the first move (of Min) in the game KAYLES-MIN is in $c$ and then no leaf $f_i$ can be selected in the game and all next selected vertices are vertices of $H$, where Max is the first to play in $H$, which is exactly the game KAYLES-MAX with Max playing first in $H$.
Therefore, if Max wins KAYLES-MAX (playing first) in $H$ with at least $k$ selected vertices, then he wins KAYLES-MIN (playing second) in $G$ with at least $\ell = k+1$ selected vertices. Moreover, if Min wins KAYLES-MAX (playing second) in $H$ with less than $k$ selected vertices, then he wins KAYLES-MIN (playing first in the center of the star $K_{1,n+1}$) in $G$ with less than $\ell = k+1$ selected vertices.

We may assume that $|V(G)|$ is even just by increasing the number of leaves of the included star. $\square$

In the following, we use KAYLES-MIN to prove that CIG\* is PSPACE-complete.

**Theorem 2.** CIG\* is PSPACE-complete even restricted to pass-stable instances $(G, k, C)$ such that $n = |V(G)|$ is a multiple of 4, $G$ has diameter 3 and $C$ is a clique of $\lfloor n/2 \rfloor$ vertices satisfying that every vertex outside $C$ has a neighbor in $C$. The same is valid for the variant of CIG\* in which Bob plays first. In other words, $c\text{gin}(G, C)$ and $c\text{gin}^B(G, C)$ are PSPACE-hard even when $G$ has diameter 3 and $C$ is a clique with $\lfloor n/2 \rfloor$ vertices of $G$, where $n = |V(G)|$.

*Proof.* We obtain a reduction from KAYLES-MIN, which we proved PSPACE-complete in Theorem 1 even for pass-stable instances of even order. Let $(H, k)$ be an instance of KAYLES-MIN where $k$ is a positive integer and $H$ is a graph with vertices $v_1, \dots, v_n$, where $n$ is even. We shall construct an instance $(G, \ell, C)$ for CIG\*. Take $\ell = k$ and let $G$ be obtained from $H$ by adding a new vertex $c_i$ and the edge $v_ic_i$ in $G$ for every vertex $v_i$ of $H$, where $1 \le i \le n$. Also make the vertices $c_1, \dots, c_n$ form a clique $C$ and consider that all of them are already selected at the beginning of the game. Notice that $G$ has diameter at most 3 and has $2n$ vertices, which is a multiple of 4 (since $n$ is even).

When selecting a new vertex $v_i$ in the game CIG\* on $G$, every neighbor $v_j$ of $v_i$ becomes a covered vertex (cannot be selected during the game), because of the shortest path $(v_i, v_j, c_j)$. Moreover, every covered vertex not in $C$ (that is, in $H$) is neighbor of a selected vertex in $H$: in fact, since $G$ has diameter at most 3, no shortest path between selected vertices, say $v_s$ and $v_r$, can have length 4 or more and, therefore, all vertices in such a shortest path are either adjacent to $v_s$ of $v_r$. Therefore, the covered vertices in the game CIG\* on $G$ are exactly the neighbors of the selected vertices of $H$, which is exactly the game KAYLES-MIN in $H$, since Min wants to minimize the number of selected vertices in KAYLES-MIN and Alice wants to minimize the selected vertices of the game CIG\*. This shows that CIG\* is PSPACE-complete. For the variant where Bob starts we do a similar reduction from KAYLES-MAX. Since KAYLES-MAX and KAYLES-MIN are PSPACE-complete in pass-stable instances, then $(G, \ell, C)$ is a pass-stable instance of CIG\*. $\square$
## 3.2 CIG is PSPACE-complete

Now we prove that the game CIG is PSPACE-complete. We obtain a reduction from CIG*, which we proved PSPACE-complete in Theorem 2 even for pass-stable instances.

**Theorem 3.** The Closed Interval Game CIG (optimization variant) is PSPACE-complete even for pass-stable instances with diameter at most 4. The same is valid also for the variant in which Bob plays first. In other words, $c\text{gin}(G)$ and $c\text{gin}^B(G)$ are PSPACE-hard even in graphs with diameter 4.

*Proof.* Due to Theorem 2, we can start considering a pass-stable instance $(H, k, C)$ of CIG* such that $H$ is a graph with $4n$ vertices, $C$ is a clique of $H$ with $2n$ vertices (of pre-selected vertices) such that every vertex outside $C$ has a neighbor in $C$ and $k$ is an integer. Let $C = \{c_1, \dots, c_{2n}\}$.

Let us construct and instance $(G, \ell)$ for CIG, which we will prove that is pass-stable and will be used to solve CIG* for $(H, k, C)$. The graph $G$ is obtained from $H$ by including, for every vertex $c_i \in C$, the gadget $F_i$ of Figure 1, with $V(F_i) = A_i \cup B_i$, where $B_i = \{b_{i,1}, \dots, b_{i,8n+1}\}$ is an independent set with $8n+1$ vertices and $A_i = \{a_{i,1}, a_{i,2}\}$ is such that both $a_{i,1}$ and $a_{i,2}$ dominate $B_i \cup \{c_i\}$. Notice that $F_i$ does not contain $c_i$ and that $c_i$ is a cut vertex in $G$, that is, the removal of $c_i$ disconnects the gadget $F_i$ from the rest of the graph $G$. Also set $\ell = 8n^2 + 4n + k$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Gadget $F_i$ for every vertex $c_i$ of the clique $C$, where $B_i$ is an independent set with $8n+1$ vertices and $A_i = \{a_{i,1}, a_{i,2}\}$. Recall that $|V(H)| = 4n$ and $|C| = 2n$.</figcaption></figure>

**Claim 1.** If Alice is the first to play in $F_i$ (i.e., to select a vertex from $F_i$), then she can ensure the selection of at most 3 vertices of $F_i$. If Bob is the first to play in $F_i$, then he can ensure the selection of at least $8n+1$ vertices of $F_i$.
*Proof of Claim.* First suppose that Alice is the first to play in $F_i$. Then she can select $a_{i,1}$. If Bob ever plays in $B_i$, she plays in $a_{i,2}$, ensuring that no other vertex from $B_i$ can be selected during the rest of the game, summing at most 3 selected vertices in $F_i$. If Bob plays in $a_{i,2}$, no other vertex of $B_i$ can be selected.

Now suppose that Bob is the first to play in $F_i$. Then he can select $b_{i,1}$. If Alice plays in $F_i$, Bob plays (without loss of generality) in $b_{i,2}$, ensuring that at least one of $a_{i,1}$ and $a_{i,2}$ cannot be selected. Since every vertex of $B_i$ belongs to only one shortest path of $G$ and this path is between $a_{i,1}$ and $a_{i,2}$, then every vertex of $B_i$ will eventually have to be selected during the game, ensuring at least $8n + 1$ selected vertices in $F_i$. ◇

Therefore, if Alice is the first to play in more than half of the gadgets $F_i$, she ensures the selection of at most

$$3 \cdot \left( \frac{|C|}{2} + 1 \right) + (8n+1) \cdot \left( \frac{|C|}{2} - 1 \right) + 4n = 8n^2 + 2 \text{ vertices.}$$

Moreover, if Bob is the first to play in more than half of the gadgets $F_i$, he ensures the selection of at least

$$2 \cdot \left( \frac{|C|}{2} - 1 \right) + (8n+1) \cdot \left( \frac{|C|}{2} + 1 \right) = 8n^2 + 11n - 1 \text{ vertices.}$$

We prove below that both Alice and Bob, in order not to lose the game, have to be the first to play in exactly half of the gadgets $F_i$, and each gadget controlled by Alice has to have exactly 3 selected vertices and each gadget controlled by Bob has to have exactly $8n + 1$ selected vertices, summing exactly

$$3 \cdot \left( \frac{|C|}{2} \right) + (8n+1) \cdot \left( \frac{|C|}{2} \right) = 8n^2 + 4n \text{ vertices.}$$

Since $1 \le k \le 4n$, we have that $8n^2 + 2 < l < 8n^2 + 11n - 1$. Thus, if a player is the first to play in more than half of the gadgets $F_i$, they win.

So, suppose that a player $P \in \{\text{Alice, Bob}\}$ wins CIG* on $(H, k, C)$. Let $Q$ be the opponent of $P$. Let $X_i = A_i$ and $Y_i = B_i$ if $P$ is Alice; otherwise, let $X_i = B_i$ and $Y_i = A_i$.

Consider the following strategy for $P$ on CIG on the graph $G$ with integer $l$. We divide the strategy in two Phases, (i) and (ii), described below. During the game, we say that a gadget $F_i$ is an Alice's gadget if the number of selected vertices in $A_i$ is greater than in $B_i$. Analogously for a Bob's gadget. If the number of selected vertices in $A_i$ is equal to in $B_i$, we say that the gadget has no owner, which can occur when both $A_i$ and $B_i$ have 0 or 1 selected vertex. We say that the game is in Phase (i) until every gadget has an owner; after that, we say that the game is in Phase (ii).

If $P$ is Alice, she first selects $a_{1,1}$ at the beginning of the game, in Phase (i).
(i1) If the player $Q$ selects a vertex of $Y_i$ in a $P$'s gadget $F_i$ (no vertex of $Y_i$ was selected and there is exactly one vertex selected in $X_i$), then $P$ selects other vertex of $X_i$, making $F_i$ a $P$'s gadget again;

(i2) If the player $Q$ selects a vertex of $X_i$ in a gadget $F_i$ in which no vertex of $X_i$ was selected, then $P$ selects other vertex of $X_i$;

(i3) If $P$ is Bob and $Q$ (Alice) selects a vertex of $Y_i = A_i$ in a gadget $F_i$ in which no vertex was selected, then $P$ (Bob) selects a vertex of $X_i = B_i$;

(i4) Otherwise, if there is a gadget $F_i$ without selected vertices, then $P$ selects a vertex of $X_i$.

From the discussed before, we may assume that the number of Alice's gadgets will be half of the gadgets. The same for Bob's gadgets. To achieve this, at most one vertex of $H$ is selected during Phase (i) and, if a vertex of $H$ was selected, it was by $Q$=Alice (from $P$'s strategy above). Moreover, we may assume without loss of generality that $a_{i,1}$ (resp. $b_{i,1}$) is selected for any Alice's (resp. Bob's) gadget $F_i$. Consider now that we are in Phase (ii): every gadget $F_i$ has an owner. Therefore, every vertex $c_i$ is forbidden, because it is in a shortest path between two selected vertices of different gadgets.

If $P$ is Alice, she first selects a vertex of $H$ following her winning strategy in CIG\* at the beginning of Phase (ii). After that:

(ii1) If the player $Q$ selects either a vertex of $H$, or a vertex of $X_i$ in a $P$'s gadget $F_i$, or a vertex of $Y_i$ in a $Q$'s gadget $F_i$, then $P$ selects a vertex of $H$ following the winning strategy in CIG\* (recall that the graph $H$ is pass-stable in the game CIG\*);

(ii2) If the player $Q$ selects a vertex of $Y_i$ in a $P$'s gadget $F_i$ (with exactly one selected vertex in $X_i$), then $P$ selects other vertex of $X_i$, making $F_i$ a $P$'s gadget again;

(ii3) If the player $Q$ selects a vertex of $X_i$ in a $Q$'s gadget $F_i$, then $P$ selects a vertex of $X_i$, making $F_i$ a $P$'s gadget and winning the game.

With this, notice that, since every shortest path between a vertex of $F_i$ and a vertex outside $F_i$ passes through $c_i$, the game CIG on $G$ works similarly to the game CIG\* on $H$ with $C$ already selected. Moreover, the player $P$ plays in $H$ according to the winning strategy on CIG\*, ensuring at most (resp. more than) $k$ selected vertices in $H$ if $P$ is Alice (resp. Bob). Furthermore, if $P$ is Alice, she ensures at most 3 selected vertices in each Alice's gadget and at most $8n+1$ selected vertices in each Bob's gadget, summing at most $\ell$ selected vertices in $G$. Finally, if $P$ is Bob, he ensures at
least 3 selected vertices in each Alice's gadget and at least $8n + 1$ selected vertices in each Bob's gadget, summing more than $\ell$ selected vertices in $G$. $\square$

# 4 CHG is NP-hard

The HULL NUMBER problem takes a graph $G$ and $k \in \mathbb{N}$ as inputs and aims at deciding whether $\mathrm{hn}(G) \le k$, where $\mathrm{hn}(G)$ is the minimum size of a hull set of $G$.

**Theorem 4 ([1]).** *The HULL NUMBER problem is NP-complete in the class of bipartite graphs.*

Here we prove the following theorem about the closed *game* hull number.

**Theorem 5.** *Deciding whether cghn($G$) $\le k$ holds is NP-hard in the class of bipartite graphs.*

*Proof.* Let $G$ be a bipartite instance of the HULL NUMBER problem and let $H$ be the bipartite graph obtained by subdividing all edges of $G$ twice. That is, every edge $\{x, y\} \in E(G)$ is replaced by a path $(x, v_x, v_y, y)$. Note that, for every $x, y \in V(G)$ (called original vertices), $\mathrm{dist}_H(x, y) = 3 \cdot \mathrm{dist}_G(x, y)$. Therefore, for every $x, y \in V(G)$, every shortest $(x, y)$-path in $G$ corresponds to one shortest $(x, y)$-path in $H$. Moreover, for every $v_x \in V(H) \setminus V(G)$ (where $v_x$ is the neighbor of $x$ in the path resulting from the subdivision of $\{x, y\} \in E(G)$) and every $v \in V(H)$ and every shortest $(v_x, v)$-path $P$ in $H$: either $x \in V(P)$ and $P \setminus \{v_x\}$ is a shortest $(x, v)$-path in $H$, or $P' = x \cdot P$ (adding $x$ to $P$) is a shortest $(x, v)$-path in $H$. Therefore, for every hull set $S$ of $H$, there exists a hull set $S' \subseteq V(G)$ of $H$ with $|S'| \le |S|$ (indeed, for every $v_x \in S \setminus V(G)$, remove $v_x$ and add $x$ if $x \notin S$). Reciprocally, for every hull set $S \subseteq V(G)$ of $H$, $S$ is also a hull set of $G$. Hence, $\mathrm{hn}(G) = \mathrm{hn}(H)$ and there exists a minimum hull set $S$ of $H$ using only original vertices (i.e., $S \subseteq V(G)$).

Next, we shall prove that $\mathrm{cghn}(H) = 2\mathrm{hn}(G) - 1$ and so prove the NP-hardness.

Let $S \subseteq V(G)$ be a minimum hull set of $H$ using only original vertices. Hence, $|S| = \mathrm{hn}(H) = \mathrm{hn}(G)$. Alice's strategy consists of selecting each vertex of $S$: while all vertices of $H$ are not covered, Alice selects a vertex of $S$ that is not selected yet. This strategy clearly ends after at most $|S| = \mathrm{hn}(G)$ turns of Alice and therefore, $\mathrm{cghn}(H) \le 2|S| - 1 = 2\mathrm{hn}(G) - 1$.

Using similar arguments as the ones showing that $H$ has a minimum hull set consisting of original vertices, we may assume that Alice always follows a strategy where she only selects original vertices.

Now, consider the following strategy for Bob: at his turn, let $x \in V(H) \cap V(G)$ be an original vertex, already covered and with a neighbor $v_x$ not
covered (such a vertex $v_x$ must exist if $H$ is not already fully covered), then
Bob selects $v_x$. By the remarks above, this does not cover new more vertices
and it follows that, in order to cover all vertices of $H$, Alice's strategy must
have selected the original vertices of a hull set of $G$. Hence, Alice must play
at least $hn(G)$ turns and so $cghn(H) \ge 2hn(G) - 1$.

**Theorem 6.** Deciding whether cghn(G) ≤ k (resp. cgin(G) ≤ k) is NP-
hard in the class of split graphs.

*Proof.* Let (G, k) be an instance of the classical problem of Minimum Dom-
inating Set, which is NP-complete and not approximable up to log n factor
[17].

Let $G'$ be obtained from $G$ as follows. Let $V_S = \{v_1^S, \cdots, v_n^S\}$ be a stable set of order $n$. Let $C$ be a clique on $n^2$ vertices: $\{v_1^1, \cdots, v_n^1, v_1^2, \cdots, v_n^2, \cdots, v_1^n, \cdots, v_n^n\}$. For every $1 \le i, j \le n$, make $v_i^S$ adjacent to $v_1^j, \cdots, v_n^j$ if and only if $i = j$ or $\{v_i, v_j\} \in E(G)$. Clearly $G'$ is a split graph. Note that, for every $1 \le j \le n$, $v_1^j, \cdots, v_n^j$ are true twins in $G'$ (vertices with same closed neighborhood). Note also that the vertices of $V_S$ are the simplicial vertices of $G'$ (and so belong to any interval/hull set) and that the (unique) minimum hull set (resp., interval set) of $G'$ is $V_S$.

It is well known that, in a split graph, the interval of any set of vertices
equals its convex hull and so both interval and hull games behave the same
[18, 19].

Now, cghn(G) ≤ n + k − 1 if and only if γ(G) ≤ k, where γ(G) denotes
the minimum size of a dominating set in G.

Indeed, if $\gamma(G) \le k$, Alice first selects the vertices of $V_S$ that corresponds
to a dominating set of size $k$. This takes at most $2k - 1$ steps (counting the
moves of Bob). Once this is done, all vertices of $C$ are covered and it remains
at most $|V_S| - k$ steps to cover the whole $G'$.

On the other hand, while the selected vertices in $V_S$ do not correspond
to a dominating set of $G$ and less than $n$ vertices have been selected in $C$,
it remains some vertices of $C$ that can be selected by Bob, since there are
at least $n$ non-covered true twins in $C$.

5 CHG and CIG are polynomial in Trees

In this section, we show that the games CHG and CIG are polynomial time
solvable in trees.

Let $T$ be a tree with at least 3 vertices. We will denote by $L(T)$ its set
of leaves. Note that for every $\ell \in L(T)$, there is no path in $T$ for which $\ell$ is
an internal vertex. So all leaves of $T$ will have to be selected by either Alice
or Bob before the game ends. A vertex is *internal* (of the tree) if it is not a
leaf.
**Lemma 3.** Let $T$ be a tree. If there exists a $k$-strategy for Alice, then there exists a $k$-strategy for Alice such that she only selects leaves.

*Proof.* Let $T$ be a tree and $f'$ be a $k$-strategy for Alice in $T$. First, let us show that there exists a $k$-strategy for Alice in $T$ such that Alice selects only leaves except possibly at her first turn.

Consider any turn of Alice, except the first one and let $C \subseteq V(T)$ be the non-empty convex set of current covered vertices. Let $v = f'(C)$. If $v$ is a leaf, the strategy goes on until the next turn of Alice.

If $v$ is not a leaf, then $T - v$ has at least two connected components and at least one of these components has no covered vertex (otherwise $v$ would be covered). Therefore, there exists a leaf $\ell$ such that $v$ is an internal vertex of a shortest path from $\ell$ to some vertex in $C$. Therefore, $\mathcal{H}(C \cup \{v\}) \subset \mathcal{H}(C \cup \{\ell\})$. By Lemma 1, it follows that $\mathrm{cghn}^B(T, \mathcal{H}(C \cup \{\ell\})) \le \mathrm{cghn}^B(T, \mathcal{H}(C \cup \{v\}))$. Therefore, Alice can exchange $v$ for $\ell$ and play the strategy that ensures that the game will finish in $\mathrm{cghn}^B(T, \mathcal{H}(C \cup \{\ell\}))$ turns. Iterating this process, we get a $k$-strategy where, except for her first turn, Alice plays leaves, as desired.

Now, let $f'$ be a $k$-strategy where Alice plays only leaves except for, possibly, her first turn (this exists by the previous paragraph). Let $v$ be the first vertex selected by Alice, following $f'$. If $v$ is a leaf, $f'$ is already the desired strategy. So, assume $v \in V(T) \setminus L(T)$.

By definition of $k$-strategy, no matter where Bob decides to play, Alice can assure that the total number of selected vertices is at most $k$, therefore, for every $w \ne v$, we have $\mathrm{cghn}(T, \{v, w\}) \le k - 2$. In particular, fix $w$ to be any *neighbor* of $v$. Let $\ell = f'({\{v, w\}})$ (note that $\ell \in L(T)$). Let $P$ be the convex hull of $\{\ell, v, w\}$. Note that $P$ is a path between $\ell$ and either $v$ or $w$. And note that $\mathrm{cghn}^B(T, P) \le k - 3$ (again, because $f'$ is a $k$-strategy). We will define a new $k$-strategy, $f$, for Alice where she starts the game by playing at $\ell$. Starting with $\ell$ as the (only) selected vertex by Alice, we consider two cases. Case 1: Bob selects the only neighbor, $u_\ell$, of $\ell$ in the tree (as expected, but not required by Lemma 2). Clearly, $\{\ell, u_\ell\} \subset V(P)$ and Alice can select a leaf $\ell'$ such that the path $P'$ from $\ell$ to $\ell'$ extends, i.e., contains, the path $P$ (it is possible that $\ell = w$). Then, $V(P) \subseteq V(P')$ and by Lemma 1(a), $\mathrm{cghn}^B(T, P') \le \mathrm{cghn}^B(T, P) \le k - 3$. Therefore, following $f$ we will have at most $k$ selected vertices. This analysis also proves that $\mathrm{cghn}(T, \{\ell, u_\ell\}) \le k - 2$, which will be useful in the following case. Case 2: Bob selects any other vertex, covering a set of vertices $C$. Clearly, $\{\ell, u_\ell\} \subset C$ and again by Lemma 1(a), $\mathrm{cghn}^B(T, C) \le \mathrm{cghn}(T, \{\ell, u_\ell\}) \le k - 2$. In either case, the total number of turns is at most $k$, so we have a $k$-strategy for Alice such that in her the first turn she plays on a leaf. Using the same argument as in the beginning of this proof, this can be turned into a strategy where Alice only plays on leaves. $\square$
**Lemma 4.** Let $T = (V, E)$ be a tree, $C \subseteq V$ be a non-empty convex set such that $V \setminus C$ contains at least one internal vertex. If Alice has a $k$-strategy in $(T, C)$, then she has a $k$-strategy first selecting a leaf whose only neighbor is not covered (not in $C$).

*Proof.* By Lemma 3, we may assume that Alice has a $k$-strategy in $(T, C)$ only selecting leaves. The following claim must be considered in contrast with Lemma 1 (in particular, the tightness of the upper bound in item (b)).

**Claim 2.** If Alice has a $k$-strategy in $(T, C)$ (selecting only leaves) when Bob starts and can pass moves, then Alice also has a $k$-strategy in $(T, C)$ (selecting only leaves) when she starts and Bob can pass moves.

*Proof of Claim.* Let $S'$ be a $k$-strategy of Alice in $(T, C)$ when Bob starts and can pass moves. Let $v_0$ be any non-covered internal vertex (it exists by the hypothesis of the lemma). We describe a strategy $S$ for Alice starting in $(T, C)$ by following a virtual game in which Bob starts by choosing $v_0$ and Alice follows $S'$ (note that the virtual game lasts at most $k$ steps).

Let $\ell_1$ be the leaf chosen by Alice following $S'$ if Bob has started by selecting $v_0$. Then, in the strategy $S$ on $(T, C)$, Alice starts by selecting $\ell_1$. Assume, by induction on $i$, that after the $i$-th ($i \ge 1$) move of Alice: the selected vertices in the actual game (i.e., starting with Alice) are $S = \{\ell_1, v_1, \ell_2, v_2, \dots, \ell_i\}$ and so the covered vertices are $\mathcal{H}(S)$, and that the selected vertices $S'$ in the virtual game are such that $S' \setminus \{v_0\} \subseteq S$ and $\mathcal{H}(S) \subseteq \mathcal{H}(S')$.

Let $v_i$ be the next vertex chosen by Bob in the actual game (possibly $v_i = \emptyset$ if Bob passes his turn). If $v_i$ is already covered in the virtual game (for instance, if $v_i = v_0$), let $\ell_{i+1}$ be the leaf selected by Alice following $S'$ in $(T, C \cup \mathcal{H}(S'))$ (so Alice acts in the virtual game as if Bob passes his last turn, which is allowed). Otherwise (if $v_i$ is not covered in the virtual game), let $\ell_{i+1}$ be the leaf selected by Alice following $S'$ in $(T, C \cup \mathcal{H}(S' \cup \{v_i\}))$. Then, Alice selects $\ell_{i+1}$ in the actual game, i.e., $S = \{\ell_1, v_1, \ell_2, v_2, \dots, \ell_i, v_i, \ell_{i+1}\}$. The induction hypothesis holds.

Note that, at any moment, if the virtual game stops (after at most $k$ steps), then all leaves belongs to $S'$. Since $S' \setminus \{v_0\} \subseteq S$, then at the same moment, $S$ contains all leaves and the actual game also stops after at most $k$ steps. $\diamond$

Now, assume that the $k$-strategy of Alice in $(T, C)$ starts by selecting a leaf $f$ whose neighbor is covered. Let $T' = T - f$. Then, Bob can make the game last at least $1+t$ steps where $t$ is the maximum number of steps of the game in $(T', C)$ when Bob starts. On the other hand, if Alice in $(T, C)$ starts by selecting a leaf $f \in V(T') \setminus C$ whose neighbor is not covered, then the game last at least $1+t'$ steps where $t'$ is the maximum number of steps of the game in $(T', C)$ when Alice starts and Bob is allowed to pass in $T'$. By the above claim, $t' \le t$ and we are done. $\square$
The eccentricity of a vertex $v$ is the maximum distance from $v$ to the other vertices. The radius $r(G)$ of a graph $G$ is the minimum eccentricity among all vertices of $G$. The center of a graph consists of the vertices with minimum eccentricity. It is known that the center of a tree is either one vertex or two adjacent vertices.

**Theorem 7.** Let $T$ be a tree. If $|V(T)| \in \{1, 2\}$ or $T$ has radius 1, then $cghn(T) = cghn^B(T) = |V(T)|$. Otherwise,

$$cghn(T) = \left\lfloor \frac{cghn(T')}{2} \right\rfloor + |L(T)|$$

and

$$cghn^B(T) = \left\lfloor \frac{cghn^B(T')}{2} \right\rfloor + |L(T)|,$$

where $T' = T - L(T)$ is the tree obtained from $T$ by removing its leaves. Thus, $cghn(T)$ and $cghn^B(T)$ can be computed in polynomial time. Moreover, if Bob is allowed to pass turns, it cannot increase the length (the number of vertices actually selected by the players) of the game.

*Proof.* The proof is by induction on the radius of $T$. If $|V(T)| \in \{1, 2\}$, then clearly $cghn(T) = cghn^B(T) = |V(T)|$. If $T$ has radius 1 and at least 3 vertices, then $T$ is a star and Bob can always select the only internal vertex of $T$ and then $cghn(T) = cghn^B(T) = |L(T)| + 1 = |V(T)|$. Moreover, in these cases, also note that, if Bob can pass turns, this cannot increase the length of the game.

So, assume that $T$ has at least 4 vertices and radius $r \ge 2$ and let $T' = T - L(T)$. Note that the radius $r(T') = r(T) - 1$ and, by induction, let $f'$ be an optimal (i.e., finishing in $cghn(T')$ turns) strategy for Alice, playing only in the leaves of $T'$. Also, assume by induction that, following $f'$, the number of turns cannot increase if Bob can pass turns.

**Alice's strategy.** We first describe an Alice's strategy $f$ when she is first to play in $T$. Let $\ell'_1$ be the leaf of $T'$ first selected by Alice when playing $f'$ in $T'$. Then Alice selects one leaf $\ell_1$ of $T$ adjacent to $\ell'_1$.

From now on, let $v_i$ be the vertex selected by Bob just after Alice has selected her $i$-th vertex in the game on $T$ (unless if Bob passes his turn). From this, Alice will assume that Bob played on a certain vertex $v'_i$ on the game in $T'$ described below or passed his turn.

If $v_i$ is a leaf of $T$ and its neighbor $v'_i$ in $T'$ is already covered but there is a vertex not covered on $T'$, or if Bob passes his turn, Alice assumes that Bob passed his turn in the game on $T'$. That is, let $\ell'_{i+1}$ be the leaf of $T'$ selected by Alice following $f'$ assuming that Bob has passed his last turn. Then, in $T$, Alice selects any leaf $\ell_{i+1}$ of $T$ adjacent to $\ell'_{i+1}$.

If $v_i$ is a leaf of $T$ and its neighbor $u$ in $T'$ is not already covered, let $v'_i = u$. Moreover, if $v_i$ is not a leaf of $T$, let $v'_i = v_i$. Then, let $\ell'_{i+1}$ be
the leaf of $T'$ selected by Alice in her optimal strategy $f'$ in $T'$, considering
that Bob played on $v_i'$ at its $i$-th turn. Then Alice plays on a leaf $\ell_{i+1}$ of $T$
adjacent to $\ell_{i+1}'$ in the game on $T$.

Finally, if $v_i$ is a leaf of $T$ and all vertices of $T'$ are already covered, then
Alice will select any leaf of $T$.

Note that, while all vertices of $T'$ are not covered, each move of Alice
following $f$ covers exactly the same vertices of $T'$ as when she follows $f'$
in $T'$. Hence, all vertices of $T'$ are covered after at most cghn($T'$) steps,
i.e., after Alice has selected $\lfloor \frac{\text{cghn}(T')-x}{2} \rfloor + x$ leaves of $T$ and Bob has se-
lected $\lfloor \frac{\text{cghn}(T')-x}{2} \rfloor$ vertices (where $x$ is the number of turns Bob passed).
Once all vertices of $T'$ have been covered, it remains at most $|L(T)| -
\left( \lfloor \frac{\text{cghn}(T')-x}{2} \rfloor + x \right)$ leaves of $T$ that are not covered (since Alice has selected
$\lfloor \frac{\text{cghn}(T')-x}{2} \rfloor + x$ leaves and Bob might have selected ones too). Hence, if Alice
follows $f$, the game ends in at most $|L(T)| - \left( \lfloor \frac{\text{cghn}(T')-x}{2} \rfloor + x \right) + \text{cghn}(T') =$
$L(T) + \lfloor \frac{\text{cghn}(T')-x}{2} \rfloor \le |L(T)| + \lfloor \frac{\text{cghn}(T')}{2} \rfloor + \text{steps.}$

**Bob's strategy.** Now we show a Bob's strategy with at least $\lfloor \frac{\text{cghn}(T')}{2} \rfloor + |L(T)|$ vertices in the game in which Alice is first to play, given Bob's best strategy in $T'$. Recall from Lemma 3 that we may assume that Alice only plays on leaves and that, by Lemma 4 that, unless all internal vertices (i.e., of $T'$) are covered, she selects a leaf whose neighbor is not covered. Let $\ell_i$ be the leaf of $T$ selected by Alice in her $i$-th turn of the game on $T$ and let $\ell_i'$ be the leaf of $T'$ adjacent to $\ell_i$. If all vertices of $T'$ are already covered (in the game in $T$), Bob can only select leaves of $T$. Otherwise, we may assume that $\ell_i'$ was not already covered by remark above (by Lemma 4). Since $\ell_i'$ was not selected before (considering the game on $T'$), Bob assumes that Alice played on $\ell_i'$ in the game on $T'$. From this, let $v_{i+1}'$ be the vertex of $T'$ in which Bob would play in his best strategy on $T'$ after Alice selects $\ell_i'$. Then Bob plays on $v_{i+1} = v_{i+1}'$ in the game on $T$. Notice that, at the end of the game, Bob selected at least $\lfloor \text{cghn}(T')/2 \rfloor$ vertices of $T'$ in the game on $T$, and we are done (since the number of steps of the game equals the number of selected internal vertices plus the number of leaves of $T$).

Analogously for cghn<sup>B</sup>(T)

<figure><img src="image_3.png" /></figure>

6 CHG is polynomial in Cobipartite graphs

A graph $G = (V, E)$ is a cobipartite graph (complement of a bipartite graph) if there is a partition $V = A \cup B$ such that $A$ and $B$ are cliques. Denote by $S$ the set of simplicial vertices of $G$. Let $S_A = S \cap A$ and $S_B = S \cap B$. Let $U$ be the set of universal vertices of $G$. Note that if $G$ is not a complete graph, then $U \cap S = \emptyset$. Let $F$ be the graph obtained from $G$ by removing the vertices
in $S$ and $U$, and removing the edges intra-cliques, i.e., $V(F) = V \setminus (U \cup S)$ and $E(F) = \{uv \in E : u \in A \cap V(F) \text{ and } v \in B \cap V(F)\}$. Denote by $C = \{C_1, C_2, \dots, C_r\}$ with $r \ge 1$ the set of connected components $C_i$ of $F$. Note that if $G$ is neither one complete graph nor the disjoint union of complete graphs, $F$ is not empty, and every component $C_i$ has at least two vertices, for every $i \in \{1, \dots, r\}$. Indeed, any vertex in $A \setminus S_A$ (resp., in $B \setminus S_B$) has a neighbor in $B \cap V(F)$ (resp., in $A \cap V(F)$).

In the following, we will use the results presented by Araujo et al. [1] for the hull number in cobipartite graphs. In particular, to show that computing $hn(G)$ can be done in polynomial time in the class of cobipartite graphs $G$, they precisely characterized minimum hull sets of such graphs. We recall their result:

**Theorem 8 ([1]).** Let $G = (A \cup B, E)$ be a cobipartite graph (with the notations defined above). Recall that any hull set must contain $S$. Furthermore:

* If $U = \emptyset$ and $S_A \neq \emptyset$ and $S_B \neq \emptyset$ then $S$ is a minimum hull set of $G$.

* Otherwise (if $U \neq \emptyset$ or $S_A = \emptyset$ or $S_B = \emptyset$):

- If $r \ge 2$, let $v_i \in C_i \cap A$ for $i < r$ and $v_r \in C_r \cap B$, then $S \cup \{v_1, \dots, v_r\}$ is a minimum hull set of $G$.

- Otherwise (if $r=1$), let $C$ be the unique component of $F$.

* If $S_A \neq \emptyset$ and $S_B \neq \emptyset$ (and so $U \neq \emptyset$), then $S \cup \{v\}$ is a minimum hull set for every $v \in C$.

* If $S_A \neq \emptyset$ and $S_B = \emptyset$, then $h(G) \le |S| + 2$. Precisely, let $v_A \in A \cap C$ be such that $|N(v_A) \cap B \cap C|$ is maximum and let $x \in (B \cap C) \setminus N(v_A) \neq \emptyset$, then $S \cup \{v_A, x\}$ is a hull set of $G$.

* If $S_A = \emptyset$ and $S_B = \emptyset$, then $h(G) \le 4$.

We first specify one of the cases in the above theorem.

**Lemma 5.** Let $G$ be a cobipartite graph that is not a complete graph. If $S_A \neq \emptyset$ and $S_B = \emptyset$ and $r=1$, then $hn(G) = |S| + 2 = |S_A| + 2$.

*Proof.* By Theorem 8, we know that $hn(G) \le |S| + 2 = |S_A| + 2$ and that any hull set contains $S_A$. Clearly, $\mathcal{H}(S_A) = S_A$ since $S_A$ induces a clique, hence, $hn(G) > |S_A|$. For the sake of contradiction, assume that there exists a hull set $S' = S_A \cup \{v\}$ of the graph $G$. If $v \in A \cup U$, then $S'$ induces a clique and $\mathcal{H}(S') = S' \neq V(G)$. Hence, $v \in B \setminus U$.

Recall that the set $B$ contains at least two vertices since $S_B = \emptyset$. Moreover, every vertex in $B$ adjacent to some vertex in $S_A$ must be universal (because the vertices in $S_A$ are simplicial). Therefore, $v$ is adjacent to no vertex in $S_A$ (otherwise $S'$ would be a clique and $\mathcal{H}(S') = S' \neq V(G)$). Moreover, since $S_B = \emptyset$, $v$ is not simplicial, and so $N(v) \cap A \neq \emptyset$ and $B \setminus (U \cup \{v\}) \neq \emptyset$.
Therefore, $X = S_A \cup (U \cap B) \cup (N(v) \cap A) \cup \{v\} \subseteq \mathcal{H}(S') = \mathcal{H}(S_A \cup \{v\})$. But $\mathcal{H}(X) = X$ and it then can be checked that $X = \mathcal{H}(S')$. Since $(B \setminus (U \cup \{v\})) \cap X = \emptyset$, $X \neq V(G)$ and thus, $S'$ is not a hull set. $\square$

We will also use the following result.

**Lemma 6 ([18]).** Let $G$ be a graph which is not a complete graph. No hull set with cardinality $\text{hn}(G)$ contains a universal vertex.

We are now ready to prove the main result of this section.

**Theorem 9.** The cghn$(G)$ (resp., cghn$^B$(G)) can be computed in polynomial time in the class of cobipartite graphs $G$.

*Proof.* We prove the theorem in the case of cghn$(G)$, the case cghn$^B$(G) is similar. The proof follows the characterization of Theorem 8 (each of the following 5 claims corresponds to one case of Theorem 8).

Note that if $G$ is a complete graph or a disjoint union of complete graphs, then $\text{cghn}(G) = |V(G)|$. From now on, let $G$ be a cobipartite graph that is neither a complete graph nor the disjoint union of complete graphs.

**Claim 3.** Let $G$ a cobipartite graph other than a complete graph and the disjoint union of complete graphs and $U = \emptyset$, $S_A \neq \emptyset$ and $S_B \neq \emptyset$. Then, $\text{cghn}(G) = |S| + 1$.

*Proof of Claim.* By Theorem 8, $S$ is the minimum hull set for $G$ and there are no edges between $S_A$ and $S_B$, since $U = \emptyset$. Furthermore, a vertex in $S_A$ (resp. $S_B$) has no neighbor in $B$ (resp. $A$). Since $G$ is neither a complete graph nor a disjoint union of complete graphs, every vertex $u \in A \setminus S_A$ has a neighbor $v \in B \setminus S_B$ and vice versa. Let $v_A \in S_A$ and $v_B \in S_B$, observe that $(v_A, u, v, v_B)$ is a shortest $(v_A, v_B)$-path, which implies that $V(G) \setminus S \subseteq \mathcal{H}(\{v_A, v_B\})$.

Consider the following strategy for Alice: first she selects a vertex in $S_A$. If Bob then selects a vertex in $S_B$, all vertices of $V \setminus (S_A \cup S_B)$ are covered by previous remark. Then at each turn, Alice selects a vertex of $S$ that is not selected yet. The game ends in at most $|S|$ steps. Otherwise (if Bob does not select a vertex of $S_B$) then Alice selects a vertex of $S_B$ in her second turn. This covers all vertices of $V \setminus (S_A \cup S_B)$ and then it only remains to select the unselected vertices of $S$: the game ends in at most $|S| + 1$ steps.

Reciprocally, if at his first turn Bob selects a vertex in $V \setminus S$ (which is possible whatever be the first move of Alice), the game lasts at least $|S| + 1$ steps (since at least all vertices of $S$ must be selected).

Therefore, $\text{cghn}(G) = |S| + 1$. $\diamond$

**Claim 4.** Let $G$ a cobipartite graph other than a complete graph. If $U \neq \emptyset$ or $S_B = \emptyset$, and $r \geq 2$, then $\text{cghn}(G) = |S| + r + 1$.
*Proof of Claim.* By Theorem 8, $S \cup \{v_1, \dots, v_r\}$ (where $v_i \in C_i \cap A$ for $1 \le i < r$ and $v_r \in C_r \cap B$) is a minimum hull set of $G$, that is $	ext{hn}(G) = |S|+r$.

Let us first describe a strategy for Alice. She first selects a vertex in $A \cap C_1$. After the first move of Bob, if it only remains uncovered vertices of $S$, then Alice (and Bob) always selects one unselected vertex of $S$ and the strategy ends after $|S| + 2$ steps. Otherwise, there must be one vertex in $B \cap C_i$, for $1 < i \le r$, that is not covered yet (indeed, if all vertices of $(F \cap B) \setminus C_1$ are covered, then the vertices of $U \cup F$ are also covered and so it remains only the vertices of $S$). Then Alice selects a vertex in $B \cap C_i$ (this covers at least all vertices in $U$ and of $C_1$ and $C_i$). From now on, each vertex selected (by Alice or Bob) in some component $C_j$ will cover (at least) every vertex in $C_j$. Hence, Alice can play arbitrarily, and the game will end after at most $|S| + r + 1$ steps.

On the other hand, consider the following strategy for Bob. Note that, while both players select vertices only in $S \cup U$, then no vertex of $F$ can be covered. The first time Alice selects a vertex $v$ in $F$ (say in $v \in C_1$), then Bob selects another vertex in $C_1 \cap N(v)$ (this does not cover any new vertex in $S$ nor in $F \setminus C_1$). Since every hull set requires all vertices of $S$ and at least one vertex per component of $F$, this implies that the game will last at least $|S| + r + 1$ steps. $\diamond$

**Claim 5.** Let $G$ a cobipartite graph, not a complete graph or the disjoint union of complete graphs. If $U \ne \emptyset$, $S_A \ne \emptyset$ and $S_B \ne \emptyset$ and $r = 1$, then $\text{cghn}(G) = |S| + 2$.

*Proof of Claim.* By Theorem 8, for every $v \in V(F)$, $S \cup \{v\}$ is a minimum hull set.

Remind that there are no edges between $S_A$ and $S_B$ since every vertex in $S_A$ adjacent to $S_B$ would be universal and simplicial, and so $G$ would be a complete graph. In particular, for every $x \in S_A$, $y \in S_B$, $U \subseteq \mathcal{H}(\{x, y\})$.

Let us consider Alice's strategy. Alice first selects a vertex $v \in S_A$. Let $w$ be the first vertex selected by Bob. Alice then plays on any vertex $v' \in S_B$ covering all remaining vertices of $U$. Let $w'$ be the next vertex selected by Bob. If $w' \in S$, Alice selects any vertex $x \in V(F)$ which covers all vertices in $F$. Otherwise, if $w' \in F$, this covers all vertices in $F$, in which case Alice plays in $S$. In both cases, after Alice's second turn (while at least 2 vertices in $S$ have been selected), it only remains the vertices of $S$ to be covered. Hence, the game lasts at most $|S| + 2$ steps.

From Bob's point of view, by Lemma 6, it is sufficient for him to select a vertex of $U$ during his first turn to make the game last at least $|S| + 2$ steps. $\diamond$

**Claim 6.** Let $G$ be a cobipartite graph, not a complete graph or the disjoint union of complete graphs. If $r = 1$ and $S_A \ne \emptyset$ and $S_B = \emptyset$, then $	ext{cghn}(G) = |S| + 3$.
*Proof of Claim.* Let $x \in A \cap F$ such that $|N(x) \cap B \cap F|$ is maximum and $y \in B \cap F$ with $\{x, y\} \notin E(G)$. By Theorem 8, $S_A \cup \{x, y\}$ is a minimum hull set of $G$. Moreover, $F \subseteq \mathcal{H}(\{x, y\})$.

Consider the following Alice's strategy. First, she selects $x$, then at her second turn she selects $y$ (if $y$ was already covered, then only the vertices in $S_A$ are not covered) and then she always selects uncovered vertices in $S_A$. This strategy ends in at most $|S_A| + 3$ steps.

Now, consider an arbitrary strategy for Alice. If she first selects a vertex $w \in U$, then by Lemma 6 and Lemma 5, the game will last at least $|S_A| + 3$ steps whatever Bob does. Otherwise, Bob can select a vertex in $U$ at his first turn, and so, by the same argument, the game will last at least $|S_A| + 3$ steps.
$\diamond$

**Claim 7.** Let $G$ be a cobipartite graph with $|V(G)| \ge 3$. If $r = 1$ and $S_A = \emptyset$ and $S_B = \emptyset$, then $cghn(G) \le 7$ can be computed in polynomial time. In particular, if $hn(G) = 2$, then $cghn(G) = 3$.

*Proof of Claim.* Recall that, in this case, $hn(G) \le 4$ and a minimum hull set of $G$ can be computed in polynomial time by Theorem 8.

If $hn(G) = 2$, let $\{x, y\} \subseteq V(G)$ be a minimum hull set. In her first two turns, Alice selects $x$ and then $y$ ensuring that the game ends after 3 turns. Moreover, Bob can always ensure that the game lasts at least 3 turns by selecting, in his first turn, a vertex on the same side ($A$ or $B$) as the first vertex selected by Alice. Hence, if $hn(G) = 2$, then $cghn(G) = 3$.

In the case $hn(G) \in \{3, 4\}$, then $cghn(G) \le 2hn(G) - 1 \le 7$ since Alice can select all vertices of a minimum hull set in $hn(G)$ of her turns.

Therefore, the *rooted tree of the game* (where the root is the configuration where no vertices have been selected and each node has children the configuration obtained after the current player has done a choice) has maximum degree $n = |V(G)|$ and height at most 7. Hence, it has polynomial $(O(n^7))$ size and a classical backtrack labeling algorithm can determine an optimal strategy. Thus, $cghn(G)$ can be computed in polynomial time.
$\diamond$
$\square$

# 7 Conclusion

The main remaining open question is whether the closed hull game, CHG, (optimization variant) is PSPACE-complete, which we conjecture to be true. It is also interesting to find other graph classes in which the decision problems of the games CHG and CIG (optimization variants) are polynomial time solvable. Unfortunately, it seems that the closed interval game CIG is hard on cobipartite graphs as the following argument suggests. First we prove that deciding if a cobipartite graph admits an interval set of size $k$ is
NP-complete (to the best of our knowledge, this was only proved for oriented
graphs [2]).

**Theorem 10.** *The problem of deciding if a cobipartite graph has an interval set (in the geodesic or $P_3$ convexities) with at most $k$ vertices is NP-complete.*

*Proof.* The problem is clearly in NP. Let $(H, k)$ be an instance for the of the Minimum Dominating Set problem, where $H = (A \cup B, E)$ is a connected bipartite. Let $G$ be obtained from $H$ by adding a vertex $a$ dominating $A$, a vertex $b$ dominating $B$, a vertex $u$ dominating all $V(H) \cup \{a, b\}$ and by completing both $A$ and $B$ into cliques. Note that $a$ and $b$ are simplicial. Also note that $G$ has diameter 2 (and then the geodesic and $P_3$ convexities coincide).

Then $G$ has an interval set of size at most $k+2$ if and only if $H$ has a
dominating set of size at most $k$.

Indeed, $a$ and $b$ must be in any interval set, since they are simplicial.
Moreover, $u$ is in no minimum interval set. Now, let $\{a, b\} \subseteq S \subseteq V(G)$.
Note that $S$ is an interval set if and only if $S \cap V(H)$ is a dominating set of
$H$. Indeed, if $N[v] \cap S \cap V(H) = \emptyset$ for some $v \in V(H)$, then $v \notin I(S)$. On
the other hand, if $v \in V(H) \setminus S$ has a neighbor $w \in S \cap V(H)$, then $v \in I(S)$,
since either $v \in I(\{a, w\})$ (if $v \in B$) or $v \in I(\{b, w\})$ (if $v \in A$). $\square$

The above reduction implies that, in the closed interval game CIG, Alice must ensure the selection of a dominating set of $H$, which also must be an independent set (since the game is closed). In other words, she aims at obtaining an independent set of $H$ as small as possible. That is, Alice and Bob are playing the optimization variant of the Kayles game on $H$ where the first player aims at minimizing the obtained independent set. This problem is PSPACE-complete by Theorem 1. However, since $H$ is bipartite, to prove that the closed interval game is PSPACE-complete in cobipartite graphs, we would need to show that the optimization variant of the Kayles game starting with Bob is PSPACE-complete in bipartite graphs, which is still an open question.

References

[1] J. Araujo, V. Campos, F. Giroire, N. Nisse, L. Sampaio, and R. Soares. On the hull number of some graph classes. *Theoretical Computer Science*, 475:1–12, 2013.

[2] J. Araújo and P.S.M. Arraes. Hull and geodetic numbers for some classes of oriented graphs. *Discrete Applied Mathematics*, 323:14–27, 2022.
[3] Samuel N. Araújo, João Marcos Brito, Raquel Folz, Rosiane de Freitas, and Rudini M. Sampaio. Graph convexity impartial games: Complexity and winning strategies. *Theoretical Computer Science*, 998:114534, 2024.

[4] Samuel N. Araújo, João Marcos Brito, Raquel Folz, Rosiane de Freitas, and Rudini M. Sampaio. Algorithms and complexity of graph convexity partizan games. *Theoretical Computer Science*, 1044:115267, 2025.

[5] Bret J Benesh, Dana C Ernst, Marie Meyer, Sarah K Salmon, and Nándor Sieben. Impartial geodetic building games on graphs. *Int. J. Game Theory*, 2025.

[6] Hans L. Bodlaender and Dieter Kratsch. Kayles and Nimbers. *Journal of Algorithms*, 43(1):106–119, 2002.

[7] Hans L. Bodlaender, Dieter Kratsch, and Sjoerd T. Timmer. Exact algorithms for Kayles. *Theoretical Computer Science*, 562:165–176, 2015.

[8] Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, and Gabriel Renault. Complexity of the game domination problem. *Theoretical Computer Science*, 648:1–7, 2016.

[9] João Marcos Brito, Thiago Marcilon, Nicolas Martins, and Rudini Sampaio. The Normal Domination Game in graphs. *arXiv*, arXiv:2502.13118, 2025.

[10] Caroline Brosse, Nicolas Martins, Nicolas Nisse, and Rudini Sampaio. The Convex Set Forming Game. *Theoretical Computer Science*, 1046:115323, 2025.

[11] F. Buckley and F. Harary. Closed geodetic games for graphs. *Congressus Numerantium*, 47:131–138, 1985. Proceedings of the 16th Southeastern Conference on Combinatorics, Graph Theory and Computing.

[12] F. Buckley and F. Harary. Geodetic games for graphs. *Quaestiones Mathematicae*, 8:321–334, 1985.

[13] Ullas Chandran S. V., Sandi Klavžar, Neethu P. K., and Rudini M. Sampaio. The general position avoidance game and hardness of general position games. *Theoretical Computer Science*, 988:114370, 2024.

[14] Gary Chartrand, Curtiss E. Wall, and Ping Zhang. The convexity number of a graph. *Graphs and Combinatorics*, 18(2):209–217, 2002.

[15] Eurinardo Costa, Victor Lage Pessoa, Rudini Sampaio, and Ronan Soares. PSPACE-completeness of two graph coloring games. *Theoretical Computer Science*, 824-825:36–45, 2020.
[16] Antoine Dailly, Harmender Gahlawat, and Zin Mar Myint. The closed geodetic game: Algorithms and strategies. In *IWOCA, LNCS*, volume 15885, pages 273–286, 2025.

[17] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In *Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing*, STOC'14, pages 624–633, New York, USA, 2014. ACM.

[18] Mitre C Dourado, John G Gimbel, Jan Kratochvíl, Fábio Protti, and Jayme L Szwarcfiter. On the computation of the hull number of a graph. *Discrete Mathematics*, 309(18):5668–5674, 2009.

[19] Mitre C. Dourado, Fábio Protti, Dieter Rautenbach, and Jayme L. Szwarcfiter. Some remarks on the geodetic number of a graph. *Discrete Mathematics*, 310(4):832–837, 2010.

[20] Pierre Duchet. Convexity in combinatorial structures. In *Proc. 14th Winter School on Abstract Analysis*, pages [261]-293. Circolo Matem- atico di Palermo, 1987.

[21] P. Erdős, E. Fried, A. Hajnal, and E.C. Milner. Some remarks on simple tournaments. *Algebra universalis*, 2:238–245, 1972.

[22] Martin G. Everett and Stephen B. Seidman. The hull number of a graph. *Discrete Mathematics*, 57(3):217–223, 1985.

[23] F. Harary. Convexity in graphs: Achievement and avoidance games. In *Annals of Discrete Mathematics* (20), volume 87, page 323. North- Holland, 1984.

[24] F. Harary and J. Nieminem. Convexity in graphs. *Journal of Differen- tial Geometry*, 16(1):185–190, 1981.

[25] Frank Harary, Emmanuel Loukakis, and Constantine Tsouros. The geodetic number of a graph. *Mathematical and Computer Modelling*, 17(11):89–95, 1993.

[26] T.W. Haynes, M.A. Henning, and C. Tiller. Geodetic achievement and avoidance games for graphs. *Quaestiones Mathematicae*, 26:389–397, 2003.

[27] M. Nečáková. A note on the achievement geodetic games. *Quaestiones Mathematicae*, 12:115–119, 1988.

[28] T. Schaefer. On the complexity of some two-person perfect-information games. *Journal of Computer and System Sciences*, 16(2):185–225, 1978.