On the Complexity of the Maker-Breaker Happy Vertex Game

Suppose Maker has a strategy that ensures a score $s_0$ in $G$. She can apply her strategy in $({[G]}_B,{[M]}_B,{[B]}_B)$, which is possible since the vertices of $V_F({[G]}_B)$ are also free in $G$. At the end of the game, a vertex $u$ is dominated in $G$ if and only if it has a neighbor $v$ colored by Breaker. If this neighbor $v$ is in $B$, then $u$ also has a neighbor colored by Breaker in ${[G]}_B$. Otherwise, $v$ belongs to ${[G]}_B$ and, as the strategy in $G[B]$ mimics the one in $G$, $v$ is still colored by Breaker in ${[G]}_B$. Consequently, any happy vertex in $G$ is also happy in ${[G]}_B$, ensuring that $s({[G]}_B)\ge s(G)$. Similarly, by applying his strategy in $G$ to ${[G]}_B$, Breaker can ensure that $s({[G]}_B)\le s(G)$, which concludes the proof. $◀$

We now focus on properties that can help us computing the score, by limiting the number of moves to consider: When considering scoring game, it happens that some moves will always have a higher impact on the score than others. It then seems natural to think that these moves will be played first. Note that a similar Lemma is used in [3], but the structure of the winning sets being more complex in the Maker-Breaker happy vertex game, it’s stated differently. We first introduce a function $h$ that takes a position $P=(G,M,B)$ and a free vertex $v\in V\setminus (M\cup B)$ and outputs the number of points scored instantly by playing $v$. Formally, we have:

If there is no ambiguity on $P$, we will simply denote it by $h(v)$. The next lemma says that if playing $v$ is worth more points than claiming $u$, even if all the neighbors of $u$ are made happy, then, there exists an optimal strategy in which $v$ is played before $u$.

We give the proof for Maker playing $u$ before $v$, a similar proof provides the result if it is Breaker.

Up to consider a position of the game that is reached later in the strategy, let $P=(G,M,B)$ be a position and suppose Maker has a strategy $𝒮$ that scores $s_0$ in which the next move of Maker is to color $u$. Let $P^{\prime }=(G,M\cup \{u\},B)$. We propose the following strategy for Maker:

• $\mathrm{■}$

  Maker plays $v$.

• $\mathrm{■}$

  If Breaker colors a vertex $w\ne u$, Maker considers that he has played this vertex in $P^{\prime }$. If the answer of Maker in $P^{\prime }$ is a vertex $w^{\prime }\ne v$, Maker answers by playing $w^{\prime }$ in $P$. If Maker’s answer in $P^{\prime }$ is to color $v$, then Maker colors $u$ instead.

• $\mathrm{■}$

  If Breaker colors $u$, Maker considers that he has played $v$ in $P^{\prime }$ and continue her strategy by playing the move that she would have played according to $𝒮$ (inverting the plays on $u$ and $v$).

Following this strategy, when all the vertices are colored, either Maker has colored both $u$ and $v$. In this case, the set of colored vertices by Maker and Breaker at the end of the game is exactly the same, so Maker scores $s_0$ by coloring $v$ first. Otherwise, the set of colored vertices is the same, except that Maker has colored $v$ instead of $u$, and Breaker has colored $u$ instead of $v$. Denote by $P_u=(G,M_u,B_u)$ the resulting position if Maker has played according to $𝒮$ and $P_v=(G,M_v,B_v)$ the resulting position of the described strategy above. The score in $P_v$ is then:

where the second inequality is obtained as we have $M\cup \{v\}\subset M_v$ and $M_u\subset V\setminus B$.

This proves that Maker can ensure a score at least $s_0$ by playing $v$ before $u$. $◀$

The so-called Super Lemma is a result that was introduced simultaneously in the PhD thesis of Nacim Oijid [22] and in the study of the game Incidence [3]. In this section, we adapt it to the Scoring Happy Vertex Game, thereby extending its applicability and providing a crucial tool for analyzing the strategic structure of the game. In the context of our game, this lemma says that if two vertices have the same neighborhood, among the uncolored vertices, and scores the same number of points among the colored vertices, there exists an optimal strategy in which the two players Maker and Breaker will both color one of these two vertices.

