Let's have a graph evaluated by integers, a number $N$, a stating node $S$ and a goal node $G$. The graph is a square mesh and all edges are oriented rightwards or downwards. Find a path form $S$ to $G$ which has a cost divisible by $N$. It doesn't have to be the shortest one. If more such paths exist, any can be taken as the result.
I'd like to know a polynomial algorithm which depends on the graph depth but not much on $N$ because $N$ can be really big.
My attempt:
It is enough to calculate only in $\Bbb{Z}_N$ while the result cost must be zero. Well, this helps a bit but it helps only a little if $N$ is big.
Scanning all possible paths from $S$ to $G$ is $O\bigl(2^d\bigr)$ hard where $d$ is the depth of goal.
My idea is dividing the graph into two parts, nodes closer to $S$ and nodes closer to $G$. Then I can search the graph from $S$ to the border and from $G$ to the border and compare the residuums. This is $O\bigl(2^{\frac{d}2}\bigr)$ hard.
You can use dynamic programming for this. Algorithm:
1) find topological sorting of your nodes. Let's denote the sorted nodes as $v_0, v_1, ..., v_{n-1}$. Note that $S = v_0$ and $G = v_n$.
2) create a boolean DP table with two dimension: first dimension size $n$ and second dimension of size $N$. Initialize all values of the table to "false". Initialize DP[0][0] to "true". $$\text{DP-entry: DP[i][j] == "true" } \iff \text{there is a path from } v_0 \text{ to } v_i \text{ with cost } c \text{ such that } c =_N j $$
3) traverse the table in the following way:
for i from 0 to n-1 do: for j from 0 to N-1 do: if(DP[i][j]) do: for every neighbour k of i: DP[k][j+cost(i, k)] = true;4) check whether DP[n][0] = true. If yes you can use backtracking to find a valid path.