Let $ G$ be a grid graph and we are given two vertices $ s$ and $ t$ and $ l$ , the goal is to check if there exists a path from $ s$ to $ t$ simple path of length $ l$ ?
Brute force algorithm will give $ n^l$ time algorithm as I will simply enumerate all the paths of length $ l$ . Are there faster algorithms for this problem?
My observation is grid graphs are bipartite graphs so all paths will be either of odd length or even length but I don’t know how to use this fact. Note that in grid graphs the degree is bounded by four so from any vertice to any other vertex, number of paths of length $ l$ are bounded by $ 4^l$ . I am looking for an algorithm faster than $ 4^l$ .