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

HAL
open science

# The Convex Set Forming Game

Caroline Brosse, Nicolas Martins, Nicolas Nisse, Rudini Sampaio

► To cite this version:

Caroline Brosse, Nicolas Martins, Nicolas Nisse, Rudini Sampaio. The Convex Set Forming Game. Theoretical Computer Science, 2025, 10.2139/ssrn.4989701. hal-05071488v2

HAL Id: hal-05071488

https://hal.science/hal-05071488v2

Submitted on 19 May 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Convex Set Forming Game*

C. Brosse¹, N. Martins², N. Nisse¹, and R. Sampaio†³

¹Université Côte d'Azur, Inria, CNRS, I3S, Sophia-Antipolis, France

²Univ. Integ. Intern. Lusofonia Afro-Brasileira, Redenção, Brazil

³Dept Computação, Universidade Federal do Ceará, Fortaleza, Brazil

## Abstract

In 1984, Frank Harary introduced the first graph convexity game, focused on the geodesic convexity. A set $S \subseteq V$ of vertices of a graph $G = (V, E)$ is convex if every shortest path between two vertices of $S$ is also included in $S$. We introduce the Convex Set Forming Game CFG: two players alternately select vertices in such a way that the set of selected vertices is always a convex set. In the normal (resp., misère) variant, the last player to be able to select a vertex wins (resp., loses). We also define a new graph invariant $gc(G)$ as the largest integer $k$ such that the first player has a strategy ensuring that, at the end of the game, at least $k$ vertices of the graph $G$ have been selected. We first show that the problems of deciding the outcome (does the first player win?) of the game in both variants (normal and misère), as well as the problem of deciding whether $gc(G) \ge k$, are PSPACE-complete. As a by-product, we prove that the optimization variant of the classical KAYLES game is PSPACE-complete. Then, we focus on convexable graphs, i.e., $n$-node graphs $G$ for which $gc(G) = n$. For this purpose, we say that a set $S = \{v_1, \cdots, v_{|S|}\} \subseteq V$ in a graph $G$ admits a Convex Elimination Ordering (CEO) if $\{v_1, \cdots, v_i\}$ is convex for every $1 \le i \le |S|$. We show that the class of graphs whose vertex-set admits a CEO coincides with the chordal graphs and that this class strictly contains the convexable graphs. Moreover, every graph which is Ptolemaic (distance-hereditary chordal) or unit interval is convexable. Finally, we give a polynomial-time algorithm for computing a largest set admitting a CEO in

<footnote>*Research supported by the projects ANR-17-EURE-0004 "EUR DS4H Investments in the Future", CAPES-Cofecub Ma 1004/23, CNPq 404479/2023-5, by the research grants ANR P-GASE and ANR DiGraphs, and by the Inria Associated Team CANOE.</footnote>

<footnote>†email: caroline.brosse@inria.fr, nicolasam@unilab.edu.br, nicolas.nisse@inria.fr, rudini@dc.ufc.br</footnote>
outerplanar graphs, which gives upper bounds on $gc(G)$ in outerplanar graphs $G$.

**Keywords:** Convexity number, geodesic games, PSPACE-hardness, chordal graphs.

# 1 Convexity games

Convexity is a classical topic, studied in many different branches of mathematics. The study of convexities applied to graphs has started about 50 years ago. The 1972 paper of Erdős et al. [14] is one of the first in this topic, focused in tournaments. According to Duchet [12], the first paper on general graphs, published in English, is the 1981 paper "Convexity in graphs" from Frank Harary and Juhani Nieminen [17]. The main convexity that has been studied is the *geodesic convexity*, in which a set $S \subseteq V$ of vertices of a graph $G = (V, E)$ is *convex* if, for every $u, v \in S$, then every $w \in V$ on a shortest path between $u$ and $v$ also belongs to $S$. Typical questions are to compute a largest convex proper subset of $V$ [8], or to compute a smallest hull set (subset of vertices whose convex hull is the whole graph) [15].

In 1984, Harary introduced the first graph convexity games in his abstract "Convexity in graphs: achievement and avoidance games" [16]. These games were investigated in a sequence of five papers [5, 6, 16, 18, 23] from 1985 to 2003, all of them focused on the geodesic convexity. After a gap of twenty years, it was proved in 2024 the first PSPACE-hardness results on graph convexity games [1] and polynomial time algorithms were obtained for cactus and block graphs [10]. Recently, another game related to hull sets has been studied in [2].

In this paper, we introduce a new natural two-player game related to convexity: the Convex Set Forming game (CFG). Two players, Alice and Bob, select vertices of a connected graph $G$ in such a way that the set of selected vertices is always a convex set. More precisely, Alice and Bob alternately (starting with Alice) select any not already selected vertex $v$ such that $S \cup \{v\}$ is a convex set of $G$, where $S$ is the set of previously selected vertices. The game ends when no such a vertex exists (i.e., when $S \cup \{v\}$ is not convex for every $v \notin S$). In the normal variant, denoted CFG-NORMAL, the last to play wins. In the misère variant, denoted CFG-MISÈRE, the last to play loses. In the optimization variant, denoted CFG-OPT, it is also given an integer $k$ in the instance and Alice wins if the game stops with at least $k$ selected vertices, and Bob wins otherwise. From the classical Zermelo-von Neumann theorem [25], one of the two players has a winning strategy in each one of these variants, since they are finite perfect-information games without draw. So, the decision problem of these games is whether Alice has a winning strategy.

The study of CFG-OPT naturally leads us to define a new graph invariant $gc(G)$ which is the largest integer $k$ such that Alice has a strategy ensuring (whatever Bob
does) that, at the end of the game, at least $k$ vertices of the graph $G$ have been selected. Hence, CFG-OPT is equivalent to the problem of deciding, given a graph $G$ and $k \in \mathbb{N}$, whether $\text{gc}(G) \ge k$.

As an example, consider a cycle $C_4$ with four vertices. Alice first selects any vertex $v$. Then Bob must select a neighbour of $v$ (note that, when $G$ is connected, the set of selected vertices must always induce a connected subgraph) and the game stops since any set with three vertices in $C_4$ is not convex. Therefore, Bob wins the normal variant, Alice wins the misère variant, and Alice wins the optimization variant if and only if $k \le 2$, i.e., $\text{gc}(C_4) = 2$.

**Our Contributions.** We first focus on the complexity of deciding the outcome of the game. The Convex Set Forming game (CFG) is similar to the classical CLIQUE FORMING and KAYLES<fnref n="1" /> games, both proved PSPACE-hard [24] in 1978. The difference is that in the CLIQUE FORMING game (resp. KAYLES game) the selected vertices must always induce a clique (resp. independent set), instead of a convex set. In Section 2, we prove that the three variants of CFG are PSPACE-complete, by reductions from the CLIQUE FORMING game. We remark that these results also hold in the case of the *monophonic convexity*<fnref n="2" />.

As a by-product, we also prove that the optimization variants of the CLIQUE FORMING and KAYLES games are PSPACE-complete, and consequently the corresponding parameters *game clique number* $\omega_g(G)$ and *game independence number* $\alpha_g(G)$ are PSPACE-hard to compute.

In Section 3, we then study the *convexable* graphs, i.e., the connected $n$-node graphs $G$ such that $\text{gc}(G) = n$. As an example, consider any tree $T$. The set of selected vertices during the game always induces a subtree $T'$ of $T$ and can always be enlarged, except if $T' = T$. Then, every tree is convexable. Note that, for a graph $G$ to be convexable, there must be an ordering $(v_1, \cdots, v_n)$ of its vertices such that $\{v_1, \cdots, v_i\}$ is convex for every $1 \le i \le n$. Given a graph $G = (V, E)$ and $S \subseteq V$, we say that $S$ admits a *Convex Elimination Ordering* (CEO) if $S$ can be ordered $(v_1, \cdots, v_{|S|})$ such that $\{v_1, \cdots, v_i\}$ is convex for every $1 \le i \le |S|$. A graph is said *CEO* if its vertex-set admits a CEO. We show that the class of CEO graphs actually coincides with the class of chordal graphs and that this class strictly contains the class of convexable graphs. Then, we show that the class of convexable graphs strictly contains the classes of Ptolemaic graphs (distance hereditary chordal) and of unit interval graphs. We leave the question of the complexity of recognizing

<footnote n="1">¹Some authors differentiate the original KAYLES game from [13], while calling NODE-KAYLES for the game on general graphs. We follow other authors, such as [3], who use only the name KAYLES.</footnote>

<footnote n="2">²In the monophonic convexity, a set $S$ of vertices of a graph $G$ is *m-convex* if, for every $u, v \in S$, then every vertex $w$ on an induced path between $u$ and $v$ also belongs to $S$ [21].</footnote>
a convexable graph as an open problem.

