Players Ruby and Bob are given an undirected graph and a number $N$. First Ruby colors $N$ vertices red, then Bob colors $N$ vertices blue (they must be distinct from Ruby's choices). Afterward, all other points on the graph are given the color of whichever color they are closest to (shortest path) with ties left blank. The player with more of their color on the resulting graph wins.

Can the first player always win (or tie)?

Some context: This problem arose for me out of a mobile puzzle game. My knowledge in graph theory is pretty minimal, so I don't have much machinery to solve it (but I have spent a while with small graphs, always able to find an unbeatable strategy for the first player). My thoughts so far are to mark points as having an advantage in comparison to their neighbors, the maximum of which I'd guess provides a win with N=1. For higher N though the dynamics get much more challenging for me to express. There seems to be an aspect of even-spacing which I'm not sure how to formalize (perhaps it's picking vertices which minimize their shortest distance to any point).

Also if anyone has heard of a similar problem before (specifically related to coloring a graph based on the shortest path to a colored vertex) or has references I'd be happy to read them, but was unable to find much since I'm not certain what to search for.

  • 1
    $\begingroup$ Do you have any thoughts on the problem? The first player certainly cannot always win; experiment with small graphs and values of N to see this $\endgroup$ – TomGrubb Jun 21 '17 at 1:14
  • $\begingroup$ I've experimented a bit with small graphs but haven't found anything contrary. I think with N=1 a strategy stealing argument gives the first player a certain win/tie. I haven't exhausted N=2, but I was hoping there would be some nontransitive strategies (which I think is a consequence of player 2 being able to always win on a certain graph). Any guidance on the structure of a counterexample would be really helpful. (For what it's worth, I came up with this on my own for fun, it's not for a class or anything.) $\endgroup$ – George Hoqqanen Jun 21 '17 at 3:14
  • $\begingroup$ Consider $N=1$ and the cycle graph on 3 vertices; both players will end with one vertex regardless of the initial placements $\endgroup$ – TomGrubb Jun 21 '17 at 3:16
  • $\begingroup$ Sure, I was asking for situations where a win or tie isn't possible for the first player. I.e. are there graphs where no matter what the first player does the second player can win. +1 to yikai $\endgroup$ – George Hoqqanen Jun 21 '17 at 3:19

I believe that the first player cannot always guarantee a tie, even when $N=1$. Some observations:

  • Given a graph $G$ and a vertex subset $X \subset V(G)$, we can always modify $G$ so that the players are forced to choose a vertex in $X$: add a huge independent set $I$ to $G$ and make all the vertices in $I$ adjacent only to the vertices in $X$, so that if one player plays outside $X$ and the other plays inside it, then the player inside $X$ grabs all vertices in $I$ and wins even if the other player gets everything else.

  • This trick also lets us assign nonnegative integer weights to the edges, and calculate distances according to the weights: subdivide each edge an appropriate number of times, and choose our subset $X$ so that the internal vertices of the subdivided edges aren't feasible to play in. (Edit: As originally written this doesn't quite work, because the players in the modified graph would score points for the subdivided edges, but I think it can be made to work if you "blow up" the real vertices into large cliques or large independent sets, so that the value of getting one more "real vertex" far exceeds the value of the new vertices inside all the subdivided edges. This transformation doesn't quite preserve the rules of the game: in the transformed graph, Bob is essentially allowed to pick a vertex already chosen by Alice, so the transformed graph is friendlier to Bob than the original graph, but if the point is to come up with a graph where Bob can guarantee a win, then this is not a problem for us.)

Once you've done these tricks, I think you can create a rock-paper-scissors scenario using the complete bipartite graph $K_{3,3}$. Say that the three vertices one partite set are $R,P,S$ and that the three vertices of the other set are $X,Y,Z$. The vertex $R$ has weights $1,2,3$ to $X,Y,Z$ respectively; $P$ has weights $3,1,2$, and $S$ has weights $2,3,1$. The players are only allowed to play in $\{R,P,S\}$, via the above tricks.

Now, if Alice picks $R$, then Bob picks $P$ and gets $Y,Z$ versus Alice's $X$. ($S$ is equidistant to both $R$ and $P$). If Alice picks $P$, Bob picks $S$ and gets $X,Z$ versus Alice's $Y$. If Alice picks $S$, Bob picks $R$ and gets $X,Y$ versus Alice's $Z$.

  • 1
    $\begingroup$ A nice idea. I guess that you can simplify your tricks to adding sufficiently many (say, five) leaves to each of $X$, $Y$, and $Z$ in the subdivided $K_{3,3}$. $\endgroup$ – Alex Ravsky Jun 27 '17 at 16:21
  • 1
    $\begingroup$ Ah, I see your point: in that case, whoever gets $X$ (or $Y$, or $Z$) also gets all the leaves attached to it, and we just need enough leaves to drown out the noise introduced by the subdivided edges. That's a nice way of doing it. $\endgroup$ – Gregory J. Puleo Jun 27 '17 at 17:47

I can prove that for the first player (Ruby) is possible not to lose in some simple cases for the given graph $G$ with $n$ vertices.

  1. Domination number $\gamma(G)\le N$. Indeed, in this case at her move the first player can assure that the red vertices constitute a dominating set. Then after the second player move only $N$ vertices colored by him will become blue, because any not red vertex has a red neighbor, so if it was not colored by the second player then it becomes red if it has no blue neighbor or remains blank otherwise.

  2. The graph $G$ is a tree and $N=1$. By Jordan Theorem from 1869 (which I proved independently few hours ago :-) ), $G$ has a vertex $v$ whose removal disconnects the tree into components of size at most $n/2$. So if the first player color the vertex $v$, the second player after his move will make blue only vertices from one of the connected components, whose size is at most $n/2$. The remaining vertices will become red.

  3. The graph $G$ is a cycle. Let the first player color clockwise vertices $v_1,\dots, v_N,v_{N+1}=v_1$ assuring that their removal disconnects the cycle into components whose sizes differs by at most $1$. Let these sizes be $l$ and $l+1$. For any $i<N$ denote the clockwise path (without its second endpoint) from a vertex $v_i$ to a vertex $v_{i+1}$ by $[v_i,v_{i+1})$. Consider a component $C$ bounded by vertices $v_i$ and $v_{i+1}$. If the second player color one vertex $v$ in $C$, then $C$ with its two red boundary vertices will be split into two paths $v_i,\dots, v$ and $v,\dots, v_{i+1}$ with the endpoints of different colors. By symmetry, after the final coloring each of them will have equal number of red and black vertices. But here the blue vertex $v$ was counted two times, as a endpoint of each of the paths. Taking this into account we see that the second player obtain no gain at the clockwise path $[v_i,v_{i+1})$. If the second player color more than one vertex $v$ in $C$ then he can assure all of vertices $[v_i,v_{i+1})$ but $v_i$ be blue, but at the cost that all vertices a some clockwise path $[v_j,v_{j+1})$ will be red. So he wins at most $l+1$ vertices at $[v_i,v_{i+1})$ but loses at least $l+1$ vertices at $[v_j,v_{j+1})$. Thus he obtains no gain in this case too.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.