---
_id: '11183'
abstract:
- lang: eng
  text: "Subgraph detection has recently been one of the most studied problems in
    the CONGEST model of distributed computing. In this work, we study the distributed
    complexity of problems closely related to subgraph detection, mainly focusing
    on induced subgraph detection. The main line of this work presents lower bounds
    and parameterized algorithms w.r.t structural parameters of the input graph:\r\n-
    On general graphs, we give unconditional lower bounds for induced detection of
    cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions
    from centralized parameterized complexity, we prove lower bounds in CONGEST for
    detecting patterns with a 4-clique, and for induced path detection conditional
    on the hardness of triangle detection in the congested clique.\r\n- On graphs
    of bounded degeneracy, we show that induced paths can be detected fast in CONGEST
    using techniques from parameterized algorithms, while detecting cycles and patterns
    of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show
    that induced subgraph detection is easy in CONGEST for any pattern graph. More
    specifically, we adapt a centralized parameterized algorithm for a more general
    maximum common induced subgraph detection problem to the distributed setting.
    In addition to these induced subgraph detection results, we study various related
    problems in the CONGEST and congested clique models, including for multicolored
    versions of subgraph-detection-like problems."
acknowledgement: "Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070)
  of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007)
  operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported
  by the European Research Council (ERC) under the European Union’s Horizon 2020 research
  and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François
  Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced
  subgraph detection [36]."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: No
author:
- first_name: Amir
  full_name: Nikabadi, Amir
  last_name: Nikabadi
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
citation:
  ama: 'Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs,
    multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A,
    eds. <i>25th International Conference on Principles of Distributed Systems</i>.
    Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.15">10.4230/LIPIcs.OPODIS.2021.15</a>'
  apa: 'Nikabadi, A., &#38; Korhonen, J. (2022). Beyond distributed subgraph detection:
    Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V.
    Gramoli, &#38; A. Milani (Eds.), <i>25th International Conference on Principles
    of Distributed Systems</i> (Vol. 217). Strasbourg, France: Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.15">https://doi.org/10.4230/LIPIcs.OPODIS.2021.15</a>'
  chicago: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
    Induced Subgraphs, Multicolored Problems and Graph Parameters.” In <i>25th International
    Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas,
    Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.15">https://doi.org/10.4230/LIPIcs.OPODIS.2021.15</a>.'
  ieee: 'A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced
    subgraphs, multicolored problems and graph parameters,” in <i>25th International
    Conference on Principles of Distributed Systems</i>, Strasbourg, France, 2022,
    vol. 217.'
  ista: 'Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced
    subgraphs, multicolored problems and graph parameters. 25th International Conference
    on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.'
  mla: 'Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection:
    Induced Subgraphs, Multicolored Problems and Graph Parameters.” <i>25th International
    Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas
    et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
    doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.15">10.4230/LIPIcs.OPODIS.2021.15</a>.'
  short: A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th
    International Conference on Principles of Distributed Systems, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2022.
conference:
  end_date: 2021-12-15
  location: Strasbourg, France
  name: OPODIS
  start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T07:56:35Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.15
ec_funded: 1
editor:
- first_name: Quentin
  full_name: Bramas, Quentin
  last_name: Bramas
- first_name: Vincent
  full_name: Gramoli, Vincent
  last_name: Gramoli
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
file:
- access_level: open_access
  checksum: 626551c14de5d4091573200ed0535752
  content_type: application/pdf
  creator: dernst
  date_created: 2022-05-02T07:53:00Z
  date_updated: 2022-05-02T07:53:00Z
  file_id: '11345'
  file_name: 2022_LIPICs_Nikabadi.pdf
  file_size: 790396
  relation: main_file
  success: 1
file_date_updated: 2022-05-02T07:53:00Z
has_accepted_license: '1'
intvolume: '       217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
  isbn:
  - '9783959772198'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Beyond distributed subgraph detection: Induced subgraphs, multicolored problems
  and graph parameters'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '11184'
abstract:
- lang: eng
  text: "Let G be a graph on n nodes. In the stochastic population protocol model,
    a collection of n indistinguishable, resource-limited nodes collectively solve
    tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
    first read each other’s states, and then update their local states. A rich line
    of research has established tight upper and lower bounds on the complexity of
    fundamental tasks, such as majority and leader election, in this model, when G
    is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
    in n polylog n pairwise interactions, with high probability, using at most polylog
    n states per node.\r\nIn this work, we consider the more general setting where
    G is an arbitrary regular graph, and present a technique for simulating protocols
    designed for fully-connected networks in any connected regular graph. Our main
    result is a simulation that is efficient on many interesting graph families: roughly,
    the simulation overhead is polylogarithmic in the number of nodes, and quadratic
    in the conductance of the graph. As a sample application, we show that, in any
    regular graph with conductance φ, both leader election and exact majority can
    be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
    using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
    and space-efficient population protocols for leader election and exact majority
    on graphs with good expansion properties. We believe our results will prove generally
    useful, as they allow efficient technology transfer between the well-mixed (clique)
    case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
  Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
  programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
  received from the European Union’s Horizon 2020 research and\r\ninnovation programme
  under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
  We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
  construction to non-regular graphs. We also thank anonymous reviewers for their
  useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Rati
  full_name: Gelashvili, Rati
  last_name: Gelashvili
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
citation:
  ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
    In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference on Principles
    of Distributed Systems</i>. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2022. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">10.4230/LIPIcs.OPODIS.2021.14</a>'
  apa: 'Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2022). Fast graphical
    population protocols. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th
    International Conference on Principles of Distributed Systems</i> (Vol. 217).
    Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>'
  chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
    Population Protocols.” In <i>25th International Conference on Principles of Distributed
    Systems</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
    217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>.
  ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
    protocols,” in <i>25th International Conference on Principles of Distributed Systems</i>,
    Strasbourg, France, 2022, vol. 217.
  ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
    25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
    vol. 217, 14.
  mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” <i>25th
    International Conference on Principles of Distributed Systems</i>, edited by Quentin
    Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022, doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.14">10.4230/LIPIcs.OPODIS.2021.14</a>.
  short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
    Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
  end_date: 2021-12-15
  location: Strasbourg, France
  name: OPODIS
  start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T08:09:39Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
  full_name: Bramas, Quentin
  last_name: Bramas
- first_name: Vincent
  full_name: Gramoli, Vincent
  last_name: Gramoli
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
external_id:
  arxiv:
  - '2102.08808'
file:
- access_level: open_access
  checksum: 2c7c982174c6f98c4ca6e92539d15086
  content_type: application/pdf
  creator: dernst
  date_created: 2022-05-02T08:06:33Z
  date_updated: 2022-05-02T08:06:33Z
  file_id: '11346'
  file_name: 2022_LIPICs_Alistarh.pdf
  file_size: 959406
  relation: main_file
  success: 1
file_date_updated: 2022-05-02T08:06:33Z
has_accepted_license: '1'
intvolume: '       217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '840605'
  name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
  isbn:
  - '9783959772198'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...