We can restrict ourselves to tree graphs. What is the complexity of the following problem?

Given a simple connected graph $G=(V, E, \phi)$ and a vertex $v\in V$, is the frog game solvable in $v$?

To play the frog game, start by placing one frog on each vertex: $f_0(u)=1,u\in V$.

Given $G$ and $f_k$ after $k$ moves have been made, a new move consists of selecting two nonempty (contain at least one frog) vertices $v_1, v_2\in V$ that are connected by a path of $f(v_1)$ distinct edges, then moving all frogs from $v_1$ to $v_2$: Now we have $f_{k+1}(v_1)=0$ and $f_{k+1}(v_2)=f_k(v_2)+f_k(v_1)$.

For example, if $f(w)=1$, then frogs in $w$ can be moved to its (nonempty) neighboring vertices. If $f(w)=2$, then frogs in $w$ can be moved to (nonempty) neighbors of its neighboring vertices, and so on. (Frogs jump over $f(w)$ distinct edges.)

We say that the frog game is solvable in some vertex $v\in V$ if there exists a sequence of moves such that all frogs end up in the vertex $v$: Meaning $f_0, f_1, \dots, f_{n-1}, n=|V|$ where $f_{n-1}(u)=|V|$ for $u=v$ and $f_{n-1}(u)=0$ for $u\ne v$.

Here is a short presentation with examples.

I suspect this problem is in NP, can we prove this?

We can solve this problem recursively.

For example, given a path graph "$v_1 - v_2 - v_3 - v_4 - v_5$" and the goal $v_2$;

We compute the multiset of path distances from the goal $v_2$ to other vertices: $D=\{1,1,2,3\}$.

We consider all partitions of $|V|-1=4$ that can be made with elements of $D$:

$$ \begin{array}{} \text{A.} & 4 & = & 3 + 1\\ \text{B.} & 4 & = & 2 + 1 + 1\\ \end{array} $$

Now we check each partition by assigning the respective vertices as new sub-goals (in all possible ways) and applying this procedure recursively. (Set $f(w)=0$ for unusable vertices $w$ within the sub-goal.)

$\text{A.}$ For example, when looking at the first partition, we have two possible selections of sub-goals. We can either consider $v_1$ or $v_3$, as both could be "$1$" in "$4=3+1$".

• If we take $v_3$, then the other sub-goal is graph "$v_1 - 0 - 0 - v_4 - v_5$" in $v_5$, but $2$ cannot be partitioned using elements of $D=\{4,1\}$, therefore this selection of sub-goals is impossible.

• If we take $v_1$, then the other sub-goal is graph "$0 - 0 - v_3 - v_4 - v_5$" in $v_5$, with $D=\{1,2\}$ and one possible partition "$2=2$". Going one step deeper, we get a trivial sub-sub-goal of "$v_3 - v_4$" in $v_3$ with trivial $D=\{1\}$ and partition "$1=1$". Therefore, this partition and selection of sub-goals gives a solution of the problem in $v_2$. Therefore, the graph is solvable in $v_2$.

$\text{B.}$ For example, when looking at the second partition, the jumps at distance $1$ are trivial and only possible selection for sub-goals, and the other sub-goal is to have $2$ frogs at vertex $v_4$ using the remaining usable vertices $v_4-v_5$; that is, it is again a trivial sub-goal with $D=\{1\}$ and partition "$1=1$". Therefore, the graph is solvable in $v_2$.

In general, this procedure is exponential at worst. When the vertex is not solvable, we will need to check all partitions and all selections of sub-goals.

Can we do better? (Is it possible that this problem is not in NP?)

Note that it is not hard to prove that path graphs $P_k$ specifically, i.e. "$v_1-v_2-\dots-v_k$", are solvable in every vertex for every $k\in\mathbb N$. That is, certain classes of graphs can be solved in terms of theorems, by explicitly constructing sequences of jumps that solve vertices or showing certain vertices are never solvable.

But I doubt that can be done for all tree graphs.

Note that I posted a similar question a long time ago on Computer Science, asking about a better approach than the exponential partition analysis (here I ask about complexity class), but there I got nothing new after two bounties. (Not sure if this counts as a cross-post, but I'll link it here just in case).