Adaptive majority problems for restricted query graphs and for weighted sets

Suppose that the vertices of a graph are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the (if it exists), and any vertex of this color is called a . We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by . It was shown by Saks and Werman that , where is the number of 1’s in the binary representation of .In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph on vertices are . We show that for any tree on an even number of vertices we have , and that for any tree on an odd number of vertices, we have . Our proof uses results about the weighted version of the problem for , which may be of independent interest. We also exhibit a sequence of graphs with such that has edges and vertices.