
\section{Computing the extremal mean lambda-star, a calibrating potential, and the tight subgraph}\label{sec:calib-alg}

This appendix records an explicit finite procedure to compute the objects in Section~\ref{sec:core-truth}.
All steps are explicit finite graph algorithms; we include them to make the normalization fully machine-checkable.

\subsection{Computing the minimal cycle mean}

Let $G=(V,E)$ with $|V|=n$, $|E|=m$, and costs $c:E\to\mathbb{R}$.
The minimal cycle mean
\[
\lambda_*=\min_{\gamma\ \mathrm{cycle}} \frac{1}{|\gamma|}\sum_{e\in\gamma} c(e)
\]
can be computed in $O(nm)$ time using Karp's algorithm.

\begin{algorithm}[H]
\caption{Karp minimal cycle mean}\label{alg:karp}
\begin{algorithmic}[1]
\Require Directed graph $G=(V,E)$, costs $c(e)$
\Ensure $\lambda_*$
\State Choose any ordering of vertices and initialize $d_0(v)=0$ for all $v\in V$
\For{$k=1$ to $n$}
\ForAll{$v\in V$}
\State $d_k(v)\gets \min_{(u\to v)\in E}\big(d_{k-1}(u)+c(u\to v)\big)$
\EndFor
\EndFor
\ForAll{$v\in V$}
\State $M(v)\gets \max_{0\le k\le n-1}\frac{d_n(v)-d_k(v)}{n-k}$
\EndFor
\State $\lambda_*\gets \min_{v\in V} M(v)$
\State \Return $\lambda_*$
\end{algorithmic}
\end{algorithm}

\subsection{Computing a calibrating potential}

Set $\tilde c(e)=c(e)-\lambda_*$.
Then $G$ has no negative cycles with respect to $\tilde c$ by definition of $\lambda_*$.
A potential $\phi$ such that $c_\phi(e)=\tilde c(e)+\phi(u)-\phi(v)\ge 0$ for all $e:u\to v$ can be obtained from shortest-path distances.

\begin{algorithm}[H]
\caption{Calibrating potential via shortest paths}\label{alg:potential}
\begin{algorithmic}[1]
\Require Graph $G=(V,E)$, reduced costs $\tilde c(e)=c(e)-\lambda_*$
\Ensure Potential $\phi$ with $c_\phi(e)\ge 0$ for all $e$
\State Add a super-source $s$ with zero-cost edges $(s\to v)$ to every $v\in V$
\State Run Bellman--Ford on $(V\cup\{s\},E\cup\{(s\to v)\})$ with costs $\tilde c$ to compute distances $\phi(v)=\mathrm{dist}(s,v)$
\State \Return $\phi$
\end{algorithmic}
\end{algorithm}

\begin{remark}
Because there are no negative cycles, Bellman--Ford terminates and returns finite distances.
The inequality $\phi(v)\le \phi(u)+\tilde c(u\to v)$ is exactly $c_\phi(u\to v)\ge 0$.
\end{remark}

\subsection{Extracting the tight subgraph and its SCC structure}

Given $\phi$, compute $c_\phi(e)$ and define $E^{(0)}=\{e:c_\phi(e)=0\}$ as in Definition~\ref{def:tight}.
This yields the tight subgraph $G^{(0)}$. SCC decomposition runs in $O(n+m)$ time (Tarjan/Kosaraju).
Aperiodicity of an SCC is certified by computing the gcd of its cycle lengths (linear-time in the SCC via a spanning tree + back-edge depth differences).

\begin{algorithm}[H]
\caption{Tight subgraph + SCC periodicity labels}\label{alg:tight-scc}
\begin{algorithmic}[1]
\Require $G=(V,E)$, costs $c$, $\lambda_*$, potential $\phi$
\Ensure Tight graph $G^{(0)}$ and SCCs labeled periodic/aperiodic
\State $E^{(0)}\gets \{u\to v\in E:\ c(u\to v)-\lambda_*+\phi(u)-\phi(v)=0\}$
\State Compute SCC decomposition of $G^{(0)}$
\ForAll{SCCs $H$}
\State Compute $\mathrm{per}(H)=$ gcd of cycle lengths in $H$
\If{$\mathrm{per}(H)=1$ and $|H|>1$} label aperiodic \Else label periodic \EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

\subsection{Complexity summary}

All objects in Section~\ref{sec:core-truth} are computable in polynomial time from the reduced finite graph:
\begin{itemize}
\item Karp minimal mean: $O(nm)$.
\item Bellman--Ford potential: $O(nm)$.
\item Tight graph extraction: $O(m)$.
\item SCC decomposition: $O(n+m)$.
\end{itemize}
Thus the canonical normalization and tight geometry can be produced and checked algorithmically as part of the finite certification pipeline.
