• New Upper Bound:

    The authors show that if either

    1. the graph in each time step has bounded degree, or

    2. the agent is allowed to make two moves per time step,

      then TEXP can be solved in $\mathcal{O}(n^1.75)$ steps — improving over the general $\mathcal{O}(n^2)$ worst-case bound.

  • Techniques:

    They develop a refined labeling and propagation strategy through phases and subphases, where labels correspond to partial walks visiting unseen vertices. A tighter analysis improves their earlier $\mathcal{O}(n^1.8)$ bound to $\mathcal{O}(n^1.75)$.

  • Structural Insight:

    The key is showing that the graph in each time step admits a spanning tree of bounded degree, even when simulating two moves per time step via graph squaring.

  • Lower Bounds:

    • They prove that for sparse temporal graphs ($\mathcal{O}(n)$ edges in the union), allowing $c$ moves per step (for any constant $c$) yields at most constant-factor improvements.
    • They establish logarithmic inapproximability: it's NP-hard to approximate TEXP with a ratio better than $c \log n$ even in bounded-degree graphs or with two moves per step.

  • NP-Hardness Construction:

    A sophisticated reduction from Hamiltonian s–t-path shows that even allowing two moves per step, distinguishing whether a graph can be explored in $\mathcal{O}(n)$ or $\Omega(n \log n)$ time is NP-hard.