The proof is made by induction on $|V_F|$

If ($|V_F|=2$), we have $V_F=\{u,v\}$. For $X=\mathrm{\varnothing }$, the hypothesis implies:

Therefore, after Maker and Breaker’s turns, the score is the same regardless of the choice of the vertex colored by the next player. Hence,

Suppose now $|V_F|\ge 3$. Assume first that Maker has a strategy $𝒮$ to ensure a score $s_0$ in $(G,M\cup \{u\},B\cup \{v\})$, and consider the following strategy in $(G,M,B)$:

• $\mathrm{■}$

  If it’s Maker’s turn, she colors the vertex she would have color in $(G,M\cup \{u\},B\cup \{v\})$, following $𝒮$.

• $\mathrm{■}$

  If Breaker colors a vertex in $\{u,v\}$, Maker colors the second vertex of $\{u,v\}$, which leads to the same score as in $G^{\prime }$ by hypothesis on $\{u,v\}$.

• $\mathrm{■}$

  Otherwise, If Breaker colors $w\notin \{u,v\}$ Maker colors the vertex $w^{\prime }$ that she is supposed to color according to $𝒮$, considering that the last move of Breaker in $(G,M\cup \{u\},B\cup \{v\})$ was $w$. Note that this move is always available and cannot be a vertex {u,v}, unless $|V_F|=3$, in which case, Breaker would also color $w$ in $(G,M\cup \{u\},B\cup \{v\})$.

Following this strategy, if the result is not obtained directly, the resulting position is $(G,M\cup \{w^{\prime }\},B\cup \{w\})$ which has two less free vertices. Hence, by induction, it has the same score as $(G,M\cup \{u,w^{\prime }\},B\cup \{v,w\})$, and since the moves $w^{\prime }$ was supposed to be optimal answer to $w$ in $(G,M\cup \{u\},B\cup \{v\})$, it has a score equal or higher than $(G,M\cup \{u\},B\cup \{v\})$, which proves that Maker can ensure $s_0$ in $(G,M,B)$.

A similar argument applied to Breaker shows that if Breaker can ensure a score of at most $s_0$ in $(G,M\cup \{u\},B\cup \{v\})$, he can ensure at most $s_0$ in $(G,M,B)$, which concludes the proof. $◀$

Similarly to the provided result in [3], this lemma enables us to directly compute the score on complete binary trees, i.e. trees defined by $T_0$ a single vertex, which is a root, and $T_i$ is obtained by taking two copies of $T_{i-1}$, and adding a new root that will be connected to the previous roots of the copies of $T_{i-1}$. The integer $i$ is then called the depth of $T_i$.

If $d=0$, $T_d$ is an isolated vertex, and Maker scores one by coloring it, otherwise the score is $0$. If $d=1$, the graph is $P_3$, the path on $3$ vertices. We can apply Theorem 13 to its two leaves, and Maker scores $1$ if she starts by coloring the middle vertex; otherwise, Breaker colors it and ensures that no vertex is happy. If $d\ge 2$, each pair of leaves attached to the same vertex are twins, thus, we can apply Theorem 13 to them. Hence, Maker has colored half of them, i.e. $2^{d-1}$ of them. Now their parents satisfy the hypothesis of Theorem 13, as they are in the winning set of the connected leaf colored by Maker and the winning set of their common parent (which exists as $d\ge 2$). Thus, Maker will color half of them, ensuring that half of the leaves she has colored are happy, and thus scoring $2^{d-2}$. We can then repeat this process until reaching the vertices of depth $1$, but now, all the colored vertices by Maker already have one neighbor colored by Breaker, and thus will not be happy. Finally, regardless of whether Maker or Breaker colors the root, it has one neighbor colored by Breaker and thus will not be happy. Finally, the score is $2^{d-2}$. This process is depicted in Figure 2. $◀$

