The Closed Hull Game and the Closed Interval Game

Due to Theorem 4, 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,\mathrm{\dots },c_{2n}\}$.

Let us construct an instance $(G,\mathrm{\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},\mathrm{\cdots },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 $\mathrm{\ell }=8n^2+4n+k$.

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$. $\mathrm{⊲}$

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

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

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

Since $1\le k\le 4n$, we have that . 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},\text{Bob}\}$ wins CIG^∗ on $(H,k,C)$. Let $Q$ be the opponent of $P$. We say that a vertex $v$ of a gadget $F_i$ is good if either it belongs to $A_i$ and $P$ is Alice or it belongs to $B_i$ and $P$ is Bob. Otherwise, we say that $v$ is bad.

Consider the following strategy for $P$ on CIG on the graph $G$ with integer $\mathrm{\ell }$. 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).

1. (i₁)

   If the player $Q$ selects a bad vertex of a $P$’s gadget $F_i$ (no bad vertex of $F_i$ was selected before and there is exactly one good vertex selected in $F_i$), then $P$ selects other good vertex of $F_i$, making $F_i$ a $P$’s gadget again;

2. (i₂)

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

3. (i₃)

   If $P$ is Bob and $Q$ (Alice) selects a bad vertex ($A_i$) of a gadget $F_i$ in which no vertex was selected before, then $P$ (Bob) selects a good vertex ($B_i$) of $F_i$;

4. (i₄)

   Otherwise, if there is a gadget $F_i$ without selected vertices, then $P$ selects a good vertex of $F_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:

1. (ii₁)

   If the player $Q$ selects either a vertex of $H$, or a good vertex of a $P$’s gadget $F_i$, or a bad vertex of 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^∗);

2. (ii₂)

   If the player $Q$ selects a bad vertex of a $P$’s gadget $F_i$ (with exactly one good vertex selected), then $P$ selects other good vertex of $F_i$, making $F_i$ a $P$’s gadget again;