Finally, in Section 4, we show that a largest set admitting a CEO can be computed in polynomial time in the class of outerplanar graphs. Note that the size of a largest set admitting a CEO in a graph $G$ provides an upper bound on $gc(G)$.

We conclude with several open questions.

## 2 PSPACE-hardness of Convex Set Forming game

In this section, we prove that the normal, misère and optimization variants of the Convex Set Forming game CFG are PSPACE-complete. As mentioned before, we consider the games as decision problems: does Alice have a winning strategy? In the normal and misère variants, the instance is a graph and, in the optimization variant, the instance is a graph and a positive integer $k$. Since the number of turns is at most $n$ and, in each turn, the number of possible vertices to label is at most $n$, all these game variants are polynomially bounded two player games, which implies that they are in PSPACE [19].

We obtain reductions from the normal, misère and optimization variants of the CLIQUE FORMING game. The normal variant was proved PSPACE-complete [24] in 1978 and the misère variant was proved PSPACE-Complete [7] recently in 2024. The optimization variant of the CLIQUE FORMING game was not proved PSPACE-hard before and we did this at the end of this section. In the CLIQUE FORMING game, two players, Alice and Bob, starting by Alice, alternately select vertices and the subset of the chosen vertices must induce a clique at any turn. As usual, the last to play wins in the normal variant and loses in the misère variant. Moreover, in the optimization variant, Alice wins if the resulting clique has size at least $k$ at the end. This is related to the KAYLES game, in which the objective is to get an independent set, instead of a clique. The CLIQUE FORMING game is the KAYLES game played on the complement of the graph, and vice-versa.

**Theorem 2.1.** *The normal, misère and optimization variants of the Convex Set Forming game CFG are PSPACE-complete even in graphs with diameter two.*

*Proof.* We first obtain a reduction for CFG-NORMAL. Let $G$ be an instance of the normal variant of the CLIQUE FORMING game. We may assume that $G$ is not complete.