Membership in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ follows from the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-completeness of Quantified MAX 2-SAT [3]. To prove the hardness, we reduce from Quantified MAX 2-SAT without the acyclicity restriction. Let $(\psi ,k)$ be an instance of Quantified MAX 2-SAT, with $\psi =Q{x}_{1}Q{x}_2\mathrm{\dots }Q{x}_n\phi$ where $\phi$ is a quantifier-free formula. Let $(l_1\vee l_2)\wedge (l_2\vee l_3)\wedge \mathrm{\cdots }\wedge (l_m\vee l_1)$ be a cycle in $\phi$. Without loss of generality, assume that $l_1=x$, the case $l_1=\neg x$ being similar. We then introduce three new existential quantifiers $\exists a\exists b\exists x^{\prime }$ and the following gadget clauses:

We consider the formula ${\psi }^{\prime }=Q{x}_{1}Q{x}_2\mathrm{\dots }Q{x}_n\exists x^{\prime }\exists a\exists b{\phi }^{\prime }$ where ${\phi }^{\prime }$ is obtained from $\phi$ by substituting $(x^{\prime }\vee l_2)$ to $(x\vee l_2)$, and by adding the clauses $(x\vee a),(\neg x\vee b),(\neg a\vee \neg x^{\prime }),(\neg b\vee x^{\prime })$. Let $k^{\prime }=k+4$.

The intuition behind this construction is that if there is an assignment of the variables that satisfy $k$ clauses in $\psi$, the same assignment putting $x^{\prime }=x$, and choosing the value of $a$ and $b$ such that $a=b=\neg x$ will satisfy $k+4$ clauses in ${\psi }^{\prime }$.

Suppose first that Satisfier has a winning strategy in $(\psi ,k)$, by applying the same strategy in $({\psi }^{\prime },k^{\prime })$, and by setting $x^{\prime }=x$, she ensures that at least $k+2$ clauses are satisfied when $x^{\prime }$ is played, as exactly one of $(x\vee a),(\neg a\vee \neg x^{\prime })$ and exactly one of $(\neg x\vee b),(\neg b\vee x^{\prime })$. Then, by putting $a=b=\neg x$, she ensures to satisfy the two remaining clauses, and that at least $k+4$ clauses are satisfied.

Reciprocally, suppose that Falsifier has a winning strategy in $(\psi ,k)$. By applying the same strategy in $({\psi }^{\prime },k^{\prime })$, he ensures that at most $k-1$ clauses are satisfied when $x_n$ is played. Then, if Satisfier puts $x=x^{\prime }$, the only clauses that can be satisfied in ${\psi }^{\prime }$ that are not in $\psi$ are the $4$ added clauses, hence, Falsifier ensures that at most are satisfied in total. If Satisfier sets $x^{\prime }=\neg x$, the only clause that can be satisfied that was in $\psi$ through this move is the clause $x^{\prime }\vee l_2$, since the other clauses do not contain $x^{\prime }$. Hence, at most $k$ clauses are satisfied outside $\{(x\vee a),(\neg x\vee b),(\neg a\vee \neg x^{\prime }),(\neg b\vee x^{\prime })\}$. But, either $x$ and $\neg x^{\prime }$ are True, then, at most one of $\{(\neg x\vee b),(\neg b\vee x^{\prime })\}$ can be satisfied, or $x$ and $\neg x^{\prime }$ are False, and then at most one of $\{(x\vee a),(\neg a\vee \neg x^{\prime })\}$ can be satisfied. In both cases, at most three of these clauses can be satisfied, and thus, at most in total, ensuring that Falsifier wins in $({\psi }^{\prime },k^{\prime })$. Hence, Satisfier wins in $(\psi ,k)$ if and only if she wins in $({\psi }^{\prime },k^{\prime })$

Finally, in the constructed formula ${\psi }^{\prime }$, the literal–clause incidence graph has at least one less cycle than the one of $\psi$ since the variables $x$ and $x^{\prime }$ are separated by the variables $a$, $\neg a$ and $b$, $\neg b$.

By iterating this construction we can eliminate all cycles. Note that each time this reduction is applied, the number of clauses that can be in a cycle decreases by one, since none of the added clauses can be in a cycle. Thus, the number of time this argument has to be applied is bounded by the number of clause of $\psi$, ensuring that this reduction is polynomial. Therefore, Acyclic Q-MAX 2-SAT is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete. $◀$

Then, we can define our second more specific problem, where we restrict the number of times a variable can occur in a clause.

