Equivalence of two dominating set games

53 Views Asked by At

Suppose that $G = (V,E)$ is a loopless directed graph. Consider the game in which two players, $P_1$ and $P_2$ take turns (i.e., alternate) selecting one vertex at a time in $G$. For simplicity assume that $n$ is even, and that each player gets $n/2$ total turns, with $P_1$ making the first move. Also suppose that if a vertex has already been chosen by some player, it may not be chosen again.

$P_1$ wins the game if the $n$ distinct chosen vertices comprise a dominating set for $G$. We define a dominating set $D$ in a digraph to be a set of vertices such that for all vertices $v \in E$, either $v \in D$ or there is an edge $(u,v) \in E$ such that $u \in D$. $P_2$ wins the game if the $n$ chosen vertices do not comprise a dominating set for $G$.

Now consider a variant of this game in which $P_1$ first chooses $n/2$ vertices and then $P_2$ chooses $n/2$ vertices. Will these two versions of the game have the same outcome? I suspect so, because it is $P_2$'s optimal strategy in both games to choose vertices that cover vertices already covered by the vertices chosen by $P_1$.

1

There are 1 best solutions below

0
On

The equivalence fails even for undirected graphs, for instance, for a disjoint union of two stars of four vertices each. For directed graphs a counterexample is even simpler, a directed path of four vertices.