A4 Refereed article in a conference publication

Solving the induced subgraph problem in the randomized multiparty simultaneous messages model




AuthorsKari J., Matamala M., Rapaport I., Salo V.

EditorsChristian Scheideler

Conference nameInternational Colloquium on Structural Information and Communication Complexity

PublisherSpringer Verlag

Publishing placeBerlin

Publication year2015

Book title 22nd International Colloquium on Structural Information and Communication Complexit

Journal name in sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series titleLecture Notes in Computer Science

Number in series9439

Volume9439

First page 370

Last page384

ISBN978-3-319-25257-5

DOIhttps://doi.org/10.1007/978-3-319-25258-2_26(external)

Web address http://api.elsevier.com/content/abstract/scopus_id/84950327338(external)


Abstract

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.



Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 23:30