This problem consists in a quantified version of bounded occurrence MAX 2-SAT - but where we furthermore impose acyclicity on the literal-clause incidence graph. First, we recall that MAX 2-SAT-3, the version of MAX 2-SAT where the number of occurrences of each variable is bounded by $3$ is $\mathrm{𝖭𝖯}$-complete [5]. More formally, this means that the following problem is $\mathrm{𝖭𝖯}$-complete:

We now prove the $\mathrm{𝖭𝖯}$-completeness of Acyclic MAX 2-SAT-2-2 by a reduction from MAX 2-SAT-3.

First, note that Acyclic MAX 2-SAT-2-2 is in $\mathrm{𝖭𝖯}$ as it is an instance of Max 2-SAT.

We reduce from the $\mathrm{𝖭𝖯}$-complete problem MAX 2-SAT-3 [5]. Let $\phi$ be a $2$-CNF formula such that each variable occurs at most thrice and $k$ an integer. If a variable in $\phi$ appears more than twice positively (resp. negatively) then it must appears exactly thrice positively (resp. negatively). Then we can satisfy all three clauses by assigning the variable to True (resp. False) and no clause is satisfied by changing the truth value of the variable from True to False (resp. False to True), i.e. we can always satisfy these three clauses without incidence on the other clauses. Thus we can simply remove these three clauses from $\phi$ and lower $k$ by $3$. By iterating this process we construct a new formula where variables not only occur at most thrice, but also occur at most twice positively and at most twice negatively.

Furthermore, if a variable appears in a cycle in the literal-clause graph, we can apply the gadget from the previous reduction to effectively remove cycles. However, this gadget introduces a new variable $x_i^{\prime }$ for each $x_i$, and requires using one more occurrence of $x_i$ if $x_i$ appears negatively in the cycle or one more of $\neg x_i$ if it appears positively in the cycle. However, this transformation cannot make a variable appear a third time positively or negatively, since if $x_i$ ($\neg x_i$ resp.) appears in the cycle, it means that it appears exactly twice positively (negatively resp.) and thus at most once negatively (positively resp.). Note also that this transformation ensures that all the occurences of $x_i$ and $\neg x_i$ are either of degree $1$, or neighbors of a vertex of degree $1$, ensuring that they cannot appear in cycle, and thus this reduction has to be applied at most once per variable. Hence, this transformation does not make any variable appear more than twice positively or negatively. This entire transformation can be performed in polynomial time, therefore we conclude that the problem is $\mathrm{𝖭𝖯}$-complete. $◀$

A direct consequence of this result is that, by quantifying all the vertices with $\exists$, it’s quantified version is $\mathrm{𝖭𝖯}$-hard and in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$.

The $\mathrm{𝖭𝖯}$-hardness is directly inherited from Acyclic MAX 2-SAT-2-2 by quantifying all the variables with $\exists$. The problem is in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ as a subproblem of QMAX 2-SAT. $◀$

These new variants of Q-MAX 2-SAT are quite general and can be used in several reductions. In particular, the reduction from Q-MAX 2-SAT provided in [3], proving that Incidence, the scoring positional game on graphs is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete starts from the literal-clause incidence graph of a formula and only adds isolated vertices and leaves to it. Hence, we almost answer an open problem of the paper, that asks the complexity of the game on trees with the following corollary:

We perform the same reduction as in [3], except that the input problem is Acyclic QMAX 2-SAT (or Acyclic QMAX 2-SAT-2-2). Since this constructions consists in adding leaves to the literal-clause incidence graph of the formula, it produces either a forest or a caterpillar, depending on the problem from which we do the reduction. $◀$

