Recently, I've stuck in quite an interesting problem. Here's its full description:
Consider a connected, non-directed, weighted graph G. In some $v \in V(G)$ stays a chip. Two players are playing the game. On each turn player moves chip to the $u$, where $u$ is one of the adjacent vertexes of current vertex.
Consider a set of edges $S \subseteq E(G)$ so that each of $e \in S$ will be visited infinite times during the game. Let $m$ be the maximum weight in $S$, so $m = \max { \{weight(e) | e \in S\} } $.
If $m$ is even, then first player is a winner, otherwise second players wins.
Let us state decision-problem L(G): given a graph G, output "Yes" if first player have optimal strategy on such graph, and "No" otherwise.
Prove that $L \in NP$
Here what i've found, studying this problem:
- If players fix their strategies $S_1$ and $S_2$, and if $S_1$ and $S_2$ are optimal, then those strategies are deterministic. It means that next vertex depends only on current vertex and whose turn it is, not on history or something else. I don't have strict proof for this fact, but it seems intuitevly correct.
- Given a fixed $S_1$ and $S_2$ we can find a winner in $poly(|V(G)|)$. Indeed, we can model a $|V(G)| + 1$ step of the game, resulting in path $v_1 \to v_2 \to \ldots \to v_{n + 1}$. Among these $n + 1$ vertexes there are at least two repeating (by Pigeonhole principle), some $v_i$ and $v_j$. We know, that moves are made deterministically, therefore we've found a cycle. Set of edges of that cycle is preciesly $S$ $\Rightarrow$ we can find all these edges, find maximum among them and find a winner.
So, I've come up with asking for optimal strategy of winner as certificate. However, I didn't managed to find an easy solution to verify that this strategy is indeed optimal (we can't iterate over all strategies of other player, because there are exponentially large number of them).
It seems to me, that this subtask (prove in polynomial time that strategy is indeed optimal) is quite "classic" and should have been already solved. However, I didn't managed to find it in google, so I decided to ask here.
Maybe, I should ask for some additional information along with the strategy of the winner?