# Tag Info

The graph in question is a grid discretization of the phase space ($TC$ in the paper). Consider a 4-connected grid in the plane with 10x10 vertices. The branching factor of this graph is 4 (ignoring the boundary), but there are only 100 vertices in this graph total. BFS on this graph will not take exponential time because BFS throws away exponentially many ...