We provide a reduction from Acyclic Q-MAX 2-SAT. Let $(\psi ,k)$ be an instance of Acyclic Q-MAX 2-SAT with $\psi =Q_1{x}_1{Q}_2{x}_2\mathrm{\dots }{Q}_n{x}_n\phi$ with $\phi$ an acyclic and quantifier-free $2$-CNF formula. Up to add a variable that appear in no clauses, for each pair of consecutive quantifiers of same type, we can suppose that $Q_i=\exists$ if $i$ is odd, and $Q_i=\forall$ if $i$ is even. Note that this addition of dummy variables do not break the acyclicity of the literal-clause incidence graph, as it only adds isolated vertices. The first step of our reduction is to duplicate our formula: we transform it into ${\psi }^{\prime }=Q_1{x}_1{Q}_2{x}_2\mathrm{\dots }{Q}_n{x}_n{Q}_{n+1}{x}_{n+1}{Q}_{n+2}{x}_{n+2}\mathrm{\dots }{Q}_{2n}{x}_{2n}\phi \wedge {\phi }^{\prime }$, where ${\phi }^{\prime }$ is obtained from $\phi$ by changing each $x_i$ to $x_{n+i}$. Note that any strategy satisfying $p$ clauses can be applied twice to satisfy $2p$ clauses in ${\psi }^{\prime }$. Let $m$ be the number of clauses of $\phi$ We will progressively construct a tree by making modifications to the literal-clause incidence graph $G_{\phi \wedge {\phi }^{\prime }}$ of $\phi \wedge {\phi }^{\prime }$, in which we denote by $v_i^{+}$ ($v_i^{-}$ resp.) the vertex corresponding to literal $x_i$ ($\neg x_i$ resp.).

Since the graph is acyclic by hypothesis, it must be a disjoint union of trees $T_1,T_2,\mathrm{\dots }{T}_{\mathrm{\ell }}$. We now construct a tree $T$ based on this graph. We start from $T_1\cup T_2\cup \mathrm{\cdots }\cup T_{\mathrm{\ell }}$. For every tree $T_i$ let us fix two of its leaves $v_i^{\mathrm{\ell }}$ and $u_i^{\mathrm{\ell }}$ and let us connect all trees into a single one by adding edges between $u_i^{\mathrm{\ell }}$ and $v_{i+1}^{\mathrm{\ell }}$ for . We denote by $\sim$ either $+$ or $-$. For each edge $\{v_i^{\sim },v_j^{\sim }\}$, we introduce a new vertex $v_{ij}^{\sim \sim }$ and replace the edge with two edges: $\{v_i^{\sim },v_{ij}^{\sim \sim }\}$ and $\{v_{ij}^{\sim \sim },v_j^{\sim }\}$.

Next, to each vertex $v_i^{\sim }$, we attach $16(n+1-i)m$ leaves. Finally, we introduce $n$ new vertices $v_i$, attach $16(n+1-i)m-4m$ leaves to each of them, add we connect them through a path whose extremity $v_n$ is attached to $v_1^{+}$.

An example of reduction is provided in Figure 4.

Let $s_0$ be defined as follows:

Let $s=s_0+m-k+1$. Both $T$ and $s$ can be constructed in polynomial time. We prove that Falsifier wins in $(\psi ,k)$ if and only if Maker wins in $(T,s)$.

Firstly, each leaf can be colored using Theorem 13. Denote by $M$ and $B$ the vertices colored during this step. Then, if $1\le i\le j\le 2n$, we have $h(v_i^{\sim })\ge |N(v_i)\setminus B|$ and $h(v_i)\ge |N(v_j^{\sim })\setminus B|$. Hence, using Lemma 12, there exists an optimal strategy in which Maker and Breaker color the vertices in the following order, for $1\le i\le n$, in increasing order:

• $\mathrm{■}$

  Maker colors one of $\{v_{2i-1}^{+},v_{2i-1}^{-}\}$.

• $\mathrm{■}$

  Breaker colors the other vertex in $\{v_{2i-1}^{+},v_{2i-1}^{-}\}$.

• $\mathrm{■}$

  Maker colors $v_{2i-1}$.

• $\mathrm{■}$

  Breaker colors one of $\{v_{2i}^{+},v_{2i}^{-}\}$.

• $\mathrm{■}$

  Maker colors the other vertex in $\{v_{2i}^{+},v_{2i}^{-}\}$.

• $\mathrm{■}$

  Breaker colors $v_{2i}$.

Considering this order, which is optimal, note that all the moves are forced or have to be chosen among two vertices $(v_i^{+},v_i^{-})$ that are connected to the same number of leaves. Moreover, no vertex $v_i^{\sim }$ nor $v_i$ can be happy, because of the leaves colored by Breaker connected to them. Hence, we know that after this step, Maker has colored exactly $s_0$ happy vertices.

