Locally Restricted Proof Labeling Schemes (Full Version)

Yuval Emek, Yuval Gil, Shay Kutten

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 satisfie…