Let $G'$ be the graph obtained from $G$ by adding four new vertices $u_1, u'_1, u_2$ and $u'_2$ adjacent to all vertices of $G$, and the edges $u_1u'_1$ and $u_2u'_2$. See Figure 1. Notice that $G'$ has diameter 2. We prove that Alice has a winning strategy in the normal CLIQUE FORMING game on $G$ if and only if she has a winning strategy in the normal variant of CFG on $G'$. Notice that the set of selected vertices must
induce a clique, since $u_1, u'_1, u_2$ and $u'_2$ are in shortest paths in $G'$ between any two non-adjacent vertices of $G$. Suppose that Alice has a winning strategy on the normal CLIQUE FORMING game on $G$. If Bob selects $u_1$ (resp. $u_2$), she selects $u'_1$ (resp. $u'_2$). Otherwise, she follows her winning strategy on $G$. Since she is the last to play in the CLIQUE FORMING game on $G$, then she is also the last to play in CFG on $G'$. Similarly if Bob has a winning strategy.

Regarding CFG-MISÈRE, we have exactly the same reduction, but from the misère variant of the CLIQUE FORMING game, which was proved PSPACE-hard [7] in 2024. The arguments are very similar.

Regarding CFG-OPT, we also have the same reduction from the graph $G$ to the graph $G'$, but now it is given a positive integer $k$ in the CLIQUE FORMING game. So let $k' = k + 2$ be the positive integer which is part of the instance of CFG-OPT together with $G'$. Similarly from the arguments before, Alice has a winning strategy in the optimization variant of the CLIQUE FORMING game on $G$ with $k$ vertices if and only if she has a winning strategy in CFG-OPT on $G'$ with $k' = k+2$ vertices. $\square$

<figure><img src="image_3.png" /><figcaption>Figure 1: Graph $G$ of the reductions in Theorem 2.1 on the normal and misère variants of CFG.</figcaption></figure>

Finally, we prove the PSPACE-hardness of the optimization variants of the CLIQUE FORMING game and the KAYLES game. We first reproduce in Theorem 2.2 the 1978 PSPACE-hardness proof of the normal KAYLES game [24], since our proof in Theorem 2.3 is strongly based on it.

**Theorem 2.2** (Schaefer, 1978). The normal KAYLES game is PSPACE-complete.

*Proof.* Recall that, in the KAYLES game, the players have to choose a vertex not adjacent to any of the previously selected vertices. Reduction from the QSAT problem (Quantified SAT, also called TQBF): it is given a totally quantified CNF formula $\Phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $B_1, \dots, B_m$, where the quantifiers are alternately $\exists$ and $\forall$ starting from $x_n$ to $x_1$. This can be seen as a game in which Alice and Bob alternately set true or false to the variables $x_n, x_{n-1}, \dots, x_1$ in this order. Alice wins if the formula is true at the end; otherwise, Bob wins.

Consider the example $\Phi = \exists x_3 \forall x_2 \exists x_1 : B_1 \wedge B_2 \wedge B_3$, with the following clauses: $B_1 = (x_1 \vee \bar{x}_1)$, $B_2 = (x_1 \vee \bar{x}_2)$ and $B_3 = (\bar{x}_1 \vee x_2 \vee x_3)$. In this example, Alice wins,
since Alice sets true to the variable $x_3$ in the first turn (in order to satisfy clause $B_3$), Bob then sets true to the variable $x_2$ (trying to make $B_2$ unsatisfied) and Alice must set true to variable $x_1$, satisfying all clauses and winning the game.

Schaefer [24] assumes that the number $n$ of variables is odd (otherwise we can add a new variable which does not appear in any clause) and the first clause $B_1$ is $(x_1 \lor \overline{x_1})$, which is always satisfied and does not change the outcome of the game. Given a QSAT formula $\Phi$, the constructed graph $G = G(\Phi)$ is described below.

For $i \in [n]$, create in $G$ the vertices $x_i$ and $\overline{x_i}$ associated to the variable $x_i$. For $k \in [m]$, create the vertex $x_{0,k}$ associated to the clause $B_k$. For $i \in [n]$ and $j \in \{0, \dots, i-1\}$, create the vertex $y_{i,j}$. Let $X_i$ be the set with all the vertices $x_i, \overline{x_i}$ and $y_{i,j}$, and make $X_i$ be a clique in $G$. Let $X_0$ be the set with the vertices $x_{0,1}, \dots, x_{0,m}$ associated to the clauses, and make $X_0$ be a clique in $G$.

If the literal $x_i$ is in the clause $B_k$, create the edge $x_ix_{0,k}$. If the literal $\overline{x_i}$ is in the clause $B_k$, create the edge $\overline{x}_i x_{0,k}$. For $i \in [n]$ and $j \in \{0, \dots, i-1\}$, create the edge $y_{i,j}w$ for every vertex $w \in (X_0 \cup \dots \cup X_{i-1}) - X_j$. This ends the reduction of [24]. See Figure 2 for the formula $\Phi$ mentioned above, which is the same example in [24].

<figure><img src="image_4.png" /><figcaption>Figure 2: Example of the construction of Theorem 3.2 of [24] from the input formula $\exists x_3 \forall x_2 \exists x_1 : (x_1 \lor \overline{x_1}) \land (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2 \lor x_3)$. A line leading to an enclosure represents multiple edges leading to each vertex in the enclosure. Also, within each enclosure, all vertices are mutually joined by edges, which are not shown.</figcaption></figure>
Schaefer [24] defines a game as legitimate if for $i = 1, \dots, n$ the vertex selected at move $i$ is either $x_{n-i+1}$ or $\bar{x}_{n-i+1}$. If a player does an illegitimate move when all previous moves were legitimate, then the other player wins immediately. In order to prove this, fix $i \in [n]$ and assume that the first $n-i$ moves were legitimate, that is, the vertices selected so far are one of each pair $\{x_n, \bar{x}_n\}, \dots, \{x_{i+1}, \bar{x}_{i+1}\}$. Clearly, from the construction of $G$, no vertex of $X_n \cup X_{n-1} \cup \dots \cup X_{i+1}$ can be played now. Suppose that the player on move $n-i+1$ plays illegitimately, by selecting a vertex from $X_i \cup \dots \cup X_0$ other than $x_i$ or $\bar{x}_i$. If the player selects a node in $X_k$, for $k < i$, then the opponent wins by choosing $y_{i,k}$ and no other vertex is playable, since any vertex of $X_k$ is adjacent to the illegitimately played vertex and any vertex of $(X_0 \cup \dots \cup X_i) - X_k$ is adjacent to $y_{i,k}$. Finally, if the illegitimate move is in $X_i$, it must be $y_{i,k}$ for some $k < i$ and therefore the opponent wins by selecting $x_k$ if $k > 0$ or $x_{0,1}$ if $k = 0$, which is playable because of the assumption about $B_1$. As before, no other vertex is playable.

As a consequence, we may consider from now on that the players move legiti-
mately. Then every move on the QSAT game in $\Phi$ has an obvious corresponding
move on the KAYLES game in $G(\Phi)$, and vice-versa: setting $x_i$ true (resp. false) in
QSAT corresponds to selecting the vertex $x_i$ (resp. $\bar{x}_i$) in KAYLES, and vice-versa.

If Alice has a winning strategy on a formula $\Phi$ of QSAT, Alice can play the
corresponding moves on the graph $G(\Phi)$ of KAYLES. After the last move of QSAT,
all clauses are satisfied (because of the winning strategy of Alice on QSAT) and then
no clause vertex is playable on KAYLES. Since $n$ is odd, Alice is the last to play,
winning the KAYLES game.

Finally, if Bob has a winning strategy on a formula $\Phi$ of QSAT, Bob can play
the corresponding moves on the graph $G(\Phi)$ of KAYLES. After the last move of
QSAT, there is at least one non-satisfied clause (because of the winning strategy of
Bob on QSAT) and then there is a playable clause vertex on KAYLES. Since $n$ is
odd, Alice selected either $x_1$ or $\bar{x}_1$ and Bob can select a playable clause vertex in
the next move, winning the KAYLES game.
□

Now we are able to prove the PSPACE-hardness of the optimization variants
of the CLIQUE FORMING and KAYLES games, and the corresponding parameters
game clique number $\omega_g(G)$ and game independence number $\alpha_g(G)$. The game clique
number $\omega_g(G)$ is the maximum $k$ such that Alice has a winning strategy with at least
$k$ vertices in the CLIQUE FORMING game. The game independence number $\alpha_g(G)$ is
the maximum $k$ such that Alice has a winning strategy with at least $k$ vertices in the
KAYLES game. Clearly, $\omega_g(G) \le \omega(G)$, $\alpha_g(G) \le \alpha(G)$ and $\omega_g(G) = \alpha_g(\bar{G})$, where
$\omega(G)$ and $\alpha(G)$ are the clique number and the independence number, respectively.

**Theorem 2.3.** *The optimization variants of the CLIQUE FORMING game and the KAYLES game are PSPACE-complete. Consequently, the game clique number $\omega_g(G)$*
and the game independence number $\alpha_g(G)$ are PSPACE-hard to compute.

*Proof.* Since the optimization variant of the CLIQUE FORMING game is the optimization variant of the KAYLES game played on the complement of the graph (and vice-versa), we will only prove that the optimization variant of the KAYLES game is PSPACE-hard.

We obtain a reduction from a variant of the QSAT problem, which we call QSAT', based on the reduction of [24] for the KAYLES game (see Theorem 2.2 above). In QSAT', Alice wants to make the formula false and Bob wants to make the formula true. This is the same as QSAT played on the complement of the formula. Thus, QSAT' is also PSPACE-Complete.

Following the proof of Theorem 2.2, instead of assuming that the number $n$ of variables is odd, we assume that $n$ is even. As in the proof of Theorem 2.2, we can do this since it is possible to add a new variable which does not appear in any clause. We also assume that $B_1 = (x_1 \lor \bar{x}_1)$.

Given a QSAT' formula $\Phi$, let $G = G(\Phi)$ be the graph constructed in the proof of Theorem 2.2. Let $G' = G'(\Phi)$ be the graph obtained from $G$ by replacing for $0 \le i < n/2$ every vertex $y_{n-2i,j}$ and $y_{n-2i-1,j}$ by independent sets $Y_{n-2i,j}$ and $Y_{n-2i-1,j}$ with $n-2i-1$ vertices each (respecting the adjacencies of $y_{n-2i,j}$ and $y_{n-2i-1,j}$). See Figure 3.

Moreover, the positive number of the optimization variant instance is $n+1$, where $n$ is the number of variables. That is, Alice wants to obtain an independent set of size greater than $n$, and Bob wants to avoid this.

As in the proof of Theorem 2.2, we can define a move $i$ as legitimate if the selected vertex is either $x_{n-i+1}$ or $\bar{x}_{n-i+1}$.

We also prove that, if an illegitimate move is done after all previous moves were legitimate, then the other player wins the optimization variant of the KAYLES game. For this, fix $i \in [n]$ and assume that the first $n-i$ moves were legitimate. From the construction of $G'$, no vertex of $X_n \cup X_{n-1} \cup \dots \cup X_{i+1}$ can be played now. Suppose that the player on move $n-i+1$ plays illegitimately, by selecting a vertex from $X_i \cup \dots \cup X_0$ other than $x_i$ or $\bar{x}_i$. If the player selects a node in $X_k$, for $k < i$, then the opponent wins by choosing a vertex of $Y_{i,k}$ and then only the other vertices of $Y_{i,k}$ are playable, since any vertex of $X_k$ is adjacent to the illegitimately played vertex and any vertex of $(X_0 \cup \dots \cup X_i) - X_k$ is adjacent to $Y_{i,k}$. We explain better this winning argument in the next paragraph. Finally, if the illegitimate move is in $X_i$, it must be in a vertex of $Y_{i,k}$ for some $k < i$ and therefore the opponent wins by selecting $x_k$ if $k > 0$ or $x_{0,1}$ if $k = 0$, which is playable because of the assumption about $B_1$. As before, if the illegitimate move was in $Y_{i,k}$, then only the other vertices of $Y_{i,k}$ are playable.

Recall that $n$ is even. Notice that, if $i$ is even, then the illegitimate move was from Alice and then the number of selected vertices is $(n-i)+1+|Y_{i,k}| = n-i+1+(i-1) =$
<figure><img src="image_5.png" /><figcaption>Figure 3: Example of the modification on the construction of Theorem 3.2 of [24] from the input formula $∃x_3∀x_2∃x_1 : (x_1 ∨ \bar{x}_1) ∧ (x_1 ∨ \bar{x}_2) ∧ (\bar{x}_1 ∨ x_2 ∨ x_3)$. The numbers in red are the sizes of the corresponding independent sets $Y_{i,j}$, where $n = 4$.</figcaption></figure>

$n$ for some $k$. Moreover, if $i$ is odd, then the illegitimate move was from Bob and then the number of selected vertices is $(n-i)+1 + |Y_{i,k}| = n-i+1+i = n+1$ for some $k$.

As a consequence, we may consider from now on that the players move legitimately in the optimization variant of the KAYLES game. Then every move on the QSAT' game in $\Phi$ has an obvious corresponding move on the optimization variant of the KAYLES game in $G'(\Phi)$, and vice-versa: setting $x_i$ true (resp. false) in QSAT' corresponds to selecting the vertex $x_i$ (resp. $\bar{x}_i$) in KAYLES, and vice-versa.

If Bob has a winning strategy on a formula $\Phi$ of QSAT', he can play the corresponding moves on the graph $G'(\Phi)$ of KAYLES. Recall that Bob wants to satisfy all clauses here. After the last move of QSAT', all clauses are satisfied (because of the winning strategy of Bob on QSAT') and then no clause vertex is playable on KAYLES, implying $n$ selected vertices.
Finally, if Alice has a winning strategy on a formula $\Phi$ of QSAT', she can play the corresponding moves on the graph $G'(\Phi)$ of KAYLES. After the last move of QSAT', there is at least one non-satisfied clause (because of the winning strategy of Alice on QSAT') and then there is a playable clause vertex on the optimization variant of KAYLES. Thus, the last player must select a playable clause vertex in the next move, implying $n + 1$ selected vertices. $\square$

# 3 Convexable Graphs

Let us now say that a graph is *convexable* if $gc(G) = n$: Alice can ensure that all vertices are selected in CFG. In this section, we aim at characterizing the convexable graphs.

## 3.1 Convex Elimination Orderings and Preliminaries

A *Convex Elimination Ordering* (CEO) of a graph $G$ is an ordering $(v_1, \cdots, v_n)$ of $V(G)$ such that $G_i = G[v_1, \cdots, v_i]$ induces a convex set for every $1 \le i \le n$. Note that the concept of CEO is closely related to the Convex Set Forming Game CFG, since two players collaborating in the game would manage to eventually select all the vertices of a graph $G$ if and only if $G$ admits a CEO (i.e., it corresponds to the one-player Convex Set Forming Game). Clearly, if a graph does not have a CEO, then $gc(G) < n$.

In the following, we relate Convex Elimination Orderings to Perfect Elimination Orderings (PEO), which are orderings $(v_1, \cdots, v_n)$ of $V(G)$ such that $v_i$ is simplicial in $G_{\ge i} = G[v_i, \cdots, v_i]$ for every $1 \le i \le n$, i.e., $N_{G_{\ge i}}(v_i)$ induces a complete graph. It is well known that a graph is chordal if and only if it has a PEO [20].

**Lemma 3.1.** Let $G$ be a connected graph. An ordering $(v_1, \cdots, v_n)$ of $V(G)$ is a CEO if and only if $(v_n, \cdots, v_1)$ is a PEO.

