Note on distributed certification of minimum spanning trees
share
A distributed proof (also known as local certification, or proof-labeling scheme) is a mechanism to certify that the solution to a graph problem is correct. It takes the form of an assignment of labels to the nodes, that can be checked locally. There exists such a proof for the minimum spanning tree problem, using O(log n log W) bit labels (where n is the number of nodes in the graph, and W is the largest weight of an edge). This is due to Korman and Kutten who describe it in concise and formal manner in [Korman and Kutten 07]. In this note, we propose a more intuitive description of the result, as well as a gentle introduction to the problem.
READ FULL TEXT