Solving the induced subgraph problem in the randomized multiparty simultaneous messages model
Salo V.; Matamala M.; Rapaport I.; Kari J.
https://urn.fi/URN:NBN:fi-fe2021042714175
Tiivistelmä
We study the message size complexity of recognizing, under the broadcast congested clique model, whether a fixed graph H appears in a given graph G as a minor, as a subgraph or as an induced subgraph. The n nodes of the input graph G are the players, and each player only knows the identities of its immediate neighbors. We are mostly interested in the one-round, simultaneous setup where each player sends a message of size O(logn) to a referee that should be able then to determine whether H appears in G. We consider randomized protocols where the players have access to a common random sequence. We completely characterize which graphs H admit such a protocol. For the particular case where H is the path of 4 nodes, we present a new notion called twin ordering, which may be of independent interest.
Kokoelmat
- Rinnakkaistallenteet [19207]