Finally, once all the previously described vertices have been colored, only the vertices $v_{ij}^{\sim \sim }$ remain. These vertices will be colored last, and each of them can be happy if and only if both of their adjacent vertices have been colored by Maker.

Suppose first that Falsifier has a winning strategy $𝒮$ in $(\psi ,k)$. We define the following strategy for Maker:

• $\mathrm{■}$

  For $0\le i\le n-1$, if Falsifier has to put $x_{2i+1}$ to True, Maker colors $v_i^{-}$, ensuring that Breaker will color $v_i^{+}$; otherwise, she colors $v_i^{+}$, ensuring that Breaker colors $v_i^{-}$.

• $\mathrm{■}$

  For $1\le i\le n$, if Breaker colors $v_{2i}^{+}$, Maker considers that Satisfier has put $x_{2i}$ to True in $𝒮$. Otherwise, she considers that Satisfier has put $x_{2i}$ to False.

• $\mathrm{■}$

  When $x_n$ is played, Maker applies $𝒮$ again from scratch.

When all the vertices $v_i,v_i^{+}$ and $v_i^{-}$ have been played, if $C_j$ is a clause that has not been satisfied in $\phi \wedge {\phi }^{\prime }$, then its two literals has been put to False. Thus, since $𝒮$ was a winning strategy for Satisfier in $(\psi ,k)$, we know that at most $k-1$ clauses of $\phi$ and at most $k-1$ clauses of ${\phi }^{\prime }$ are satisfied. Thus, at least $2\left(m-(k-1)\right)$ vertices $v_{ij}^{\sim \sim }$ has their two neighbors colored by Maker. Hence, Maker can by playing only on them ensure to color at least half of them, i.e. $m-k+1$, and having colored $s_0+m-k+1=s$ happy vertices in total.

Reciprocally, suppose that Satisfier has a winning strategy $𝒮$ in $(\psi ,k)$. We define the following strategy for Breaker:

• $\mathrm{■}$

  For $0\le i\le n-1$, if Satisfier has to put $x_{2i+1}$ to True, Breaker colors $v_i^{+}$; otherwise, he colors $v_i^{-}$.

• $\mathrm{■}$

  For $1\le i\le n$, if Maker colors $v_{2i}^{+}$, Breaker colors $v^{-}2i$ and considers that Satisfier has put $x_{2i}$ to False in $𝒮$. Otherwise, he considers that Satisfier has put $x_{2i}$ to True.

• $\mathrm{■}$

  When $x_n$ is played, Breaker applies $𝒮$ again from scratch.

Now, when all the vertices, $v_i,v_i^{+}$ and $v_i^{-}$ have been played, the same argument as above ensures that any clause that was satisfied by $𝒮$ has one of its literal played by Breaker. Hence, since $𝒮$ was a winning strategy in $\psi$, at least $2k$ vertices $v_{ij}^{\sim \sim }$ are already dominated by Breaker, and thus, at most $2(m-k)$ of them are not. By pairing them, Breaker can ensure to claim at least $m-k$ of them ensuring that Maker scores at most . Thus, Breaker wins. $◀$

The proof is identical to the one on trees, except that instead of using Acyclic Q-MAX 2-SAT, we now rely on Acyclic Q-MAX 2-SAT-2-2, which is proved to be $\mathrm{𝖭𝖯}$-hard. In this case, the constructed graph $G_{\phi }$ is not only a disjoint union of trees, but in particular a disjoint union of paths, since each vertex in the graph would have degree at most $2$. The same reduction carries through and produces a caterpillar by always connecting the different paths through one of their extremities. This shows that SHVG remains $\mathrm{𝖭𝖯}$-hard on caterpillars. $◀$

Let $𝒮$ be a strategy for Maker in $s(G\setminus \{v\},M\setminus \{v\},B)$. By applying $𝒮$ in $(G,M,B)$ which has the same set of uncolored vertices, any vertex made happy in $(G,M,B)$ is also happy in $s(G\setminus \{v\},M\setminus \{v\},B)$, which proves the result. $◀$

