Proposition: Directional transient potentials

Fix $n\in {\mathbb{R}}^d$ and $\beta \ge 0$. The following are equivalent:

1. $n\cdot v(C)\le \beta$ for every simple cycle;

2. finite potentials ${\pi }_v$ exist such that

   $$n\cdot {\Delta }_e-\beta t_e\le {\pi }_{\mathrm{head}(e)}-{\pi }_{\mathrm{tail}(e)}(e\in E(Q)).$$

Every path from $u$ to $v$, of duration at most $t$, then satisfies

Proof. Summing (eq:potential) around a cycle proves (i). Conversely, set $w_e=n\cdot {\Delta }_e-\beta t_e$. Every closed walk has nonpositive weight by cycle decomposition. Add a root with zero-weight edges to all vertices. Let ${\pi }_v$ be the maximum weight of a root-to-$v$ walk. Removing nonpositive closed subwalks does not decrease its weight, so a maximum exists among finitely many simple walks. Appending an edge gives ${\pi }_{\mathrm{head}}\ge {\pi }_{\mathrm{tail}}+w_e$, which proves (ii). Summation gives (eq:potentialpath); use $\beta \ge 0$ for a path completed before $t$.