Brief Announcement: Time-Travel Planning with Tenet Turnstiles

We define a total order on pairs $(d,t)\in \mathbb{N}\times \mathbb{N}$: iff , or $d=d^{\prime }$ and ($d$ even and ), or ($d$ odd and $t>t^{\prime }$). Intuitively, after an even number of inversions the agent moves forward (minimizing arrival time), while after an odd number it moves backward (maximizing arrival time, so it can reach the destination earlier by then going forward).

The offline algorithm is a Dijkstra-like scan over vertices. Each vertex $u$ carries a key $(d[u],tmp[u])$: the minimum number of inversions to reach $u$ and the associated optimal time under the order above. A priority queue extracts candidates in this order; for each extracted $(u,d,t)$, the algorithm scans neighbors $v$ and inserts the best reachable $(v,d^{\prime },t^{\prime })$ into the queue. Correctness follows from showing that the order is consistent with optimal substructure of Tenet travels: any prefix of an optimal travel is itself optimal. Since each vertex is finalized at most once and the queue size is bounded by $n$, the total running time is $O(m\log n)$.

Lower bound. We use an indistinguishability argument. For odd $n$ and large $t$, consider the graph $G_n^t$ with $V=\{1,\mathrm{\dots },n\}$, alternating edges at times $0$ and $1$, and a full path at time $t$ as illustrated in Figure 3. Instances $G_n^{\mathrm{\infty }}$ and $G_n^{t_{max}+1}$ (where $t_{max}$ is the furthest time reached by the algorithm) are indistinguishable, yet their optimal costs differ by a factor of $n$: the algorithm must pay at least $n$ inversions to traverse $G_n^{\mathrm{\infty }}$, while OPT pays $1$ on $G_n^{t_{max}+1}$ using the late full path.

Upper bound. Any simple travel uses at most $n-1$ edges and thus at most $n-1$ inversions. Since our strategy may initially wait until the ODOC travel is identifiable, it requires at most one extra inversion, giving a total cost bounded by $n$.

Lower bound. For $n=3k+2$, consider a graph $G_k$ with $k$ gadgets hanging off the source: each gadget has a spine of length $3$ with its middle edge available only at time $1$, as illustrated in Figure 4. Under S-online, the agent cannot distinguish which gadget leads to the destination before exploring all of them, forcing linear cost ($\frac{4}{3}n-\frac{17}{3}$ inversions) while OPT uses one inversion.

Upper bound. The DFS strategy maintains a spanning tree of explored vertices via parent pointers, prioritizing the destination when available. Each tree edge is traversed at most twice (once down, once back), except the last two (no backtrack from destination, and the penultimate is always explored first). Each traversal may require one inversion; including a possible final inversion to return to time $0$ gives at most $2(n-1)-2=2n-4$ inversions.

Call a vertex a cliff if its predecessor and one of its successors in the footprint tree have an earlier time of occurrence. Cliffs force the agent to perform extra inversions: visiting a cliff-hanger (a descendant reachable from the cliff backward in time) and returning costs $2$ inversions.

The ST-online-easy algorithm greedily follows a cost-optimal travel to an unvisited vertex at each step, exploring cliff-hangers as they appear. If $k$ is the maximum number of cliffs on any root-to-leaf path, the total cost is bounded by $f(k)=-3k^2+(2n-1)k+1$. This concave quadratic is maximized at $k=(2n-1)/6$, yielding $\frac{{(2n-1)}^2}{12}+1$.

Tightness. An adaptive adversary reveals edges incrementally: each time the algorithm commits to exploration, the adversary places the next useful edge further in the future, forcing the algorithm to accumulate cliffs. This construction matches the bound $f(k)$ for every integer $k\in [2,(n-4)/2]$, confirming optimality.

Fix any algorithm $A$ with claimed ratio $\rho$. Start with edge $(src,x)\in E_0$. The agent must explore $x$ (otherwise we add a direct edge from $x$ to $dst$ invisible to the agent). After the agent has oscillated between $src$ and $x$ for $\rho$ rounds, costing $2\rho$ inversions, we place the edge $(src,dst)\in E_{t+1}$ where $t$ is the current furthest time reached. Then OPT pays $1$ and the algorithm pays more than $\rho$, a contradiction.