• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model

Jarkko Kari, Martín Matamala, Ivan Rapaport, Ville Salo, Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model. In: 22nd International Colloquium on Structural Information and Communication Complexit, Lecture Notes in Computer Science 9439, 370–384, Springer Verlag, 2015.

http://dx.doi.org/10.1007/978-3-319-25258-2_26

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.

BibTeX entry:

@INPROCEEDINGS{uconv1552108,
  title = {Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model},
  booktitle = {22nd International Colloquium on Structural Information and Communication Complexit},
  author = {Kari, Jarkko and Matamala, Martín and Rapaport, Ivan and Salo, Ville},
  volume = {9439},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer Verlag},
  pages = {370–384},
  year = {2015},
}

Edit publication