Exact Minimum-Event Explanations under Localized Observation Uncertainty

Changepoint detectors, trend filters and perception pipelines routinely propose sparse event explanations of time series. We study how to verify such proposals exactly: given interval-valued observations of a scalar trajectory whose velocity jumps are nonnegative, capped and confined to labelled timing windows, can at most k events explain them? The budget query is NP-complete in general. We identify a shared-endpoint reset: across an interval with exactly observed endpoints and a timing window that opens at its start, the full set of feasible outgoing velocities is one interval, whatever the incoming set. The reset confines combinatorial branching to uncertainty blocks of maximum length β and gives an exact algorithm in 2^β·poly(n, β, L) time with rational witness recovery; assuming the Exponential Time Hypothesis, no 2^o(β) algorithm exists. A five-interval construction shows why exactness is needed: a complete-history first-moment flow relaxation with full-horizon fractional lookahead accepts two events although every compatible trajectory needs three. In the verified comparisons, every ACCEPT has a rational witness and every REJECT an exact certificate. On 24 retail-log windows fixed before inference, local inference settles 666 of 672 budget queries versus 540 for a bound-based baseline; on two taxi-log panels it matches enumeration and a certifying MILP cascade at about 28% less CPU than enumeration. At fixed block size two, a separate prospective synthetic panel with n up to 130 yields 14 of 16 certified budget decisions, retaining two call-limited UNKNOWNs. Exact certificates also expose over-counting and model-inconsistent proposals from ℓ1 relaxations and trend filtering. We report null comparisons and a downstream pilot without local-inference gains.