Your intuition about verifying optimal solutions has misled you here. Interesting optimization questions such as "shortest" or "best" are conventionally reformulated as decision questions about a particular bound. The verification then becomes easy: check to see, for instance, that the certificate path works and is shorter than the specified bound. A log-time search with such a verifier as a subroutine produces a polynomial verifier for the original optimality question.
It seems in section 2.2 the author points out that for a very special case of the snow blower problem, it is np complete ( see section 8 where they show a domain of polygons with holes). This special case might apply to snow blowing narrow paths through a field.
Right afterwards, the authors note that
> "the hardness of SBP in the fixed-throw model and in simple polygons is open. In fact, we do not even know what the optimal solutions are for simple cases like a square or rectangular domain."
which to me says that for the domain similar to an open field, or just a very wide pathway, the problem may be more complicated than NP-complete and they have not yet found an optimal solution for it.