*Proof.* We begin by proving that any CEO is the reverse of a PEO. By contrapositive, assume that $(v_n, \cdots, v_1)$ is not a PEO and let $j > 1$ be any integer such that $v_j$ is not simplicial in $G[v_{j-1}, \cdots, v_1]$. Then, there exist two non-adjacent vertices in $N(v_j) \cap \{v_{j-1}, \cdots, v_1\}$. These vertices are linked by a shortest path containing $v_j$. Therefore $G[v_1, \cdots, v_{j-1}]$ is not convex, so $(v_1, \cdots, v_n)$ is not a CEO.

Now, assume that $(v_n, \cdots, v_1)$ is a PEO (and so the graph $G$ is chordal). We will show that the ordering $(v_1, \cdots, v_n)$ is a CEO. For contradiction, let $1 < j < n$ be the smallest index such that $(v_1, \cdots, v_j)$ is not convex. Then there is an index $i < j$ and a shortest path $P$ between $v_i$ and $v_j$ with all internal vertices in $\{v_{j+1}, \cdots, v_n\}$. Let $k$ be the largest index $k$ such that $v_k$ belongs to $P$. Then the two neighbors of $v_k$ in the path $P$ are non-adjacent and belong to $\{v_1, \cdots, v_{k-1}\}$, a contradiction. $\square$
This has strong implications on which graphs can admit a CEO. Since admitting a PEO is a characterization of chordal graphs, we can now state the following corollary.

**Corollary 3.2.** Let $G$ be a connected graph. Then, $G$ admits a CEO if and only if $G$ is chordal. Consequently, deciding if a graph admits a CEO is polynomial time solvable. Moreover, if $G$ is not chordal, then $\text{gc}(G)$ cannot be $n$.

By definition of a CEO, it follows that the class of convexable graphs is a subclass of graphs admitting a CEO and so, by Corollary 3.2, a subclass of chordal graphs.

**Corollary 3.3.** Every convexable graph admits a CEO and, consequently, is chordal.

The converse of Corollary 3.3 is not true since the 6-fan $F_6$, depicted in Figure 4, clearly admits a CEO but it is not convexable (Lemma 3.4). Recall that the $k$-fan with $k \ge 1$ is the graph $F_k$ obtained from a path $(v_1, \cdots, v_k)$ with $k$ vertices by adding a universal vertex $v_0$ to it.

<figure><img src="image_6.png" /><figcaption>Figure 4: $F_5$ is convexable, but $F_6$ is not.</figcaption></figure>

**Lemma 3.4.** $F_5$ is convexable, but $F_k$ for $k \ge 6$ is not convexable.

*Proof.* First consider the 5-fan $F_5$. Alice first selects $v_3$. Then Bob can only select $v_0$, $v_2$ or $v_4$. If Bob selects $v_0$, Alice selects $v_2$. If Bob selects $v_2$ or $v_4$, Alice selects $v_0$. After this, note that the extreme points $v_1$ and $v_5$ cannot be selected before their neighbors $v_2$ and $v_4$ has been selected. Thus, all vertices are selected and, consequently, $F_5$ is convexable.

Now consider the 6-fan $F_6$. First suppose that Alice selects $v_0$ on her first turn. Then Bob selects $v_2$ and Alice is forced to choose one vertex in $\{v_1, v_3, v_5, v_6\}$. If Alice selects $v_5$, the vertices $v_3$ and $v_4$ cannot be ever selected. If Alice chooses $v_3$ (resp. $v_6$), Bob selects $v_6$ (resp. $v_3$) and then $v_4$ and $v_5$ cannot be selected during the game. If Alice selects $v_1$, Bob selects $v_5$ and then $v_3$ and $v_4$ will be never selected.

Now suppose that Alice selects $v_3$ in her first move. Then Bob selects $v_2$, Alice is forced to select $v_0$ and thus Bob selects $v_6$, ensuring that $v_4$ and $v_5$ cannot be selected during the game. If Alice selects $v_2$ in her first move, Bob selects $v_3$ and we have the same situation. Now suppose that Alice selects $v_1$ in her first move. Then
Bob selects $v_2$, Alice is forced to select $v_0$ and thus Bob selects $v_5$, ensuring that $v_3$ and $v_4$ cannot be selected during the game. Analogously, by symmetry, if Alice selects $v_4$, $v_5$ or $v_6$ in her first move. Therefore, $F_6$ is not convexable. We can easily extend it to prove that the k-fan $F_k$ is not convexable for $k \ge 6$. $\square$

The following lemma shows that there are convexable interval graphs containing non-convexable interval graphs as induced subgraph. For this, let $F'_7$ be the graph of Figure 5 obtained from the 7-fan $F_7$ by adding one extra universal vertex $v'_0$. Notice that $F_6$ and $F_7$ are induced subgraphs of $F'_7$.

<figure><img src="image_7.png" /><figcaption>Figure 5: Convexable graph $F'_7$ containing $F_7$ (and so $F_6$) as induced subgraphs.</figcaption></figure>

**Lemma 3.5.** *The graph $F'_7$ of Figure 5 is convexable.*

*Proof.* Alice first selects $v_4$. Then Bob can only select $v_0$, $v'_0$, $v_3$ or $v_5$. If Bob selects $v_0$ or $v'_0$, Alice selects $v_3$. If Alice selects $v_3$ or $v_5$, Bob selects $v_0$. After this, Bob is forced to select $v_0$ or $v'_0$, and then Alice selects $v_3$ or $v_5$ in her next move.

Thus, the selected vertices at this point are exactly $v_0, v'_0, v_3, v_4$ and $v_5$. Bob can select neither $v_1$ nor $v_7$. Then he is forced to select $v_2$ or $v_6$, and Alice can ensure that all vertices will be selected. $\square$

**Monophonic convexity.** Regarding the monophonic convexity (based on induced paths, instead of shortest paths), the converse of Corollary 3.3 is true. That is, we say that a set $S$ of vertices of a graph $G$ is *m-convex* if, for every $u, v \in S$, every *w* on an induced *u-v* path also belongs to $S$ [21]. We say that a graph is *m-convexable* if it is convexable in the monophonic convexity. Also let $CFG_m$ be the Convex Set Forming Game in the monophonic convexity. We will use the following lemma regarding chordal graphs. It is known that every minimal separator of a chordal graph is a clique [11].

**Lemma 3.6** ([22]). *If $S$ is a minimal $u-v$ separator of a chordal graph $G$, then the connected components of $G-S$ containing $u$ or $v$ have a vertex that is adjacent to all vertices of $S$.*
**Theorem 3.7.** A graph is $m$-convexable if and only if it is chordal.

*Proof.* It is easy to see that Lemma 3.1 and Corollaries 3.2 and 3.3 also work on the monophonic convexity. Let us now prove the converse. Let $G$ be a connected chordal graph. We prove that, for every $m$-convex set $K \subsetneq V(G)$, there is a vertex $v \in V(G) \setminus K$ such that $K \cup \{v\}$ is $m$-convex. Let $C$ be a connected component of $G-K$ and let $S = N(C) \subseteq K$. Notice that $S$ is a clique, since otherwise there is an induced path between non-adjacent vertices of $S$ whose internal vertices are in $C$, a contradiction because $K$ is $m$-convex. Let $c \in C$ and let $G'$ be the chordal graph obtained from $G$ by adding a new vertex $b$ adjacent to all vertices of $S$. Then $S$ is a minimal $b-c$ separator of $G'$ and, from Lemma 3.6, there is a vertex $v \in C$ adjacent to every vertex of $S$. Therefore $K \cup \{v\}$ is $m$-convex in $G$. Finally, if the chordal graph is not connected, the game proceeds in its components and every vertex of each component is selected during the game. $\square$

The above proof implies:

**Corollary 3.8.** Let $G$ be a chordal graph. Alice wins the normal (resp. misère) variant of the Convex Set Forming Game in the monophonic convexity ($CFG_m$) if and only if the number of vertices is odd (resp. even). Moreover, $gc_m(G) = n$, where $gc_m(G)$ is the game convexity number related to the monophonic convexity.

In what follows, we return to the geodesic convexity and identify subclasses of connected chordal graphs that are convexable.

## 3.2 Ptolemaic graphs

Ptolemaic graphs are defined as distance-hereditary chordal graphs. They correspond exactly to chordal graphs without the 4-fan $F_4$ (also called gem) as an induced subgraph. This class is incomparable with proper interval graphs as there exist proper interval graphs that are not Ptolemaic (the gem), and Ptolemaic graphs that are not proper interval (the claw).

**Theorem 3.9.** Every Ptolemaic graph $G$ is convexable.

