Distributed Property Testing for Subgraph-Freeness Revisited

Understand

In the subgraph-freeness problem, we are given a constant-size graph $H$, and wish to determine whether the network contains $H$ as a subgraph or not.

• The \emph{property-testing} relaxation of the problem only requires us to distinguish graphs that are $H$-free from graphs that are $\epsilon$-far from $H$-free, meaning an $\epsilon$-fraction of their edges must be removed to obtain an $H$-free graph.
• Recently, Censor-Hillel et.
• al.