Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Gábor Damásdi, Dániel Gerbner, Gyula O. H. Katona +8

Suppose that the vertices of a graph $G$ are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it…