3. (ii₃)

   If the player $Q$ selects a good vertex of a $Q$’s gadget $F_i$, then $P$ selects other good vertex of $F_i$, making it 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 $\mathrm{\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 $\mathrm{\ell }$ selected vertices in $G$. $◀$

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^{\prime }=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^{\prime }\subseteq V(G)$ of $H$ with $|S^{\prime }|\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 $(G,k)$ be an instance of the classical problem of Minimum Dominating Set, which is NP-complete and not approximable up to $\log n$ factor [18]. Let $V=V(G)=\{v_1,\mathrm{\cdots },v_n\}$.

Let $G^{\prime }$ be obtained from $G$ as follows. Let $V_S=\{v_1^S,\mathrm{\cdots },v_n^S\}$ be a stable set of order $n$. Let $C$ be a clique on $n^2$ vertices: $\{v_1^1,\mathrm{\cdots },v_n^1,v_1^2,\mathrm{\cdots },v_n^2,\mathrm{\cdots },v_1^n,\mathrm{\cdots },v_n^n\}$. For any $1\le i,j\le n$, make $v_i^S$ adjacent to $v_1^j,\mathrm{\cdots },v_n^j$ if and only if $i=j$ or $\{v_i,v_j\}\in E(G)$. Clearly $G^{\prime }$ is a split graph. Note that, for any $1\le j\le n$, $v_1^j,\mathrm{\cdots },v_n^j$ are true twins in $G^{\prime }$ (vertices with same closed neighborhood). Also note that the vertices of $V_S$ are simplicial in $G^{\prime }$ (and so belong to any interval/hull set) and that the (unique) minimum hull set (resp., interval set) of $G^{\prime }$ 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 [19, 20]. Now, $\mathrm{cghn}(G)\le n+k-1$ if and only if $\gamma (G)\le k$, where $\gamma (G)$ denotes the minimum size of a dominating set in $G$. $◀$

The proof is by induction on the radius of $T$. If $|V(T)|\in \{1,2\}$, then clearly $\mathrm{cghn}(T)={\mathrm{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 $\mathrm{cghn}(T)={\mathrm{cghn}}^B(T)=|L(T)|+1=|V(T)|$. Moreover, in these cases, 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^{\prime }=T-L(T)$. Note that the radius $r(T^{\prime })=r(T)-1$ and, by induction, let $f^{\prime }$ be an optimal (i.e., finishing in $\mathrm{cghn}(T^{\prime })$ turns) strategy for Alice, playing only in the leaves of $T^{\prime }$. Also, assume by induction that, following $f^{\prime }$, the number of turns cannot increase if Bob can pass turns.

We first describe an Alice’s strategy $f$ when she is first to play in $T$. Let ${\mathrm{\ell }}_1^{\prime }$ be the leaf of $T^{\prime }$ first selected by Alice when playing $f^{\prime }$ in $T^{\prime }$. Then Alice selects one leaf ${\mathrm{\ell }}_1$ of $T$ adjacent to ${\mathrm{\ell }}_1^{\prime }$. 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^{\prime }$ on the game in $T^{\prime }$ described below or passed his turn.

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

If $v_i$ is a leaf of $T$ and its neighbor $u$ in $T^{\prime }$ is not already covered, let $v_i^{\prime }=u$. Moreover, if $v_i$ is not a leaf of $T$, let $v_i^{\prime }=v_i$. Then, let ${\mathrm{\ell }}_{i+1}^{\prime }$ be the leaf of $T^{\prime }$ selected by Alice in her optimal strategy $f^{\prime }$ in $T^{\prime }$, considering that Bob played on $v_i^{\prime }$ at its $i$-th turn. Then Alice plays on a leaf ${\mathrm{\ell }}_{i+1}$ of $T$ adjacent to ${\mathrm{\ell }}_{i+1}^{\prime }$ in the game on $T$. Finally, if $v_i$ is a leaf of $T$ and all vertices of $T^{\prime }$ are already covered, then Alice will select any leaf of $T$.

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

Now we show a Bob’s strategy with at least $\lfloor \frac{\mathrm{cghn}(T^{\prime })}{2}\rfloor +|L(T)|$ vertices in the game in which Alice is first to play, given Bob’s best strategy in $T^{\prime }$. Recall from Lemma 10 that we may assume that Alice only plays on leaves and that, by Lemma 11 that, unless all internal vertices (i.e., of $T^{\prime }$) are covered, she selects a leaf whose neighbor is not covered. Let ${\mathrm{\ell }}_i$ be the leaf of $T$ selected by Alice in her $i$-th turn of the game on $T$ and let ${\mathrm{\ell }}_i^{\prime }$ be the leaf of $T^{\prime }$ adjacent to ${\mathrm{\ell }}_i$. If all vertices of $T^{\prime }$ are already covered (in the game in $T$), Bob can only select leaves of $T$. Otherwise, we may assume that ${\mathrm{\ell }}_i^{\prime }$ was not already covered by remark above (by Lemma 11). Since ${\mathrm{\ell }}_i^{\prime }$ was not selected before (considering the game on $T^{\prime }$), Bob assumes that Alice played on ${\mathrm{\ell }}_i^{\prime }$ in the game on $T^{\prime }$. From this, let $v_{i+1}^{\prime }$ be the vertex of $T^{\prime }$ in which Bob would play in his best strategy on $T^{\prime }$ after Alice selects ${\mathrm{\ell }}_i^{\prime }$. Then Bob plays on $v_{i+1}=v_{i+1}^{\prime }$ in the game on $T$. Notice that, at the end of the game, Bob selected at least $\lfloor \mathrm{cghn}(T^{\prime })/2\rfloor$ vertices of $T^{\prime }$ 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 ${\mathrm{cghn}}^B(T)$. $◀$

We prove the theorem in the case of $\mathrm{cghn}(G)$, the case ${\mathrm{cghn}}^B(G)$ is similar. The proof follows the characterization of Theorem 13 (each of the following $5$ claims corresponds to one case of Theorem 13).

Note that if $G$ is a complete graph or a disjoint union of complete graphs, then $\mathrm{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. We prove the following.

• $\mathrm{■}$

  Let $G$ be a cobipartite graph other than a complete graph and the disjoint union of complete graphs and $U=\mathrm{\varnothing }$, $S_A\ne \mathrm{\varnothing }$ and $S_B\ne \mathrm{\varnothing }$. Then, $\mathrm{cghn}(G)=|S|+1$.

• $\mathrm{■}$

  Let $G$ be a cobipartite graph other than a complete graph. If $U\ne \mathrm{\varnothing }$ or $S_B=\mathrm{\varnothing }$, and $r\ge 2$, then $\mathrm{cghn}(G)=|S|+r+1$.

• $\mathrm{■}$

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

• $\mathrm{■}$

  Let $G$ be a cobipartite graph, not a complete graph or the disjoint union of complete graphs. If $r=1$ and $S_A\ne \mathrm{\varnothing }$ and $S_B=\mathrm{\varnothing }$, then $\mathrm{cghn}(G)=|S|+3$.

• $\mathrm{■}$

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

$◀$