§3, TEST(V), second case, p. 38 — if TEST(V) = YES, every T-path has length ≥ V
ProvedHassinRSP.Rounding.test_yes_specConsider an instance of the restricted shortest path problem (vertices , , edges with , positive integer lengths and transition times ), a time budget , and a real . Hassin's test is specified at the top of §3: "This test has the following properties: If it outputs a positive answer then definitely OPT . If it outputs a negative answer, then all we know is that OPT ." This statement is the positive half.
If TEST(V) outputs YES — that is, for no integer is there a – path using only edges with , of transition time at most and rounded length — then every -path satisfies
In particular OPT . The conclusion covers all -paths, including those through edges with that TEST deletes. This is what allows the Rounding Algorithm to raise its lower bound to after a YES answer.
Formalization Note. "OPT " is expressed as a bound on every -path, so it holds vacuously, as it should, when no -path exists. The hypotheses and are not needed and are omitted.
import Mathlib import Definitions.Def_HassinRSP_Rounding_Setting
namespace HassinRSP.Rounding
theorem test_yes_spec (I : Instance) (hI : I.WellFormed) (T : ℕ) (ε : ℝ) (hε0 : 0 < ε)
(V : ℝ) :
testYes I T ε V → ∀ q, IsTPath I T q → V ≤ pathLen I q := by sorry
end HassinRSP.Rounding
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.