Let $S$ be a subdivided star. First, since the Maker-Breaker domination game on $S$ has outcome $𝒩$ [8], we have $Bs(S)=0$.

Let $C$ be its central vertex and $P_1,\mathrm{\dots },P_k$ be the paths attached to it. Note that if $k\le 2$, $S$ is a path and its score is given by Theorem 27, i.e. its score is $1$ if it has an odd number of vertices and Maker starts, and $0$ otherwise.

Suppose now that Maker starts and $k>2$. Let $l$ be the number of odd paths in $S$ and let $P_1,\mathrm{\dots },P_l$ be these $l$ odd-length paths. Suppose $l\ge 1$. If Maker colors the central vertex at the beginning, by coloring $C$, she can guarantee a score of at least $Bs(S,\{C\},\mathrm{\varnothing })$. By Lemma 31, $Bs(S,\{C\},\mathrm{\varnothing })\ge Bs(S\setminus C,\mathrm{\varnothing },\mathrm{\varnothing })$ and, since $S\setminus C$ is an union of paths, by Corollary 29, $Bs(S\setminus C,\mathrm{\varnothing },\mathrm{\varnothing })=\lfloor \frac{l}{2}\rfloor$. Hence $Ms(S)\ge \lfloor \frac{l}{2}\rfloor$.

Let $n_i=2k_i+1$ be the length of $P_i$ and denote by $u_1^i,\mathrm{\dots },u_{2k_i+1}^i$ the vertices of $P_i$ for $1\le i\le l$ such that $u_{2k_i+1}^i$ is connected to $C$. Breaker has a pairing strategy to prevent Maker from scoring inside the even-length paths by pairing adjacent vertices starting from their leaves. Moreover the pairing ${\{(u_{2j-1}^1,u_{2j}^1)\}}_{1\le j\le k_1}\cup \{(u_{2k_1+1}^1,C)\}$ enables Breaker to prevent Maker from scoring inside $P_1\cup \{C\}$. It results that the only vertices that can be made happy are in $(P_2+\mathrm{\cdots }+P_l)$. Hence, by applying the strategy provided in Corollary 29 in $(P_2+\mathrm{\cdots }+P_l)$ when Maker plays in it, and by applying his pairing strategy in $S\setminus \left(P_2+\mathrm{\cdots }+P_l\right)$, since $Ms(P_2+\mathrm{\cdots }+P_l)=\lceil \frac{l-1}{2}\rceil =\lfloor \frac{l}{2}\rfloor$, we conclude that $Ms(S)\le \lfloor \frac{l}{2}\rfloor$. All together, we have $Ms(S)=\lfloor \frac{l}{2}\rfloor$

If $l=0$ however, Maker can still guarantee a score of $1$. We prove this result by induction. Since $k>2$, there are at least two even paths $P_1$ and $P_2$. Let $S_n$ be the subdivided star that is formed by connecting $n$ paths $P_1,P_2,\mathrm{\dots },P_n$ of length exactly $2$ to a central vertex $C$. By coloring successively all the leaves’ neighbors, Maker forces Breaker to answer by coloring each leaves, since otherwise by coloring one of the leaves and its neighbor Maker can score $1$, which will conclude the proof. Once Maker colored all the leaves’ neighbors and Breaker colored all the leaves, it is again Maker’s turn. All vertices adjacent to the central vertex have been colored by Maker, thus by coloring it Maker scores $1$. As a result, $Ms(S_n)$ is at least one. This sequence is illustrated in Figure 5 for $n=3$.

If $S$ is formed by connecting $n$ paths $P_1,P_2,\mathrm{\dots },P_n$ each of length $2k_i$ for $1\le i\le n$ to a central vertex $C$, and assuming that $P_1$ has length $2k_1>2$. Then Maker colors the neighbor of the leaf of $P_1$, forcing Breaker to answer by playing on the leaf, or letting Maker score $1$ in her next move. Then by Lemma 31 and Lemma 11, Maker can ensure on this position a score at least equal to that of $S^{\prime }$ formed by connecting $n$ paths $P_1^{\prime },P_2,\mathrm{\dots },P_n$ to $C$ where $P_1^{\prime }$ is the path of length $2k_1-2$, and, inductively, at least that of $S_n$.