Computing the existence of a path in a code execution graph
As such, your problem seems to be NP-complete. To see the membership in NP, you can first guess a path, and then check that this path ends with $V_q$ and is valid. For the hardness part, we can directly reduce from the Boolean satisfiability problem (SAT), which itself is NP-hard. The problem SAT takes as input a formula in conjunctive normal form (CNF), and outputs YES if the formula is satisfiable, and NO otherwise. Let $F = C_1 \land \ldots \land C_m$ be a CNF over variables $\{x_1,\ldots,x_n\}$, where each clause $C_i$ is a disjunction of literals. We will construct an instance graph $G_F$ of your problem with distinguished nodes $V_0$ and $V_\top$ such that there exists a valid path from $V_0$ to $V_\top$ if and only if $F$ is satisfiable. For every variable $x_i$, $1 \leq i \leq n$, $G_F$ has a node $V_{x_i}$ and a node $V_{\overline{x_i}}$, and you have one “indicator” $I_{x_i}$, with possible values being $\{\text{TRUE}, \text{FALSE}\}$. The node $V_{x_i}$ assigns $I_{x_i}$ to TRUE (i.e., you have $I_{x_i} := \text{TRUE}$), while the node $V_{\overline{x_i}}$ assigns $I_{x_i}$ to FALSE. Now, we have an (directed) edge between the node $V_0$ and the node $V_{x_1}$, as well as between $V_0$ and $V_{\overline{x_i}}$. For $1 \leq i &lt; n$ we have the edges $(V_{x_i},V_{x_{i+1}})$, $(V_{x_i},V_{\overline{x_{i+1}}})$, $(V_{\overline{x_i}},V_{x_{i+1}})$, and $(V_{\overline{x_i}},V_{\overline{x_{i+1}}})$. For now, a path in the graph simply assigns a Boolean value to each variable, so we now need to construct the part that “checks” that this assignment satisfies $F$. For every clause $C_i$, $1 \leq i \leq m$, we construct a graph gadget $G_{C_i}$ encoding that $C_i$ is satisfied. For instance, suppose that $C_i$ is the clause $x_4 \lor \overline{x_2} \lor x_3$. Then $G_{c_i}$ has an entry node $V_{C_i,x_4}$, and nodes $V_{C_i,\overline{x_2}}$ and $V_{C_i,x_3}$. You have a “switching” edge from $V_{C_i,x_4}$ to the entry node of $G_{C_{i+1}}$ that checks that $I_{x_4} = \text{TRUE}$, and a switching edge from $V_{C_i,x_4}$ to $V_{C_i,\overline{x_2}}$ that checks that $I_{x_4} = \text{FALSE}$, and so on. You then chain these gadgets in series and plug that chain to the already partially constructed graph $G_F$ (that guesses an assignment), and construct the node $V_\top$ in the expected way (I'll leave the missing details), and voilà: there is a path from $V_0$ to $V_\top$ in $G_F$ if and only if $F$ is satisfiable.

Now, the fact that your problem is NP-hard is not necessarily the end of the world, since, as you said yourself, you can still get good results with a simple brute-force strategy. There are two things that you could investigate:


maybe your graphs have a particular structure that actually makes the problem solvable in polynomial time;
if not, you could consider using a SAT solver (such as Glucose), with an encoding similar to this question, for instance. Sometimes this gives really good results and you don't even need to optimize the thing.