*Proof.* Let $G$ be a Ptolemaic graph. We actually prove a stronger result: for every convex set $K \subsetneq V(G)$, there exists a vertex $v \in V(G) \setminus K$ such that $K \cup \{v\}$ is convex (i.e., every convex set $K$ is the prefix of a CEO for $G$). In other words, in the Convex Set Forming game (CFG), Alice can always find a vertex to be selected to extend the convex set of selected vertices and, whatever be her choice, Bob will have an available vertex to select next.

Let $C$ be a connected component of $G-K$ and let $S = N(C) \subseteq K$. If $S = \{a\}$, then any neighbour $v$ of $a$ in $C$ is such that $K \cup \{v\}$ is convex. Hence, let us assume
that $|S| > 1$. Let $a$ and $b$ be two vertices in $S$. First, let us assume that $a$ and $b$ are not adjacent and consider such $a$ and $b$ as close as possible (while not adjacent). Let $P$ be a shortest $a-b$ path and $Q$ be an induced $a-b$ path whose internal vertices are in $C$. Since $K$ is convex, then $V(P) \subseteq K$ and $Q$ is longer than $P$. If all internal vertices of $P$ are in $K \setminus S$, then $P \cup Q$ is an induced cycle of size at least 5, contradicting the fact that $G$ is chordal. Then, by the minimality of the choice of $a$ and $b$, $V(P) \subseteq S$ and consequently (by minimality of the distance between $a$ and $b$) $P = (a, x, b)$ has exactly three vertices for some $x \in S$. Since $G$ is chordal, all internal vertices of $Q$ are adjacent to $x$. Therefore, $Q \cup \{x\}$ contains a 4-fan (gem) as induced subgraph, a contradiction.

Thus $a$ and $b$ are adjacent and, consequently, $S$ is a clique. Let $c \in C$ and let $G'$ be the chordal graph obtained from $G$ by adding a new vertex $b$ adjacent to all vertices of $S$. Then $S$ is a minimal $b-c$ separator of $G'$ and, from Lemma 3.6, there is a vertex $v \in C$ adjacent to every vertex of $S$. Therefore $K \cup \{v\}$ is convex in $G$.

Finally, if the Ptolemaic graph is not connected, the game proceeds in its components and every vertex of each component is selected during the game. □

The above proof implies:

**Corollary 3.10.** Let $G$ be a Ptolemaic graph. Alice wins the normal (resp. misère) variant of the Convex Set Forming Game (CFG) if and only if the number of vertices is odd (resp. even). Moreover, $\text{gc}(G) = n$.

We show in the next lemma that the above result cannot be extended to $F_5$-free chordal graphs. Figure 6 shows a non-convexable chordal graph that contains no induced $F_5$.

<figure><img src="image_8.png" /><figcaption>Figure 6: Non-convexable graph containing induced 4-fans but no induced 5-fan.</figcaption></figure>
**Lemma 3.11.** *There are connected chordal graphs without induced 5-fan that are not convexable.*

*Proof.* First consider the game in the graph $H$, with vertices $V = \{0, \dots, 6\}$, shown inside the dotted circle of Figure 6. If Bob starts by selecting the vertex 0 of $H$, then Alice has to answer 1 (or symmetrically 2) and Bob can select 3 (resp., 6) and then none of 2 or 4 (resp., 1 or 5) can be selected anymore.

Let $G$ be obtained from three copies $X, Y$ and $Z$ of $H$ by adding a new vertex $r$ adjacent to each of the vertices 0 of the copies of $H$ (Figure 6). It can be checked that $G$ is connected chordal and $F_5$-free.

Let us assume that Alice does not play first in $X$. Let us consider the first step when $r$ is selected. If it is by Alice, then Bob selects the vertex 0 of $Y$. Otherwise, at his next turn, Bob selects the vertex 0 of the copy $Y$ or $Z$ that has not been played yet (say it is $Y$). Then, by the parity of the number of the vertices, Bob may ensure that Alice is the next one to play in $Y$. Following the reasoning as above, all vertices of $Y$ cannot be selected. Hence, $G$ is not convexable. □

In another direction, we know several convexable graphs that are not Ptolemaic. For example, the 5-fan $F_5$ (see Lemma 3.4), which belongs to the class of Interval graphs, considered in the following section.

## 3.3 Interval graphs

An *interval graph* is the intersection graph of real intervals. In this section, we are interested in CFG-OPT in interval graphs: the optimization version of the geodesic Convex Set Forming Game.

A *unit interval graph* $G$ is the intersection graph of a set of real intervals of unit length. Precisely, given a set $V = \{[h_i, h_i + 1] : i = 1, \dots, n\}$ of unit-length real intervals ($h_i \in \mathbb{R}$ for $i = 1, \dots, n$), its intersection graph $G$ with vertices $v_1, \dots, v_n$ is the graph such that $v_i$ and $v_j$ are adjacent if and only if $[h_i, h_i + 1]$ and $[h_j, h_j + 1]$ have non-empty intersection. Note that we may assume that all $h_i$'s are distinct, i.e., $G$ is also a *proper interval graph* (no interval is contained in another). Actually, a graph is a proper interval graph if and only if it is a unit interval graph [4]. Note that recognizing a unit interval graph and obtaining an interval representation of it can be done in linear time [9].

Note that any $k$-fan is an interval graph. However, it is a unit interval graph if and only if $k \le 4$. In particular, no unit interval graph contains an induced 5-fan $F_5$. From now on, let $[a, b]$ with $a < b \in \mathbb{N}$ denote the set $\{a, a+1, \dots, b-1, b\}$. Contrary to the proof of Theorem 3.9 on Ptolemaic graphs, which is short, the proof of the theorem below is more complicated, since it cannot use chordal graph
properties, such as Lemma 3.6, nor distance-hereditary graph properties, such as
not containing the 4-fan $F_4$, which is a unit interval graph.

**Theorem 3.12.** Every connected unit interval graph is convexable.

*Proof.* Let $G$ be a connected unit interval graph with vertex-set ordered $(v_1, \cdots, v_n)$
such that $h_1 < h_2 < \cdots < h_n$. We will describe a strategy for Alice ensuring that
all vertices are eventually selected.

