English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Subgraph detection has recently been one of the most studied problems in theCONGEST model of distributed computing. In this work, we study the distributedcomplexity of problems closely related to subgraph detection, mainly focusingon induced subgraph detection. The main line of this work presents lower boundsand parameterized algorithms w.r.t structural parameters of the input graph:  -- On general graphs, we give unconditional lower bounds for induceddetection of cycles and patterns of treewidth 2 in CONGEST. Moreover, byadapting reductions from centralized parameterized complexity, we prove lowerbounds in CONGEST for detecting patterns with a 4-clique, and for induced pathdetection conditional on the hardness of triangle detection in the congestedclique.  -- On graphs of bounded degeneracy, we show that induced paths can bedetected fast in CONGEST using techniques from parameterized algorithms, whiledetecting cycles and patterns of treewidth 2 is hard.  -- On graphs of bounded vertex cover number, we show that induced subgraphdetection is easy in CONGEST for any pattern graph. More specifically, we adapta centralized parameterized algorithm for a more general maximum common inducedsubgraph detection problem to the distributed setting.  In addition to these induced subgraph detection results, we study variousrelated problems in the CONGEST and congested clique models, including formulticolored versions of subgraph-detection-like problems.

Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters