  Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme
(PLS) is a distributed verification system dedicated to evaluating if a given
configured graph satisfies a certain property. It involves a centralized
prover, whose role is to provide proof that a given configured graph is a
yes-instance by means of assigning labels to the nodes, and a distributed
verifier, whose role is to verify the validity of the given proof via local
access to the assigned labels. In this paper, we introduce the notion of a
locally restricted PLS in which the prover's power is restricted to that of a
LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent
impossibilities of PLSs in the locally restricted setting, we turn to models
that relax the correctness requirements by allowing the verifier to accept some
no-instances as long as they are not "too far" from satisfying the property in
question. To this end, we evaluate (1) distributed graph optimization problems
(OptDGPs) based on the notion of an approximate proof labeling scheme (APLS)
(analogous to the type of relaxation used in sequential approximation
algorithms); and (2) configured graph families (CGFs) based on the notion of
atesting proof labeling schemes (TPLS) (analogous to the type of relaxation
used in property testing algorithms).