The idea is to define the notion of *extendable* convex set and to show that, if the
set of selected vertices (after Alice's turn) is extendable, then after a finite number
of steps, Alice can reach a larger extendable set (after her turn). Moreover, once $v_1$
and $v_n$ belong to the set of selected vertices that is extendable, then all remaining
vertices can be added in any order. The first move of Alice is always to select the
vertex $v_1$ which (as it can be seen below) is an extendable set. So the proof below is
by induction on the size of the extendable set of selected vertices after some moves
of Alice.

We say that a convex set $S$ is *extendable* if there exists $m \ge 1$ and $m$ intervals
$R = [l_1 = 1, r_1] \cup \cdots \cup [l_m, r_m]$ (with $l_j \le r_j < l_{j+1} - 1$ for any $1 \le j < m$ and
$l_m \le r_m \le n$), and $I_j \subseteq \{v_\ell : \ell \in [r_{j-1}+1, l_j-1]\}$ for any $1 < j \le m$ such that:

$$
1. S = \{v_i\}_{i \in R} \cup \bigcup_{1 < j \le m} I_j;
$$

2. $\{v_\ell : \ell \in [r_{j-1}, l_j]\}$ induces a complete graph for any $1 < j \le m$, and

3. $N(\{v_{r_{j+1}}, \dots, v_n\}) \cap \{v_1, \dots, v_{r_j}\} \subseteq \{v_{l_j}, \dots, v_{r_j}\} \subseteq S$ for every $1 \le j \le m$.

**Claim 3.13.** Let $S$ be extendable and let $S'$ be a convex set with $S \subseteq S'$. Then, for every $i \le r_m$, $S' \cup \{v_i\}$ is convex. Moreover, if $S'$ is extendable, then $S' \cup \{v_i\}$ is extendable.

*Proof of Claim.* If $v_i \in S$, the result holds directly. So, assume that $v_i \notin S$.
Then there is a unique $1 < j \le m$ such that $v_i \in \{v_{r_{j-1}+1}, \cdots, v_{l_{j-1}}\} \setminus I_j$. For
contradiction, suppose that $S' \cup \{v_i\}$ is not convex. Therefore, there exists a shortest
path $P = (u_0 = v_i, u_1, \cdots, u_p = w)$ from $v_i$ to some vertex $w$ in $S' \cap \{v_1, \cdots, v_{r_{j-1}}\}$
(the case in $S' \cap \{v_{l_j}, \cdots, v_n\}$ is symmetric) with $u_1 \notin S'$. Then, by Property
3, $u_1 \in \{v_{r_{j-1}+1}, \cdots, v_{l_{j-1}}\} \setminus I_j$. By Property 2 and the fact that $G$ is a
unit interval graph, then $P' = (v_{l_j}, u_1, \cdots, u_p = w)$ is also a shortest path. Indeed, if
$(v_{l_j}, u'_1, u'_2, \cdots, w)$ were a path shorter than $P'$ from $v_{l_j}$ to $w$, then, because $G$ is a
unit interval graph, $(v_i, u'_1, u'_2, \cdots, w)$ would also be a path contradicting the fact
that $P$ is a shortest $v_i-w$ path. This contradicts the fact that $S'$ is convex.

Then, $S' \cup \{v_i\}$ is extendable by just adding $v_i$ to $I_j$. ♢
In particular, the previous claim implies that if, at some step, the set of selected vertices is extendable and contains $v_1$ and $v_n$ (i.e., $r_m = v_n$), then Alice eventually ensures that all vertices will be selected.

**Claim 3.14.** If $S$ is extendable, then $S \cup \{v_{r_m+1}\}$ is extendable.

*Proof of Claim.* Since each interval in the interval representation of $G$ has unit length, $v_{r_m+1}$ is adjacent to every vertex in $N(\{v_{r_m+1}, \cdots, v_n\}) \cap \{v_1, \cdots, v_{r_m}\}$. Therefore, every shortest path from $v_{r_m+1}$ to a vertex in $S$ has its first vertex in $N(\{v_{r_m+1}, \cdots, v_n\}) \cap \{v_1, \cdots, v_{r_m}\} \subseteq S$. Hence, $S \cup \{v_{r_m+1}\}$ is convex.

To show that it is extendable, it is sufficient to replace $r_m$ by $r_m+1$ and all three properties are satisfied for $S \cup \{v_{r_m+1}\}$ since $S$ is extendable. $\diamond$

Now, let us assume (by induction on $r_m = i \ge 1$) that, after Alice's turn, the set $S$ of selected vertices is extendable (which is the case after the first move of Alice who starts by selecting $v_1$). By the previous claims, if Bob selects a vertex $v_j$ with $j \le i + 1$ and Alice selects $v_{i+1}$ (if $j \le i$) or $v_{i+2}$ (if $j = i + 1$), then the induction hypothesis is satisfied for a larger extendable set of selected vertices.

Hence, let us assume that Bob selects $v_j$ with $j > i + 1$ (so $S \cup \{v_j\}$ is convex).

**Claim 3.15.** If $j = n$ or $v_j$ is a cut-vertex (separating the set $\{v_1, \cdots, v_{j-1}\}$ from $\{v_{j+1}, \cdots, v_n\}$), then the set of selected vertices is extendable.

*Proof of Claim.* By setting $j = r_{m+1} = l_{m+1}$ and adding $v_j$ to $R$, Properties 1 and 3 are satisfied. Since $S \cup \{v_j\}$ is convex, it induces a connected subgraph and so $v_j$ must be adjacent to $v_{r_m} = v_i$. Therefore, because $G$ is a unit interval graph, $\{v_i, v_{i+1}, \cdots, v_j\}$ induces a complete graph and Property 2 also holds. $\diamond$

So, if $j = n$, by Claim 3.13, all vertices will eventually be selected. Moreover, if $v_j$ is a cut-vertex, then, by selecting $v_{j+1}$, Alice leads to a larger extendable set by Claim 3.14. Hence, we may assume that $j < n$ and $v_j$ is not a cut vertex.

Note that, since $G$ is a connected unit interval graph, then $\{v_i v_j\} \in E$. Let $k > j$ be the smallest integer such that $\{v_j v_k\} \notin E$ (if $k$ does not exist, let us set $k = n + 1$). Note that $k > j + 1$ since $G$ is connected. Note that, because $G$ is an interval graph, $\{v_i, \cdots, v_j\}$ and $\{v_j, \cdots, v_{k-1}\}$ induce complete graphs.

Let $i < h < j$ be the smallest integer such that $v_h$ is adjacent to some vertex $v_p$ with $p > j$ ($h$ exists because $v_j$ is not a cut-vertex).

**Claim 3.16.** $S \cup \{v_j, v_h\}$ is convex.

*Proof of Claim.* By contradiction, assume that there is a shortest path $(u_0 = v_h, u_1, \cdots, v_p)$ from $v_h$ to $v_p \in S$ with $u_1 \notin S \cup \{v_j, v_h\}$. Then, $(v_j, u_1, \cdots, v_p)$ is also a shortest path, contradicting that $S \cup \{v_j\}$ is convex. $\diamond$
Then, Alice can select $v_h$ and does it.

**Claim 3.17.** Any subset of $\{v_1, \cdots, v_j\}$ containing $S \cup \{v_h, v_j\}$ is convex.

*Proof of Claim.* For the vertices $v_t \notin S \cup \{v_h, v_j\}$ with $t < i$, it follows from Claim 3.13. For the vertices $x \in \{v_i, \cdots, v_j\}$, it comes from the fact that $\{v_i, \cdots, v_j\}$ induces a clique. Indeed, if adding $x$ would not induce a convex set, then adding $v_j$ would not have induced a convex set (the proof is similar to the one of Claim 3.16).
$\diamond$

**Claim 3.18.** Let $S' \subseteq \{v_1, \cdots, v_j\}$ be a convex super-set of $S \cup \{v_h, v_j\}$ such that $\{v_h, \cdots, v_j\} \setminus S' \neq \emptyset$. Then, $S' \cup \{v_t\}$ with $t > j$ is not convex.

*Proof of Claim.* Let $v_k \in \{v_h, \cdots, v_j\} \setminus S'$. Let $P = (u_0 = v_t, u_1, \cdots, u_p)$ be any shortest path from $v_t$ to a vertex $u_p \in S'$. Note that $u_1 \in \{u_h, \cdots, v_j\}$ by definition of $h$ and because $S' \cup \{v_t\}$ must be convex. If $u_2$ is adjacent to $v_k$, then $(u_0 = v_t, v_k, \cdots, u_p)$ is also a shortest path showing that $S' \cup \{v_t\}$ is not convex. Hence, $u_2$ is not a neighbour of $v_k$, but then $u_2$ is not adjacent to $v_j$ either ($G$ being a unit interval graph). Therefore $(v_j, v_k, u_2, \cdots, u_p)$ is also a shortest path and so $S'$ is not convex, a contradiction.
$\diamond$

**Claim 3.19.** Let $S' \subseteq \{v_1, \cdots, v_j\}$ be a convex super-set of $S \cup \{v_h, \cdots, v_j\}$. Then, $S'$ is extendable.

*Proof of Claim.* By construction, Property 1 of the definition of a extendable set is satisfied by $S'$. Let us set $h = l_{m+1}$ and $j = l_{m+1}$. Properties 2 and 3 are satisfied for every $j' \le m$ because $S$ is extendable and by Claim 3.13 for the vertices $v_{i'}$ with $i' \le r_m = i$. Property 3 for $m+1$ is satisfied by definition of $h$. Finally, Property 2 for $m+1$ is satisfied, since $v_j$ is adjacent to $v_{r_m}$ and $G$ is a unit interval graph.
$\diamond$

From Claims 3.17 and 3.18, it follows that the vertices in $\{v_h, \cdots, v_j\}$ must (and can) be selected before any vertex $v_p$ can be selected with $p > j$. Moreover, once the vertices of $\{v_h, \cdots, v_j\}$ are selected, we reach a larger extendable subset by Claim 3.19. If Alice was the one to complete that, then the induction hypothesis (with a larger extendable set) is reached. Otherwise, she can select $v_{j+1}$ by Claim 3.14 and, again, we are done.
$\square$

**Remark.** The converse of the Theorem 3.12 is not true since the claw (star with three leaves) is convexable, but is not a proper interval graph. More generally, we have seen that Ptolemaic graphs are convexable and many of them are not proper interval graphs. In particular:

**Corollary 3.20.** Every tree and, more generally, every block graph (every two-connected component is a clique) is convexable.
# 4 Largest CEO set in Outerplanar graphs

Given a graph $G$, a set $S \subseteq V(G)$ is called a CEO set if there exists an ordering $(v_1, \cdots, v_{|S|})$ of $S$ such that, for every $1 \le i \le |S|$, $G[v_1, \cdots, v_i]$ induces a convex subgraph of $G$. We say that $v_1$ (resp., $v_1$ and $v_2$) is (are) the starting vertex (vertices) of $S$. Here, we show that computing a largest CEO set of outerplanar graph can be done in polynomial time. This problem can be seen as the optimization version of the Convex Set Forming Game CFG when Bob wants to help Alice.

A graph is outerplanar if it admits a planar embedding (a planar drawing without crossing edges) such that all vertices lie on the outerface. An important property that will be used is that every internal face of an outerplanar graph corresponds to an isometric cycle.

A graph is outerplanar if it admits a planar embedding (a planar drawing without crossing edges) such that all vertices lie on the outerface. An important property that will be used is that every internal face of an outerplanar graph corresponds to an isometric cycle.

A tree-decomposition of a graph $G = (V, E)$ consists of a pair $(T, \mathcal{X})$ where $T$ is a tree and $\mathcal{X} = (X_t)_{t \in V(T)}$ is a family of subsets (called bags) of vertices of $G$ indexed by the nodes of $T$ such that:

* $\bigcup_{t \in V(T)} X_t = V$;

* for every $\{u, v\} \in E$, there exists $t \in V(T)$ with $u, v \in X_t$, and

* for every $u \in V$, $\{t \in V(T) \mid u \in X_t\}$ induces a subtree of $T$.

It can easily be shown by induction on the number of faces that any outerplanar graph $G = (V, E)$ admits a tree-decomposition $(T, \mathcal{X})$ where $T$ is a tree rooted in some node $r \in V(T)$ and every bag either induces a tree (called a *tree-bag*) or a face (called a *face-bag*) such that, for every tree-bag $X_t \in \mathcal{X}$, each child $t'$ (and also the parent) of $t$ corresponds to a face-bag and $X_t \cap X_{t'}$ is a single vertex and, for every face-bag $X_t \in \mathcal{X}$ with a face-bag child $X_{t'}$, $X_t$ and $X_{t'}$ intersect in a single vertex or in an edge.

For every node $t \in V(T)$ of $T$ (rooted at $r$), let $T_t$ be the subtree of $T$ rooted in $t$ and let $G_t = G[\bigcup_{t' \in T_t} X_{t'}]$.

We describe a recursive algorithm that takes a node $t \in V(T)$ as input (let $X^t = X_t \cap X_{t'}$ with $t'$ the parent of $t$, and $X^t = \emptyset$ if $t = r$) and computes $(S_{opt}^t, S_x^t, S_y^t, S_{xy}^t)$ satisfying the following:

* $S_{opt}^t$ is a largest CEO set in $G_t$;

* if $X^t = \{x\}$, $S_x^t$ is a CEO set in $G_t$, such that $x \in S_x^t$ and $S_x^t$ is largest among such CEO sets; and $S_y^t = S_{xy}^t = \emptyset$; Moreover, $x$ is a starting vertex of $S_x^t$.

* if $X^t = \{x, y\}$ (in which case $\{x, y\} \in E(G)$):
- $S_x^t$ is a CEO set in $G_t$, such that $x \in S_x^t$ and $y \notin S_x^t$ and $S_x^t$ is largest among such CEO sets; Moreover, $x$ is a starting vertex of $S_x^t$.

- $S_y^t$ is a CEO set in $G_t$, such that $y \in S_y^t$ and $x \notin S_y^t$ and $S_y^t$ is largest among such CEO sets; Moreover, $y$ is a starting vertex of $S_y^t$.

- $S_{xy}^t$ is a CEO set in $G_t$, such that $x, y \in S_{xy}^t$ and $S_{xy}^t$ is largest among such CEO sets; Moreover, $x$ and $y$ are starting vertices of $S_{xy}^t$.

The algorithm proceeds as follows.

* If $X_t$ is a leaf-bag (i.e., $t$ is a leaf of $T$), let $X^t = \{x\}$ or $X^t = \{x, y\}$ (where $X^t = X_t \cap X_{t'}$ with $t' \neq t$ if $t = r$):

- if $X_t$ is a tree-bag, then $S_{opt} = S_x = X_t$ and $S_y^t = S_{xy}^t = \emptyset$.

- if $X_t$ is a face-bag, let $(v_0, v_1, \dots, v_p)$ be the corresponding face with, if $X_t \neq \emptyset$, $v_0 = x$ and (if $X^t = \{x, y\}$) $v_1 = y$. Then, $S_{opt}^t = S_x^t = \{v_0, v_p, v_{p-1}, \dots, v_{\lfloor \frac{p}{2} \rfloor+1}\}$, $S_y^t = \{v_1, v_2, \dots, v_{\lfloor \frac{p}{2} \rfloor+1}\}$, $S_{xy}^t = \{v_0, v_1, \dots, v_{\lfloor \frac{p}{2} \rfloor}\}$ (and $S_y^t = S_{xy}^t = \emptyset$ if $y$ is not defined).

* Now, let $t \in V(T)$ with $d \ge 1$ children $t_1, \dots, t_d$ and assume that, for every $1 \le i \le d$, $(S_{opt}^{t_i}, S_{x_i}^{t_i}, S_{y_i}^{t_i}, S_{x_i y_i}^{t_i})$ has been computed recursively (where $X^{t_i} = \{x_i\}$ or $X^{t_i} = \{x_i, y_i\}$).

- if $X_t$ is a tree-bag, then let $S_x^t = X_t \cup \bigcup_{1 \le i \le d} S_{x_i}^{t_i}$. Let $1 \le j \le d$ be such that $S_{opt}^{t_j}$ is a largest set among the sets $S_{opt}^{t_i}$, $1 \le i \le d$. If $|S_x^t| \ge |S_{opt}^{t_j}|$, then $S_{opt}^t = S_x^t$ and $S_{opt}^t = S_{opt}^{t_j}$ otherwise.

- if $X_t$ is a face-bag, let $F = (v_0, v_1, \dots, v_p)$ be the corresponding face. Set $\mathcal{Y} = \emptyset$.

* For every $a, b \in V(F)$ (except if the distance between $a$ and $b$ equals $\frac{p+1}{2}$ and $p$ is odd), let $P_{ab}$ be the (unique) shortest $a-b$ path ($P_{ab}$ lies in $F$). Set $Y_{ab} = P_{ab}$ (in the particular case when $F$ is a triangle, then $P_{ab} = V(F)$). For every $1 \le i \le d$, if $X^{t_i} \cap P_{ab} = \{x_i\}$ then add $S_{x_i}^{t_i}$ to $Y_{ab}$; if $X^{t_i} \cap P_{ab} = \{y_i\}$ then add $S_{y_i}^{t_i}$ to $Y_{ab}$; and if $X^{t_i} \cap P_{ab} = \{x_i, y_i\}$ then add $S_{x_i, y_i}^{t_i}$ to $Y_{ab}$. Add $Y_{ab}$ to $\mathcal{Y}$. (note that, if $F$ is a triangle, $|\mathcal{Y}| = 1$).

* Let $S_x^t$ be any largest set in $\mathcal{Y}$ that contains $x$ (but not $y$ if $y$ is defined); let $S_y^t$ be any largest set in $\mathcal{Y}$ that contains $y$ but not $x$ and let $S_{xy}^t$ be any largest set in $\mathcal{Y}$ that contains both $x$ and $y$.

* Let $1 \le j \le d$ be such that $S_{opt}^{t_j}$ is a largest set among the sets $S_{opt}^{t_i}$, $1 \le i \le d$. If $S_{opt}^{t_j}$ is largest than any set in $\mathcal{Y}$, then $S_{opt}^t = S_{opt}^{t_j}$; otherwise let $S_{opt}^t$ be any largest set in $\mathcal{Y}$.
**Theorem 4.1.** Let $G$ be any $n$-node outerplanar graph. The above algorithm computes a largest CEO-set of $G$ in time $O(n^3)$.

*Proof.* Let $(T, \mathcal{X})$ be a tree-decomposition of $G$ as described above (it can be computed in linear-time). In particular, $T$ is rooted at some node $r$.

Since the number of bags of the tree-decomposition is $O(n)$ and that the computation time, for each bag, is dominated by the fact of considering each pair of vertices (for a face-bag), the time complexity is $O(n^3)$.

We show by induction that, for every bag $X_t$, the computed sets $(S_{opt}^t, S_x^t, S_y^t, S_{xy}^t)$ satisfy the desired properties. Then, $S_{opt}^r$ will be the desired solution.

The result clearly holds for any leaf bag. So let $t \in V(T)$ with $d \ge 1$ children $(t_1, \cdots, t_d)$ and assume, by induction, that $(S_{opt}^{t_i}, S_{x_i}^{t_i}, S_{y_i}^{t_i}, S_{x_i y_i}^{t_i})$ satisfy the desired properties for every $1 \le i \le d$.

* Let us first consider the case when $X_t$ is a tree-bag. Recall that, for every $1 \le i \le d$, $X_t^{t_i} = \{x_i\}$ where $x_i$ is a cut vertex of $G$. Let $S$ be a largest CEO of $G_t$ intersecting $X_t$.

**Claim 4.2.** $X_t \subseteq S$.

*Proof of Claim.* Otherwise, let $v \in (X_t \setminus S) \cap N(S)$, then $S \cup \{v\}$ is convex and so it is a larger CEO (by placing $v$ at the end of the ordering) contradicting the maximality of $S$. $\diamond$

**Claim 4.3.** For every $1 \le i \le d$, $S \cap V(G_{t_i})$ is a largest CEO set of $G_{t_i}$ among those sets that contains $x_i$.

*Proof of Claim.* For purpose of contradiction, assume that this is not true for some $1 \le i \le d$. Let $(v_1, \cdots, v_{j-1}, v_j = x_i, v_{j+1}, \cdots, v_h)$ be the CEO (induced by the one of $S$) for the set $S \setminus (V(G_{t_i}) \setminus \{x_i\})$ and let $O_i$ be the CEO of a largest CEO-set of $G_{t_i}$ containing $x_i$. Note that $O_i$ can be chosen such that it start from $x_i$ (since by induction, $S_{x_i}^{t_i}$ is a largest CEO-set of $G_{t_i}$ containing $x_i$ and it can start from $x_i$). Then, Let $(v_1, \cdots, v_{j-1}) \odot O_i \odot (v_{j+1}, \cdots, v_h)$ is a CEO for $G_t$, largest than $S$, a contradiction. $\diamond$

Now, let $\{x\} = X^t$ (unless $t=r$) and let $\mathcal{O}$ be a CEO of $X_t$ starting in $x$ (this clearly exists since $X_t$ is a tree) and, for every $1 \le i \le d$, let $O_i$ be the ordering of $S_{x_i}^{t_i}$. Then, $\mathcal{O} \odot \mathcal{O}_1 \odot \cdots \mathcal{O}_d$ is a maximum CEO set of $G_t$ containing $x$. And $x$ is a starting vertex.

Hence, $S_x^t$ satisfies the desired properties. The fact that $S_{opt}^t$ also satisfies the desired properties trivially holds (since by induction, all $S_{opt}^{t_i}$ are maximum in $G_{t_i}$ and, if they do not intersect $X_t$, they are inclusion maximal in $G_t$).
• Second, assume that $X_t$ is a face-bag and let $F = (v_0, \cdots, v_p)$ be the corresponding face. Recall that, for every $1 \le i \le d$, $X^{t_i} = \{x_i\}$ where $x_i$ is a cut vertex of $G$ or $X^{t_i} = \{x_i, y_i\}$ where $\{x_i, y_i\}$ is an edge separator. Let $S$ be a inclusion maximal CEO of $G_t$ intersecting $X_t$.

**Claim 4.4.** If $X_t$ is a triangle, i.e., if $p=2$, then $X_t \subseteq S$.

*Proof of Claim.* Otherwise, let $v \in (X_t \setminus S) \cap N(S)$, then $S \cup \{v\}$ is convex and so it is a larger CEO (by placing $v$ at the end of the ordering) contradicting the maximality of $S$. $\diamond$

**Claim 4.5.** If $p > 2$, then there exist $a, b \in V(F)$ (and with the distance between $a$ and $b$ is $< \frac{p+1}{2}$ if $p$ is odd) such that $S \cap X_t = P_{ab}$ where $P_{ab}$ is the unique shortest path between $a$ and $b$.

*Proof of Claim.* First, $S \cap X_t$ must be connected by convexity of $S$. Second, let $O = (u_1, \cdots, u_{|S|})$ be a CEO of $S$ and let $v_j$ be the last vertex of $S \cap X_t$ appearing in $O$. If $S \cap X_t = F$, then $(v_1, \cdots, v_{j-1})$ is not convex (because $p > 2$), a contradiction. Hence, $S \cap X_t$ must be a path $P_{ab}$ between two vertices $a, b \in F$ and $P_{ab}$ must be the unique shortest path between $a$ and $b$ (recall that $F$ induces an isometric cycle in $G$) since otherwise, $(v_1, \cdots, v_j)$ would not be convex. $\diamond$

**Claim 4.6.** For every $1 \le i \le d$, let $Y_i = X_t \cap S \subseteq X^{t_i}$. Then, $S \cap V(G_{t_i})$ is a largest CEO set of $G_{t_i}$ among those CEO sets $S'$ of $G_{t_i}$ such that $S' \cap X^{t_i} = Y_i$.

*Proof of Claim.* The proof is similar to the one of Claim 4.3. $\diamond$

The end of the proof of this case is a direct adaptation of the end of the proof of the previous case (when $X_t$ is a tree-bag). $\square$

# 5 Conclusions and Open Problems

In this paper, we have introduced a new two player game related to (geodesic) convexity, the Convex Set Forming Game CFG, and show that determining its outcome is PSPACE-complete in general. It would be interesting to determine a large class of graphs in which the problem can be solved in polynomial time.

Regarding the optimization variant of the CFG, the class of convexable graphs seems particularly interesting. We have exhibited several classes of convexable graphs and the situation is summarised in the next proposition, and illustrated in Figure 7.
<figure><img src="image_9.png" /><figcaption>Figure 7: Partial characterization of Convexable graphs: a visual summary. All graphs in the classes depicted in “dark green” (Proper Interval $\cup$ Ptolemaic) are convexable. Graphs depicted in the “light green” areas are examples of convexable graphs (to illustrate that these area are not empty). Graphs depicted in the “white” areas are examples of non convexable graphs. The question mark indicates that we do not know whether there exist Interval $F_5$-free not convexable graphs.</figcaption></figure>

**Proposition 5.1.** The following inclusions hold:

* Ptolemaic $\subsetneq$ Convexable $\subsetneq$ Chordal,

* Connected Proper interval $\subsetneq$ Convexable $\subsetneq$ Chordal,
• Connected Interval \ Convexable ≠  , and

• (Chordal \ Interval) ∩ Convexable ≠  .

Proof. The first inclusion is the Theorem 3.9 and it is proper because $F_5$ is convex-
able. The second inclusion is the Corollary 3.3 and it is proper from Lemma 3.4.
The third inclusion comes from Theorem 3.12. The fact that it is a proper inclusion
comes from Corollary 3.20.
□

We were unfortunately unable to fully characterize the class of convexable graphs.
For instance,

**Question 1.** *Are there interval $F_5$-free connected graphs that are not convexable?*

Actually, the case of fans is intriguing. For instance (see Figure 7), we have
examples with 2 copies of $F_5$ as induced subgraphs that are convexable and some
examples that are not: take two copies of $F_5$. In one case identify their vertices $v_1$,
and in the second case make their vertices $v_1$ adjacent. This seems to relate (but
not only) with the “parity of the distance between the 2 copies”.

**Question 2.** *What is the complexity of deciding whether a graph is convexable?*

On our way to characterize convexable graphs, we defined the notion of sets of
vertices admitting a CEO.

**Question 3.** Given a graph $G$ and $k \in \mathbb{N}$, what is the complexity of deciding whether $G = (V, E)$ contains a subset $S \subseteq V$, $|S| \ge k$, such that $S$ admits a CEO?

**References**

[1] Samuel N. Araújo, João Marcos Brito, Raquel Folz, Rosiane de Freitas, and Rudini Sampaio. Graph convexity impartial games: Complexity and winning strategies. *Theoretical Computer Science*, 998:114534, 2024.

[2] Bret J. Benesh, Dana C. Ernst, Marie Meyer, Sarah Salmon, and Nandor Sieben. Impartial geodetic building games on graphs, 2023.

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

[4] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. *Graph Classes: A Survey*. Society for Industrial and Applied Mathematics, 1999.
[5] Fred Buckley and Frank Harary. Closed geodetic games for graphs. *Congres-sus Numerantium*, 47:131–138, 1985. Proceedings of the 16th Southeastern Conference on Combinatorics, Graph Theory and Computing.

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

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

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

[9] Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, and Alan P. Sprague. Simple linear time recognition of unit interval graphs. *Inf. Process. Lett.*, 55(2):99–104, 1995.

[10] Antoine Dailly, Harmender Gahlawat, and Zin Mar Myint. The closed geodetic game: algorithms and strategies, 2024.

[11] G. A. Dirac. On rigid circuit graphs. *Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg*, 25:71–76, 1961.

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

[13] H. E. Dudeney. *The Canterbury Puzzles and other curious problems*. E. P. Dutton, New York, 1907.

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

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

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

[17] Frank Harary and Juhani Nieminen. Convexity in graphs. *Journal of Differential Geometry*, 16(1):185–190, 1981.
[18] T.W. Haynes, M.A. Henning, and C. Tiller. Geodetic achievement and avoidance games for graphs. *Quaestiones Mathematicae*, 26:389–397, 2003.

[19] R. Hearn and E. Demaine. *Games, Puzzles and Computation*. A. K. Peters Ltd, 2009.

[20] Pinar Heggernes. Minimal triangulations of graphs: A survey. *Discrete Mathematics*, 306(3):297–317, 2006.

[21] Robert E. Jamison. A perspective on abstract convexity: classifying alignments by varieties. *Convexity and Related Combinatorial Geometry*, 1982.

[22] P.Sreenivasa Kumar and C.E.Veni Madhavan. Minimal vertex separators of chordal graphs. *Discrete Applied Mathematics*, 89(1):155–168, 1998.

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

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

[25] E. Zermelo. Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In *Proc. 5th Int. Congress of Mathematicians*, pages 501–504, 1913.