• Mathematics > Combinatorics [Submitted on 10 Oct 2025 (v1), last revised 24 Feb 2026 (this version, v2)] Title:Multiparty equality in the local broadcast model View PDF HTML (experimental)Abstract:In this paper we consider the multiparty equality problem in graphs, where every vertex of a graph $G$ is given an input, and the goal of the vertices is to decide whether all inputs are equal. • We study this problem in the local broadcast model, where a message sent by a vertex is received by all its neighbors and the total cost of a protocol is the sum of the lengths of the messages sent by the vertices. • This setting was studied by Khan and Vaidya, who gave in 2021 a protocol achieving a 4-approximation in the general case. • We study this multiparty communication problem through the lens of network topology. • We design a new protocol for 2-connected graphs, whose efficiency relies on the notion of total vertex cover in graph theory. • This protocol outperforms the aforementioned 4-approximation in a number of cases.

Article Summaries:

  • Mathematics > Combinatorics [Submitted on 10 Oct 2025 (v1), last revised 24 Feb 2026 (this version, v2)] Title:Multiparty equality in the local broadcast model View PDF HTML (experimental)Abstract:In this paper we consider the multiparty equality problem in graphs, where every vertex of a graph $G$ is given an input, and the goal of the vertices is to decide whether all inputs are equal. We study this problem in the local broadcast model, where a message sent by a vertex is received by all its neighbors and the total cost of a protocol is the sum of the lengths of the messages sent by the vert

Sources: