Checking Global Graph Properties by Means of Local Computations: the Majority Problem

This paper is a contribution to the study of the general problem of characterizing those properties which can be computed on a graph or a network by means of local transformations. By using an abstract model based on graph relabelling systems we consider the majority problem : let G be a graph whose vertices have label A or B ; we say that label A has the majority if the number of A-labelled vertices is strictly greater than the number of B-labelled vertices (jGj A ? jGj B ). We prove that there exists graph relabelling systems deciding for every connected graph G whether jGj A ? jGj B (resp. jGj A = jGj B ) or not. On the other hand, we prove that no such system can decide if jGj A ? jGj B \Gamma m (resp. jGj A = jGj B \Gamma m), for any positive integer m. 1 Introduction One of the main characteristics of distributed systems is the local nature of the computation. A set of processors, connected in some specific way, try to reach a common goal (e.g. computing some function) after a..